9 ms·

I also work at Google and what mystifies me when I do interviews is just how consistently people manage to screw up even the medium difficulty questions. I used

by jfasi 8y ago

I also work at Google and what mystifies me when I do interviews is just how consistently people manage to screw up even the medium difficulty questions. I used to love asking this question until it was banned: https://programmingpraxis.com/2012/01/20/knights-on-a-keypad/ https://programmingpraxis.com/2012/01/20/knights-on-a-keypad... This is a great question because it has several levels of solutions: 1. A recursive solution that iterates over all sequences, exponential time and logarithmic in space. Interviewing for T3 (entry level, think college grad), getting only this far in 45 minutes earns a "leaning no hire" in my book. 2. The above solution except with memoization, which reduces the runtime to linear but requires linear space. This one earns a "leaning hire" from me. 3. A dynamic programming solution that takes linear time and constant space. This one gets a "hire" to a "strong hire," depending on the elegance of the implementation and the strength of the discussion we have around it. 4. A logarithmic time solution involving adjacency matrices, matrix multiplication, and binary decomposition of numbers. I've never seen anyone get this and I only learned about it after months of asking this question. It's shocking how few candidates actually got as far as solution 1. I kinda want to open this up to the HN comments section, because this does not strike me as a brutally difficult problem, but the rate at which people fell on their faces when presented with this question suggests either something about our interview process or about the candidates we interview. EDIT: A clarification about “getting as far as” a particular solution: I’m not sitting there stone faced taking notes, I provide hints and prods and suggestions to push candidates toward more optimal solutions. I want the candidate to get as far as possible because it feels good to watch someone succeed, but oftentimes they run out of steam or take forever to implement their solution. In particular with respect to solution 1, if that’s as far as a candidate can get despite my recommendations, that’s not a good sign for their algorithmic ability.

aaomidi 8y ago
I mean I'm surprised you don't see why this question is plain stupid. I've had to deal with an algorithm problem of this difficulty once in my entire work life and I was given a week time to go figure out the best way to go about this. Your problem creates an unrealistic standard of a software developer. You don't get to see something like their coding quality which is a lot more important in a candidate than their ability to solve an arbitrary algorithms question. Especially since these algorithm quesstions are now being studied for the sake of interviews. Rather than to learn something. It's shocking to me how many engineers I come across that think having an algorithms based interview actually gives them good results.
- kamaal 8y ago
  >>I mean I'm surprised you don't see why this question is plain stupid. Its more psychological than technical. Once a person knows how to do a thing, they start to think any one who doesn't, is stupid. Their intelligence becomes the baseline to measure others intelligence.
  - aaomidi 8y ago
    I agree with this. My question always is why do you think this is important for the position you're hiring. Does knowing this question mean they're actually good for your position? This is turning into the situation I've seen in places with serious entrance exams for universities. For example in Iran, a lot of not so talented but have great memorization and afforded to do mindless practice exams are making it into higher education while creative and talented and less fortunate people are staying out. There are entire businesses built around practicing algorithm questions now, this is not a good sign.
jasondclinton 8y ago
I wouldn't be able to answer this question in the time allotted and would heavily discount its signal if I were on the hiring committee with this question in the candidate's packet. It tests for algorithm memorization which is not a hiring signal.
- jfasi 8y ago
  What memorized algorithm does this test for? As far as I know there is no algorithm to do this, and this interview tests for algorithm design rather than memorization.
  - jasondclinton 8y ago
    You said above that you have set LNH for a T3 writing out the obvious solution to your question. The problem is that optimizing that solution comes one of two ways: 1. having seen the specific class of problem before and knowing, as you're writing that solution, to stop and switch to the class of solution you've seen before that would solve the problem more efficiently, or 2. finishing the obvious, poorly performing solution and then optimizing it like an real engineer would do. The problem is that there's not going to be enough time for this to occur in the interview session. The act of writing out the poorly performing solution will consume the entire session. Therefore, the only way someone would have passed your interview question would have been if they had seen this class of problem before.
    - sadamznintern 8y ago
      I'm really glad someone is seeing this for what it is. Too often people claim that you should go for the naive solution first, and then iterate, when that really doesn't work in the dynamics of a normal interview.
    - jfasi 8y ago
      This is a fair point, even tough it doesn’t answer my question. When I interview I split up the coding and the algorithms assessments: if someone quickly and correctly implements the naive solution, I consider myself justified in grading them as solid in coding and moving on and having an algorithmic design discussion for the rest of the interview so I can speak more to their algorithms abilities. If someone fails to design anything more sophisticated than number 1 despite my guidance, or takes an unreasonable amount of time to implement it, that’s a signal. Also, let’s keep in mind a hiring recommendation isn’t a judgment of a person’a abilities as an engineer, it’s a judgement of how badly we should be trying to hire them relative to other candidates. My LNH is a statement that the candidate is solid but not stellar enough to extend an offer to. If our hiring pool were restricted or we needed to hire more people my assessment would be accordingly softened.
pcwalton 8y ago
> I kinda want to open this up to the HN comments section, because this does not strike me as a brutally difficult problem, but the rate at which people fell on their faces when presented with this question suggests either something about our interview process or about the candidates we interview. Because whiteboard coding is stressful and hard. I still kick myself for almost failing to get a basic sorting question right back in 2009, because the interviewer disguised it as a question about horse racing and it was interview 8 at the end of the day. (I still ended up getting an offer, but I turned it down.)
jarsin 8y ago
> t's shocking how few candidates actually got as far as solution How many people in the real world sit around and practice dynamic programming questions all day?? The answer is ZERO!
- sadamznintern 8y ago
  It is >0, and those people make more than me :(
- kamaal 8y ago
  >>How many people in the real world sit around and practice dynamic programming questions all day?? You will surprised how many people as a matter of fact actually do this. In fact for a lot of people the whole purpose of a day job is to pay them salaries so that practice interview questions to hop on the next jobs. The bad news is many companies think these sort of puzzle solving skills are penultimate level of software engineering skills and pay top salaries, so these people don't even worry about being bad at their current jobs. Do these for a few years, and pad big brands to your resume and then you are automatically considered something special and qualified for big title promotions.
  - jarsin 8y ago
    Oh trust me I know. I was being a smart ass and pointing out that only people that don't live in reality do this stupid shit. Dynamic programming interview questions, in particular, are the epitome of the absurdity of technical interviews.
WorldMaker 8y ago
It becomes brutally difficult in the context of a time-limited interview. You have the pressures of: 1) anxiety about limited time, 2) anxiety about hidden "tricks" or "cleverness", 3) inter-personal anxiety. It's that last one that I think algorithms/white-board coding entirely fails to see the trees for the forest. You would think as an industry that seems to lean heavily towards introverts and people in various places on the autism and social disorder spectrums, that the industry would not rely so much on high-pressure inter-personal communication scenarios for interviewing. Which is not to say that soft skills don't matter: they absolutely do, and most industries their job interviews are much more highly focused on soft skills. The point is that you are testing soft and hard skills together in a highly charged mix. If I want to sit down and play with an algorithms problem, I'd probably like to do it in a quiet room with no one watching/looking over my shoulder, and if I'm writing anything for most of the thought time it's scribbles and doodles, not algorithm-appropriate diagrams. "Programmer's Tourette's" of a sort imply that I'd probably be swearing at it for a while as I work to make sense of it. Asking a complicated algorithms question in a whiteboard scenario requires me to "play-act" a more linear string of thoughts, which diagram nicely, than I would use in an actual puzzle situation, while trying to be personal/presentable/well-spoken. I can certainly do that, but that mix of social skills and problem solving skills is very rarely needed in real life where we mostly compartmentalize such things to meetings versus coding time. Then add in the ticking clock anxiety, that I don't feel like I have time to breathe, much less patiently tease out a solution to the problem. Then add in the exhaustions of jet lag and trying to do all of that for 8 hours. I feel like a lot of these sorts of questions, I could solve the problem rather well on my own time, or I could be a great, sociable, and presentable candidate with smart thoughts but maybe not immediate solutions. You want to the test for the former, but present only situations where the latter works well. I feel like I'm not far from a baseline human on inter-personal skills, and even am somewhat more extrovert than the average programmer, and knowing that I have problems doing "both" the soft and hard skills for an eight hour interview day, I sometimes can't imagine how anyone in this industry gets hired because it's almost like we've optimized interviews to be intentional hells for programmers by trying to test hard skills in high pressure soft skills environments. I very much believe that the technical interview culture as it exists today meets the definition of hazing [1], and that one day the industry will look back on it and wonder what was it thinking. [1] https://en.wikipedia.org/wiki/Hazing https://en.wikipedia.org/wiki/Hazing
sadamznintern 8y ago
I was asked this question at a company (unicorn, but lower bar than Google, got the offer) and I only described #1. Thanks for calling me stupid though!
- jfasi 8y ago
  That wasn’t my intention, and I updated my comment to clarify. Did your interviewer offer suggestions or just sit there?
  - sadamznintern 8y ago
    It may not have been the intention but I'm honestly aghast at the utter elitism coming out of Google and Facebook. I get that you are "superior humans" that are plucked from top institutions making 25% more than me at Amazon, but you don't have to keep emphasizing it. My interviewer offered suggestions. Finally I described memoizing it (can be done with 2 lines in Python with a dictionary) though he was more interested in how to do it without extra space by utilizing a BFS that uses the input list as a queue. Then he ran off for another meeting.
    - jfasi 8y ago
      > I'm honestly aghast at the utter elitism coming out of Google and Facebook I presume it's Google and Facebook's extremely high hiring bar that you're attributing to elitism? Let me attempt to reframe that for you in a way that I hope will let you let go of some of the anger I'm picking up on: There's no denying that Google and Facebook target top-tier institutions and put their candidates through hell. However, I don't attribute this to elitism. I personally got my start at a less-than-stellar CS program, and I go out of my way to recruit there as an alum. I've detected no elitism from any recruiters, interviewers, or hiring managers, and I've seen a number of people hired as interns and full time engineers as a direct result of my outreach. If Google were as elitist an organization as you seem to think, I and the people I've helped get hired would never have had a chance. So then what explains the high bar? Simple necessity. I can't share details, but the number of applications we receive for every opening is staggering. What's more, when we approach people in industry and academia, we see a high rate of interest. The blunt truth is that we are more selective about hiring because we can be. When a hundred people (not real figures) apply for each available posting and your hiring pipeline is staffed well enough to interview all of them, you'd better believe you're going to hire the best one in that pool. This isn't a Google thing, this isn't a Facebook thing, this is a rational actor thing. So no, I don't think you're stupid for coming up with a suboptimal solution, I have no reason to think you're a bad engineer, and I wouldn't reject you because your background. However, given a pool of candidates of whom some got as far as solution 3 and some got as far as solution 1, I'm going to more enthusiastically recommend hiring the ones who got solution 3.
jstewartmobile 8y ago
English is a rich and fuzzy language. I have more trouble translating problems like this into human than I do solving them. Sometimes interviewers will respond to questions about the question. Others will only repeat the question as-stated. With the latter, I'd be sunk. Pólya's first principle.
mlevental 8y ago
>A logarithmic time solution involving adjacency matrices, matrix multiplication, and binary decomposition of numbers. can you post a link to this solution? sounds cool. edit: lol i just realized this is simply multiplying the adjacency matrix and what you mean by binary decomposition of numbers is just exponentiation by squaring. it's funny now that i realized i'll probably never figure out the dp solution. edit2: got it. number of length n paths for some key u is sum of n-1 paths across "knight neighbors" of u. base case is length 1 path which is just # of neighbors. it's funny this problem is designed in a particular way. using the keypad instead of a chessboard lets you write down the graph by hand rather than actually procedurally generating it (which is awkward with lots of literal edge conditions to check).
- chillee 8y ago
  Yeah this is one of the "standard" uses for matrix multiplication. Another one is calculating the N-th fibonacci number in logarithmic time (or any linear recurrence).
morazow 8y ago
How would you rate this solution? Assuming we have static keypad grid. long moves(int start = 1, int len) { assert(len > 0); long[] cur = new long[10]; for (int i = 0; i < 10; i++) { cur[i] = 1; } long[] nxt = new long[10]; while (len-- > 0) { nxt[0] = cur[4] + cur[6]; nxt[1] = cur[8] + cur[6]; nxt[2] = cur[7] + cur[9]; nxt[3] = cur[4] + cur[8]; nxt[4] = cur[3] + cur[9] + cur[0]; nxt[5] = 0; nxt[6] = cur[1] + cur[7] + cur[0]; nxt[7] = cur[2] + cur[6]; nxt[8] = cur[1] + cur[3]; nxt[9] = cur[4] + cur[2]; for (int i = 0; i < 10; i++) { cur[i] = nxt[i]; } } return cur[start]; }
- bjourne 8y ago
  Very good! However there is an off-by-one error as the exercise asks for paths of lengths not number of nodes. If you came up with that in 45 minutes without googling, you are very strong indeed.
bjourne 8y ago
Fun exercise. This is how far I got after about 45 minutes: https://gist.github.com/bjourne/7e45d41e8e4f5518bb92f6df7978051e https://gist.github.com/bjourne/7e45d41e8e4f5518bb92f6df7978... I wasted half the time not getting that you don't need to store the paths only the counts! But this was in my quiet home and I would probably fluke out in an interview setting where you have to talk while you code. I'm still going to consider myself a pretty good coder. Perhaps not Google material, but pretty damn good still. :)

by jfasi 8y ago

aaomidi 8y ago

I mean I'm surprised you don't see why this question is plain stupid. I've had to deal with an algorithm problem of this difficulty once in my entire work life and I was given a week time to go figure out the best way to go about this. Your problem creates an unrealistic standard of a software developer. You don't get to see something like their coding quality which is a lot more important in a candidate than their ability to solve an arbitrary algorithms question. Especially since these algorithm quesstions are now being studied for the sake of interviews. Rather than to learn something. It's shocking to me how many engineers I come across that think having an algorithms based interview actually gives them good results.

kamaal 8y ago
>>I mean I'm surprised you don't see why this question is plain stupid. Its more psychological than technical. Once a person knows how to do a thing, they start to think any one who doesn't, is stupid. Their intelligence becomes the baseline to measure others intelligence.
- aaomidi 8y ago
  I agree with this. My question always is why do you think this is important for the position you're hiring. Does knowing this question mean they're actually good for your position? This is turning into the situation I've seen in places with serious entrance exams for universities. For example in Iran, a lot of not so talented but have great memorization and afforded to do mindless practice exams are making it into higher education while creative and talented and less fortunate people are staying out. There are entire businesses built around practicing algorithm questions now, this is not a good sign.

jasondclinton 8y ago

I wouldn't be able to answer this question in the time allotted and would heavily discount its signal if I were on the hiring committee with this question in the candidate's packet. It tests for algorithm memorization which is not a hiring signal.

jfasi 8y ago
What memorized algorithm does this test for? As far as I know there is no algorithm to do this, and this interview tests for algorithm design rather than memorization.
- jasondclinton 8y ago
  You said above that you have set LNH for a T3 writing out the obvious solution to your question. The problem is that optimizing that solution comes one of two ways: 1. having seen the specific class of problem before and knowing, as you're writing that solution, to stop and switch to the class of solution you've seen before that would solve the problem more efficiently, or 2. finishing the obvious, poorly performing solution and then optimizing it like an real engineer would do. The problem is that there's not going to be enough time for this to occur in the interview session. The act of writing out the poorly performing solution will consume the entire session. Therefore, the only way someone would have passed your interview question would have been if they had seen this class of problem before.
  - sadamznintern 8y ago
    I'm really glad someone is seeing this for what it is. Too often people claim that you should go for the naive solution first, and then iterate, when that really doesn't work in the dynamics of a normal interview.
  - jfasi 8y ago
    This is a fair point, even tough it doesn’t answer my question. When I interview I split up the coding and the algorithms assessments: if someone quickly and correctly implements the naive solution, I consider myself justified in grading them as solid in coding and moving on and having an algorithmic design discussion for the rest of the interview so I can speak more to their algorithms abilities. If someone fails to design anything more sophisticated than number 1 despite my guidance, or takes an unreasonable amount of time to implement it, that’s a signal. Also, let’s keep in mind a hiring recommendation isn’t a judgment of a person’a abilities as an engineer, it’s a judgement of how badly we should be trying to hire them relative to other candidates. My LNH is a statement that the candidate is solid but not stellar enough to extend an offer to. If our hiring pool were restricted or we needed to hire more people my assessment would be accordingly softened.

pcwalton 8y ago

> I kinda want to open this up to the HN comments section, because this does not strike me as a brutally difficult problem, but the rate at which people fell on their faces when presented with this question suggests either something about our interview process or about the candidates we interview. Because whiteboard coding is stressful and hard. I still kick myself for almost failing to get a basic sorting question right back in 2009, because the interviewer disguised it as a question about horse racing and it was interview 8 at the end of the day. (I still ended up getting an offer, but I turned it down.)

jarsin 8y ago

> t's shocking how few candidates actually got as far as solution How many people in the real world sit around and practice dynamic programming questions all day?? The answer is ZERO!

sadamznintern 8y ago
It is >0, and those people make more than me :(
kamaal 8y ago
>>How many people in the real world sit around and practice dynamic programming questions all day?? You will surprised how many people as a matter of fact actually do this. In fact for a lot of people the whole purpose of a day job is to pay them salaries so that practice interview questions to hop on the next jobs. The bad news is many companies think these sort of puzzle solving skills are penultimate level of software engineering skills and pay top salaries, so these people don't even worry about being bad at their current jobs. Do these for a few years, and pad big brands to your resume and then you are automatically considered something special and qualified for big title promotions.
- jarsin 8y ago
  Oh trust me I know. I was being a smart ass and pointing out that only people that don't live in reality do this stupid shit. Dynamic programming interview questions, in particular, are the epitome of the absurdity of technical interviews.

WorldMaker 8y ago

It becomes brutally difficult in the context of a time-limited interview. You have the pressures of: 1) anxiety about limited time, 2) anxiety about hidden "tricks" or "cleverness", 3) inter-personal anxiety. It's that last one that I think algorithms/white-board coding entirely fails to see the trees for the forest. You would think as an industry that seems to lean heavily towards introverts and people in various places on the autism and social disorder spectrums, that the industry would not rely so much on high-pressure inter-personal communication scenarios for interviewing. Which is not to say that soft skills don't matter: they absolutely do, and most industries their job interviews are much more highly focused on soft skills. The point is that you are testing soft and hard skills together in a highly charged mix. If I want to sit down and play with an algorithms problem, I'd probably like to do it in a quiet room with no one watching/looking over my shoulder, and if I'm writing anything for most of the thought time it's scribbles and doodles, not algorithm-appropriate diagrams. "Programmer's Tourette's" of a sort imply that I'd probably be swearing at it for a while as I work to make sense of it. Asking a complicated algorithms question in a whiteboard scenario requires me to "play-act" a more linear string of thoughts, which diagram nicely, than I would use in an actual puzzle situation, while trying to be personal/presentable/well-spoken. I can certainly do that, but that mix of social skills and problem solving skills is very rarely needed in real life where we mostly compartmentalize such things to meetings versus coding time. Then add in the ticking clock anxiety, that I don't feel like I have time to breathe, much less patiently tease out a solution to the problem. Then add in the exhaustions of jet lag and trying to do all of that for 8 hours. I feel like a lot of these sorts of questions, I could solve the problem rather well on my own time, or I could be a great, sociable, and presentable candidate with smart thoughts but maybe not immediate solutions. You want to the test for the former, but present only situations where the latter works well. I feel like I'm not far from a baseline human on inter-personal skills, and even am somewhat more extrovert than the average programmer, and knowing that I have problems doing "both" the soft and hard skills for an eight hour interview day, I sometimes can't imagine how anyone in this industry gets hired because it's almost like we've optimized interviews to be intentional hells for programmers by trying to test hard skills in high pressure soft skills environments. I very much believe that the technical interview culture as it exists today meets the definition of hazing [1], and that one day the industry will look back on it and wonder what was it thinking. [1] https://en.wikipedia.org/wiki/Hazing https://en.wikipedia.org/wiki/Hazing

sadamznintern 8y ago

I was asked this question at a company (unicorn, but lower bar than Google, got the offer) and I only described #1. Thanks for calling me stupid though!

jfasi 8y ago
That wasn’t my intention, and I updated my comment to clarify. Did your interviewer offer suggestions or just sit there?
- sadamznintern 8y ago
  It may not have been the intention but I'm honestly aghast at the utter elitism coming out of Google and Facebook. I get that you are "superior humans" that are plucked from top institutions making 25% more than me at Amazon, but you don't have to keep emphasizing it. My interviewer offered suggestions. Finally I described memoizing it (can be done with 2 lines in Python with a dictionary) though he was more interested in how to do it without extra space by utilizing a BFS that uses the input list as a queue. Then he ran off for another meeting.
  - jfasi 8y ago
    > I'm honestly aghast at the utter elitism coming out of Google and Facebook I presume it's Google and Facebook's extremely high hiring bar that you're attributing to elitism? Let me attempt to reframe that for you in a way that I hope will let you let go of some of the anger I'm picking up on: There's no denying that Google and Facebook target top-tier institutions and put their candidates through hell. However, I don't attribute this to elitism. I personally got my start at a less-than-stellar CS program, and I go out of my way to recruit there as an alum. I've detected no elitism from any recruiters, interviewers, or hiring managers, and I've seen a number of people hired as interns and full time engineers as a direct result of my outreach. If Google were as elitist an organization as you seem to think, I and the people I've helped get hired would never have had a chance. So then what explains the high bar? Simple necessity. I can't share details, but the number of applications we receive for every opening is staggering. What's more, when we approach people in industry and academia, we see a high rate of interest. The blunt truth is that we are more selective about hiring because we can be. When a hundred people (not real figures) apply for each available posting and your hiring pipeline is staffed well enough to interview all of them, you'd better believe you're going to hire the best one in that pool. This isn't a Google thing, this isn't a Facebook thing, this is a rational actor thing. So no, I don't think you're stupid for coming up with a suboptimal solution, I have no reason to think you're a bad engineer, and I wouldn't reject you because your background. However, given a pool of candidates of whom some got as far as solution 3 and some got as far as solution 1, I'm going to more enthusiastically recommend hiring the ones who got solution 3.

jstewartmobile 8y ago

English is a rich and fuzzy language. I have more trouble translating problems like this into human than I do solving them. Sometimes interviewers will respond to questions about the question. Others will only repeat the question as-stated. With the latter, I'd be sunk. Pólya's first principle.

mlevental 8y ago

>A logarithmic time solution involving adjacency matrices, matrix multiplication, and binary decomposition of numbers. can you post a link to this solution? sounds cool. edit: lol i just realized this is simply multiplying the adjacency matrix and what you mean by binary decomposition of numbers is just exponentiation by squaring. it's funny now that i realized i'll probably never figure out the dp solution. edit2: got it. number of length n paths for some key u is sum of n-1 paths across "knight neighbors" of u. base case is length 1 path which is just # of neighbors. it's funny this problem is designed in a particular way. using the keypad instead of a chessboard lets you write down the graph by hand rather than actually procedurally generating it (which is awkward with lots of literal edge conditions to check).

chillee 8y ago
Yeah this is one of the "standard" uses for matrix multiplication. Another one is calculating the N-th fibonacci number in logarithmic time (or any linear recurrence).

morazow 8y ago

How would you rate this solution? Assuming we have static keypad grid. long moves(int start = 1, int len) { assert(len > 0); long[] cur = new long[10]; for (int i = 0; i < 10; i++) { cur[i] = 1; } long[] nxt = new long[10]; while (len-- > 0) { nxt[0] = cur[4] + cur[6]; nxt[1] = cur[8] + cur[6]; nxt[2] = cur[7] + cur[9]; nxt[3] = cur[4] + cur[8]; nxt[4] = cur[3] + cur[9] + cur[0]; nxt[5] = 0; nxt[6] = cur[1] + cur[7] + cur[0]; nxt[7] = cur[2] + cur[6]; nxt[8] = cur[1] + cur[3]; nxt[9] = cur[4] + cur[2]; for (int i = 0; i < 10; i++) { cur[i] = nxt[i]; } } return cur[start]; }

bjourne 8y ago
Very good! However there is an off-by-one error as the exercise asks for paths of lengths not number of nodes. If you came up with that in 45 minutes without googling, you are very strong indeed.

bjourne 8y ago

Fun exercise. This is how far I got after about 45 minutes: https://gist.github.com/bjourne/7e45d41e8e4f5518bb92f6df7978051e https://gist.github.com/bjourne/7e45d41e8e4f5518bb92f6df7978... I wasted half the time not getting that you don't need to store the paths only the counts! But this was in my quiet home and I would probably fluke out in an interview setting where you have to talk while you code. I'm still going to consider myself a pretty good coder. Perhaps not Google material, but pretty damn good still. :)