9 ms·

Google Interview Questions Deconstructed: The Knight’s Dialer

98 points by thanato0s 6y ago

username90 6y ago
Counting the number of paths when you have loops is easiest using a connection matrix and matrix exponentiation. Then you get log(n) time.
- deleted 6y ago
  [deleted]
- defen 6y ago
  I think this hits on why these types of problems are potentially bad. You could be the world's worst software engineer, but if you'd taken a graph theory course recently, you'd pattern match this, say "sure, can I use Matlab?" and be done in under 10 minutes. Or you could have tons of experience deploying robust production systems but have never happened to learn / need to use dynamic programming, in which case coming up with it in 45 minutes during an interview is not going to happen.
  - username90 6y ago
    The junior and the senior aren't competing for the same job though, this just checks that you still remember the theory you learned in college. And no, just because you are senior doesn't mean that you get a free pass forgetting everything you learned in college. I haven't practiced problems like this in over 5 years and I still ace them.
    - noitpmeder 6y ago
      /r/iamverysmart/
      - username90 6y ago
        What is your point? Companies wants to hire smart people which is why they have these interviews. This applies no matter what level people are at. "I forgot" isn't valid defense. All the people in these threads who says things like "I knew this but forgot" are really cringy.
        Judgmentality 6y ago
        /r/woosh
        username90 6y ago
        Do you think this is a good way to discuss things at HN?
        Judgmentality 6y ago
        I believe that HN needs more humor, not less - so yes.
        noarchy 6y ago
        The point may be that many (if they're truly senior, not someone with 3-5 years in the industry) will not have used these theories in 10+ years. The real-world application is questionable.
        username90 6y ago
        And my point is that I'd rather hire someone who didn't forget these things. When you learn something well you don't forget, it is like riding a bike. If you learned how to ride a bike 10 yards and then stopped and never did it again then you would forget how to do it, saying "I passed the bike riding test when I was 10, I don't need to do it again" isn't a good defense. I mean, why did you even go to college if you intended to just forget everything afterwards instead of learning the things properly for life? I'd rather not hire people who just do the work necessary to pass and get the degree and don't want to learn more.
    - defen 6y ago
      > this just checks that you still remember the theory you learned in college. Sure, but not everyone went to college or studied computer science / math. This seems like one of those problems that's really just testing a very specific type of preexisting knowledge.
      - username90 6y ago
        You'll get full score even if you don't know the matrix solution, just doing a memoized recursive one is enough. However if you had that specific knowledge then they still test whether they have the skills to apply esoteric knowledge correctly which is also very valuable. Anyway, Google no longer has this question. Once it gets known outside Google bans it from interviews. Sometimes people give banned questions but in general they don't and it is taken into account. I remember it being popular as a question 4 years ago, popular questions tend to leak quickly and get banned though.
        Gunax 6y ago
        According to the blog post, the interviewers weren't even aware of the matrix solution until one candidate brought it up.
        KnobbleMcKnees 6y ago
        I assume they all immediately handed in their letters of resignation and/or hired the candidate in as a principle engineer. Sarcasm aside, the very fact that they ban questions demonstrates how useless these types of questions really are. If you ban it because people might know it due to its popularity then what are you testing for? I thought it was for whether a candidate could solve the problem, but it appears to be to check which percentile of a special 'knowledge' club they belong to...
      - bakuninsbart 6y ago
        If you are an experienced programmer, how long does it take you to learn the handful or so algs/concepts you need for these kinds of problems? It'd probably 20-30 hours of learning, which is a reasonable expectation to ace interviews. - And it is not like you have to necessarily come up with a solution all by yourself, communicating your issues well, and the interviewer will probably help you, if you have an otherwise impressive résume it shouldn't pose a problem at all.
  - nitwit005 6y ago
    I wouldn't be surprised if people occasionally re-create famous math problems, given how many interview questions seem to get created these days.
  - kevincox 6y ago
    If someone just pattern matched it I would give them a backup question. The point of these questions isn't seeing if they can solve it, it is seeing how they think about problems. I'm also not worried if they make a good solution, or even get a solution at all. But almost all candidates can start making progress, come up with some possible solutions and tell me about those solutions.
- Jabbles 6y ago
  That is covered in the next blogpost: https://alexgolec.dev/knights-dialer-logarithmic-time-edition/ https://alexgolec.dev/knights-dialer-logarithmic-time-editio...
- joshbuckler 6y ago
  If you then diagonalize that connection matrix, you can get constant time (though you might have to make a special case for starting at the `5` key): "Diagonalization can be used to efficiently compute the powers of a matrix..." [1] [1] https://en.wikipedia.org/wiki/Diagonalizable_matrix#Application_to_matrix_functions https://en.wikipedia.org/wiki/Diagonalizable_matrix#Applicat...
  - username90 6y ago
    Diagonalizing the matrix makes it easier to calculate the exponent by making it a series of numeric exponentials, but calculating the exponent of a number is still a log(n) operation. Also given that this is a discrete problem moving to floating points like you'd likely have to do when you diagonalize could easily lead to errors in the final answer.
  - twiceaday 6y ago
    I tried but Wolfram Alpha doesn't take inputs that long hah. In any case even if it works you will likely get irrational terms which will make it only theoretically nice but not practically computable, like the closed-form Fibonacci formula.
warmfuzzykitten 6y ago
Typical brain-teaser interview question that will have absolutely no correlation to on-the-job performance but makes the interviewer feel really smart. I thought Google had gotten away from these.
- joshuamorton 6y ago
  This isn't a brainteaser. It's a programming problem. Brainteasers are like "how many ping pong balls fit in a 747" or "you wake up an inch tall in a blender, the blades start spinning in a minute. How do you survive."
  - throwaways885 6y ago
    > how many ping pong balls fit in a 747 This one does seem useful. Being able to do back-of-the-napkin (i.e. fermi problem) calculations is a pretty good skill.
    - watwut 6y ago
      Back of napkin that requires you to know what 747 is wrong be correlated with anything programming related.
    - crocal 6y ago
      Actually a typical GMAT question...
    - toast0 6y ago
      It might be an OK problem if the interviewee is familiar with 747s and ping pong balls, and will be interacting with physical objects as part of their job. I have a terrible time with physical measurments and area and space, but thankfully it's not relevant to my work.
    - CydeWeys 6y ago
      Google does still use questions like this, it's just that they're relevant to programming/system design. So a question might be "How many servers are needed to run Gmail?" The reason the 747 question is bad is because it has little to do with programming and a lot to do with how much you happen to know about planes and ping pong balls and how to estimate volumes of irregularly shaped objects, none of which have much if any correlation with programming ability.
mcqueenjordan 6y ago
This is a fun problem, but it's a terrible interview question for trying to hire software engineers.
- kevincox 6y ago
  Why? Note that the point of the problem isn't if you can solve it. It is how you approach it. A problem like this gives you a lot of signal. * Can the person program at all. * Do they consider the performance of possible solutions. * Are they good at explaining their thought process. * Do they consider edge cases? * Do they write tests? I'm not saying that it should be the only interview, or it is the most important. But it clearly provides differentiation between candidates. I'm also not saying it is the perfect way to get this differentiation, but I think it is far from "terrible".
  - xienze 6y ago
    > * Can the person program at all. * Do they consider the performance of possible solutions. * Are they good at explaining their thought process. * Do they consider edge cases? * Do they write tests? All good things to look for. The problem is, day-to-day you don't have to do all of those things in 45 minutes while several people at the table watch you. Personally I'm a fan of a short programming exercise (perhaps even this problem) that you can take home and walk through with the team at a later time. I know those are detested by some, but I think they're fair (assuming the task is not something outrageous; something that can be knocked out in an evening perhaps) and give a much better idea of what an employee is capable of.
  - vanusa 6y ago
    Can the person program at all. Do they consider the performance of possible solutions. * Are they good at explaining their thought process. * Do they consider edge cases? * Do they write tests?* That's what you'd like to think it's testing for. In reality, it's testing for: "Here's a hoop - would you like to jump through it for me please? BTW not only will stumbling or even hesitating pretty much disqualify you - we love to dish after hours about those who fail to make the cut."
- 6y ago
deleted 6y ago
[deleted]
dudus 6y ago
At the end he hints at a better solution. Now I'm intrigued.
- chromatin 6y ago
  It's in a follow-on article (or just think back to your undergraduate discrete mathematics or graph theory courses)
- deleted 6y ago
  [deleted]
umaar 6y ago
On the subject of Google Interview challenges and keypads, I wrote about a Google keypad challenge here: https://umaar.com/blog/my-code-exercise-submissions-part-1/ https://umaar.com/blog/my-code-exercise-submissions-part-1/ - it's all about outputting keypad directions such as "right, right, ⏎" based on the desired input.
jeffbee 6y ago
It might not be obvious but these kinds of questions are terrible for diversity and inclusion because they incorporate too much cultural knowledge that is not universal. A person who has never seen chess will spend more of the interview just trying to figure out what is meant by the Knight's move. That disadvantages people from low-chess cultures, no matter how qualified and intelligent they may be. Chess also has a class aspect, so you are biasing against class background as well. This is the same reason why they had to stop writing SAT questions that started out "Tad and Buffy are at duece in the fifth set of their tennis match ...".
- blahyawnblah 6y ago
  I doesn't take long to understand how a knight moves, though. Move two squares in a direction and then move one square perpendicular to that.
  - notsuoh 6y ago
    Not hard, but still disadvantageous to people who haven't seen it before as that's one more thing they have to learn and keep in mind during a stressful interview.
  - bowmessage 6y ago
    Sorry, what is a square? I come from a society that exclusively uses a polar coordinate system and have no such concept of your cartesian-biased constructs. (/s)
    - deleted 6y ago
      [deleted]
    - jeffbee 6y ago
      Well, what is a square in this context? Does a phone dialer have "squares"? If you explain it that way it's nonsensical because there are squares on a chess board and there are not squares on many phone keypads. Those of you who are trying to turn the flaw of this question into a joke are perfectly demonstrating two things: hiring practices in our industry are a joke to many of the people conducting interviews, and your thinking is so weak that you are unable to unambiguously explain this question without resorting to the chess analogy.
mym1990 6y ago
Is it just me or is it somewhat pointless to be lamenting the fact that this may or may not be a terrible part of the hiring process? At the end of the day if you sit down for the interview and are given this question, you can either do your best to solve it or walk out of the interview and go to a company that you feel is 'more worth your time'. When you're playing by Google's rules, there's not much to be accomplished in the form of complaining. My guess is that many hiring practices will change(and are changing) over time based on the internal work that people are doing to drive better initiatives, and less based on comments on HN. Personally, I would like to see what people thing about the actual solution to this particular problem...
- xienze 6y ago
  > you can either do your best to solve it or walk out of the interview and go to a company that you feel is 'more worth your time'. The problem is so many other companies have copied this practice because hey, Google asks brainteasers and gets the best candidates, so we should do it too!
  - mym1990 6y ago
    They have, but we're definitely seeing a turn towards a better direction recently. The software engineering job market has gone through some incredibly fast changes in only the last 10-15 years, and we will likely never perfect the process as the landscape changes, but I guess the optimist in me believes that at least some companies are doing their best. Its just my view that when the first 10 comments on this post echo that this is a terrible practice, it makes it difficult to have a more technical conversation about the OP.
- UncleMeat 6y ago
  It isn't pointless. Criticizing leetcode style interviews produces an infinite supply of social media comments and upvotes. The conversation will never progress, but it lets people argue on the internet, which is a key value proposition of headlines today.
- itronitron 6y ago
murgindrag 6y ago
So here's the thing. And I know I'll get knocked to r/iamverysmart for this. It timed myself. It took less than 10 minutes from reading the problem to coding up a working dynamic programming solution (no peaking at the rest of the article). A big chunk of that was (unsuccessfully) trying to come up with a closed-form solution. I didn't get the log(n) solution until I found it existed at the bottom, but once the author mentioned it's existence, that took less than 5 minutes to figure out. I didn't code that up, though. I'm probably an above-average programmer, but I'm not a 99.99% outlier. I interviewed early Google. The questions were tough for me (much more so than this one). Things which jumped out at me: "The better the candidate, the fewer hints I tend to have to give, but I have yet to see a candidate who required no input from me at all." I read this as "We're scraping the bottom of the barrel for candidates. Our candidates are nothing like those who applied to Google circa 2000" And: "I didn’t even know it existed until one of my colleagues came back to his desk with a shocked look on his face and announced he had just interviewed the best candidate he’d ever seen." I read this as: "Our employees are dumb. In using this interview question for years, none of us ever noticed the obvious." What's going on there? I mean I can see messing up an interview question like this under the stress of an interview (I literally confused linked lists and arrays in probably my worst interview ever). But no candidate? Ever? And no employee? Come on. There's something deeply wrong at Google. It's been deeply wrong for a few years. I hope someone fixes it.
- chromatin 6y ago
  Likewise I was surprised at how trivial this seemed? My first solution was matrix multiplication -- I remember distinctly in undergraduate discrete mathematics learning that matrix exponentiation solved the hops-on-graph problem. I did not think to convert to binary to make logarithmic time, however.
  - murgindrag 6y ago
    The "convert to binary" is a standard algorithm for modular exponentiation. Anyone who has taken a cryptography course will know it. It's not the fastest algorithm (by big-O; probably is in practice), though. You can do a matrix decomposition, exponentiate the eigenvalues, and convert back. Speed will depend on how you do the exponentiation, and that's gets into a pile of optimized numerical methods.
zinclozenge 6y ago
For anybody wondering, this is a disguised 'count number of walks of length k on a graph' problem. On a more general note, anytime a problem admits a dynamic programming solution, there almost always is a graph based approach.
- tyrust 6y ago
  >On a more general note, anytime a problem admits a dynamic programming solution, there almost always is a graph based approach. This concept was introduced to me back in my algorithms class and is pretty useful. For anyone looking for a longer explanation, page 167 of the textbook [0] has the nugget and some examples: >Every dynamic program has an underlying dag (directed acyclic graph) structure: think of each node as representing a subproblem, and each edge as a precedence constraint on the order in which the subproblems can be tackled. [0] - PDF: http://algorithmics.lsi.upc.edu/docs/Dasgupta-Papadimitriou-Vazirani.pdf http://algorithmics.lsi.upc.edu/docs/Dasgupta-Papadimitriou-...
- avinassh 6y ago
  > On a more general note, anytime a problem admits a dynamic programming solution, there almost always is a graph based approach. Whoa, this is something new for me. For e.g. how would you transform calculating nth fibonacci number into a graph problem?
  - anandoza 6y ago
    Draw a graph with vertices labeled 0 through N, then add edges i->(i+1) and i->(i+2). The answer is the number of paths from 0 to N. This is still pretty specific to counting paths in the same way the original knight problem is, though. The other comment is talking about how you represent each state for the recursive function as a vertex, then connect it to its dependencies (basically taking the recursion tree, but merging identical calls).
    - deleted 6y ago
      [deleted]
  - 6y ago
jtchang 6y ago
Random question but why is it called memoization instead of just caching? Isn't it the same thing? For some reason I never ran across the word memoization when I was doing CS a number of years ago.
- shajznnckfke 6y ago
  The term is over 50 years old: https://en.m.wikipedia.org/wiki/Memoization#Etymology https://en.m.wikipedia.org/wiki/Memoization#Etymology Probably been used in CS longer than “caching”.
  - AnimalMuppet 6y ago
    If you include hardware in CS, no, caching is older. If you don't, I'm not sure.
- phendrenad2 6y ago
  CS is full of needless jargon and buzzwords, which only serve to make the field seem more impressive to outsiders.
- username90 6y ago
  Memoization is only when you cache the results of a referentially transparent function in software, caching is more general. You have cpu caches, browser bashes, even entire servers can be caches of common web requests etc. So using the word "memoization" is more specific and leads to less confusion.
- chimtim 6y ago
  caching a computation result is called memoization.
dmurray 6y ago
I was surprised none of the solutions exploited the symmetry of the graph. There are 4 sets of numbers you can be on in a path of length 2+, and it only matters which set you are in: {0}, {1, 3, 7, 9}, {2, 8} and {4, 6}. 5 should be special cased since only paths of length 1 are possible. That doesn't give you a big-O speedup, but it should be a 2x performance improvement for the algorithm that is linear in the number of hops.
egsmi 6y ago
Nice variant of the Knight Tour. The 0 makes the board shape a bit odd and therefore interesting. https://en.m.wikipedia.org/wiki/Knight%27s_tour https://en.m.wikipedia.org/wiki/Knight%27s_tour
sjg007 6y ago
Algorithm questions are the tech version of word problems. What they tell you is how good someone is at solving these types of problems. Solve a lot of these problems if you want to work at Google.
- colinmhayes 6y ago
  The point of these problems is to find out how committed an applicant is. If you can ace them the interviewer knows that you have enough critical thinking skills to succeed and enough commitment skills to learn whatever you need.
sethammons 6y ago
This problem was used at my work years ago. We now have a hiring guild dedicated to making a better interview process. Multiple people said they were originally in the guild to prevent this problem from being used haha.
- tupputuppu 6y ago
  It really makes you wonder whether puzzles like this are a valid measure for real life performance at Google. Probably not.
  - dekhn 6y ago
    They are not (except for a very limited number of developers working on very specific things).
lostmsu 6y ago
I would stop at "level 3" in this blog post intentionally. Writing an unrolled dynamic solution as opposed to a simple cache is an extremely error-prone mental gymnastics in my experience. The initialization procedure and indexing are especially susceptible. Moreover, the resulting code is usually barely readable. I wish people would stop expecting it. In practice, the memoization approach is sufficient in 99% cases, and having a 3% chance to make an error in unroll code that causes user data to be misplaced is a much worse option.
techie128 6y ago
Unpopular opinion here: These type of questions are horrible at filtering out bad software engineers. Employers should be focusing on principles of software engineering rather than random math problems. Most new grad will write code like they were solving leetcode problems. It is sad that we need to teach them standard tools, protocols, concurrency, software engineering practices right out of college.
deleted 6y ago
[deleted]
guenthert 6y ago
I got a more general comment / question regarding this form of interview. Is this some kind of hidden age discrimination? Now I just might not be the target audience for those interviews or exactly one of those they mean to filter out, but after more than two decades of experience in the field (in various roles, but my first paid job as programmer was in '92) I feel uncomfortable with the kind of brain teasers I find on leetfree.org. Some are outright silly (e.g. "wiggle-sort"), some might be valid in some niche, but hardly common place (e.g. sparse matrix multiplication -- I haven't ever had the need to multiply matrices since leaving the University, but I haven't done any 3D graphics or robot control since then either). If the companies which employ such interviews are aware of the distance of those puzzles to the day-to-day labor of a software engineer, then I suppose it's OK. But seeing that the interviewer himself was direct hire from University with no outside professional experience makes me wonder whether they are creating their own ivory tower. In case of Google this seems to work out for them (they decidedly wanted to make things different than then already established enterprises and having seen those, I say more power to them), but will it for others?
- stmw 6y ago
  There is probably some of that, no process is perfect... If nothing else, at least it's more objective than a more bias-prone personality fit approach. But it's also possible to practice - even 20+ years after University - if one wants to interview at Google or another company that uses those kinds of interviews. Reading a few blogs like this and some live interviews on a site like interviewing.io or some such will put you back to graph walks or sparse matrix multiplication in no time.

98 points by thanato0s 6y ago

Counting the number of paths when you have loops is easiest using a connection matrix and matrix exponentiation. Then you get log(n) time.

deleted 6y ago
[deleted]
defen 6y ago
I think this hits on why these types of problems are potentially bad. You could be the world's worst software engineer, but if you'd taken a graph theory course recently, you'd pattern match this, say "sure, can I use Matlab?" and be done in under 10 minutes. Or you could have tons of experience deploying robust production systems but have never happened to learn / need to use dynamic programming, in which case coming up with it in 45 minutes during an interview is not going to happen.
- username90 6y ago
  The junior and the senior aren't competing for the same job though, this just checks that you still remember the theory you learned in college. And no, just because you are senior doesn't mean that you get a free pass forgetting everything you learned in college. I haven't practiced problems like this in over 5 years and I still ace them.
  - noitpmeder 6y ago
    /r/iamverysmart/
    - username90 6y ago
      What is your point? Companies wants to hire smart people which is why they have these interviews. This applies no matter what level people are at. "I forgot" isn't valid defense. All the people in these threads who says things like "I knew this but forgot" are really cringy.
      - Judgmentality 6y ago
        /r/woosh
        username90 6y ago
        Do you think this is a good way to discuss things at HN?
        Judgmentality 6y ago
        I believe that HN needs more humor, not less - so yes.
      - noarchy 6y ago
        The point may be that many (if they're truly senior, not someone with 3-5 years in the industry) will not have used these theories in 10+ years. The real-world application is questionable.
        username90 6y ago
        And my point is that I'd rather hire someone who didn't forget these things. When you learn something well you don't forget, it is like riding a bike. If you learned how to ride a bike 10 yards and then stopped and never did it again then you would forget how to do it, saying "I passed the bike riding test when I was 10, I don't need to do it again" isn't a good defense. I mean, why did you even go to college if you intended to just forget everything afterwards instead of learning the things properly for life? I'd rather not hire people who just do the work necessary to pass and get the degree and don't want to learn more.
  - defen 6y ago
    > this just checks that you still remember the theory you learned in college. Sure, but not everyone went to college or studied computer science / math. This seems like one of those problems that's really just testing a very specific type of preexisting knowledge.
    - username90 6y ago
      You'll get full score even if you don't know the matrix solution, just doing a memoized recursive one is enough. However if you had that specific knowledge then they still test whether they have the skills to apply esoteric knowledge correctly which is also very valuable. Anyway, Google no longer has this question. Once it gets known outside Google bans it from interviews. Sometimes people give banned questions but in general they don't and it is taken into account. I remember it being popular as a question 4 years ago, popular questions tend to leak quickly and get banned though.
      - Gunax 6y ago
        According to the blog post, the interviewers weren't even aware of the matrix solution until one candidate brought it up.
        KnobbleMcKnees 6y ago
        I assume they all immediately handed in their letters of resignation and/or hired the candidate in as a principle engineer. Sarcasm aside, the very fact that they ban questions demonstrates how useless these types of questions really are. If you ban it because people might know it due to its popularity then what are you testing for? I thought it was for whether a candidate could solve the problem, but it appears to be to check which percentile of a special 'knowledge' club they belong to...
    - bakuninsbart 6y ago
      If you are an experienced programmer, how long does it take you to learn the handful or so algs/concepts you need for these kinds of problems? It'd probably 20-30 hours of learning, which is a reasonable expectation to ace interviews. - And it is not like you have to necessarily come up with a solution all by yourself, communicating your issues well, and the interviewer will probably help you, if you have an otherwise impressive résume it shouldn't pose a problem at all.
- nitwit005 6y ago
  I wouldn't be surprised if people occasionally re-create famous math problems, given how many interview questions seem to get created these days.
- kevincox 6y ago
  If someone just pattern matched it I would give them a backup question. The point of these questions isn't seeing if they can solve it, it is seeing how they think about problems. I'm also not worried if they make a good solution, or even get a solution at all. But almost all candidates can start making progress, come up with some possible solutions and tell me about those solutions.
Jabbles 6y ago
That is covered in the next blogpost: https://alexgolec.dev/knights-dialer-logarithmic-time-edition/ https://alexgolec.dev/knights-dialer-logarithmic-time-editio...
joshbuckler 6y ago
If you then diagonalize that connection matrix, you can get constant time (though you might have to make a special case for starting at the `5` key): "Diagonalization can be used to efficiently compute the powers of a matrix..." [1] [1] https://en.wikipedia.org/wiki/Diagonalizable_matrix#Application_to_matrix_functions https://en.wikipedia.org/wiki/Diagonalizable_matrix#Applicat...
- username90 6y ago
  Diagonalizing the matrix makes it easier to calculate the exponent by making it a series of numeric exponentials, but calculating the exponent of a number is still a log(n) operation. Also given that this is a discrete problem moving to floating points like you'd likely have to do when you diagonalize could easily lead to errors in the final answer.
- twiceaday 6y ago
  I tried but Wolfram Alpha doesn't take inputs that long hah. In any case even if it works you will likely get irrational terms which will make it only theoretically nice but not practically computable, like the closed-form Fibonacci formula.

warmfuzzykitten 6y ago

Typical brain-teaser interview question that will have absolutely no correlation to on-the-job performance but makes the interviewer feel really smart. I thought Google had gotten away from these.

joshuamorton 6y ago
This isn't a brainteaser. It's a programming problem. Brainteasers are like "how many ping pong balls fit in a 747" or "you wake up an inch tall in a blender, the blades start spinning in a minute. How do you survive."
- throwaways885 6y ago
  > how many ping pong balls fit in a 747 This one does seem useful. Being able to do back-of-the-napkin (i.e. fermi problem) calculations is a pretty good skill.
  - watwut 6y ago
    Back of napkin that requires you to know what 747 is wrong be correlated with anything programming related.
  - crocal 6y ago
    Actually a typical GMAT question...
  - toast0 6y ago
    It might be an OK problem if the interviewee is familiar with 747s and ping pong balls, and will be interacting with physical objects as part of their job. I have a terrible time with physical measurments and area and space, but thankfully it's not relevant to my work.
  - CydeWeys 6y ago
    Google does still use questions like this, it's just that they're relevant to programming/system design. So a question might be "How many servers are needed to run Gmail?" The reason the 747 question is bad is because it has little to do with programming and a lot to do with how much you happen to know about planes and ping pong balls and how to estimate volumes of irregularly shaped objects, none of which have much if any correlation with programming ability.

mcqueenjordan 6y ago

This is a fun problem, but it's a terrible interview question for trying to hire software engineers.

kevincox 6y ago
Why? Note that the point of the problem isn't if you can solve it. It is how you approach it. A problem like this gives you a lot of signal. * Can the person program at all. * Do they consider the performance of possible solutions. * Are they good at explaining their thought process. * Do they consider edge cases? * Do they write tests? I'm not saying that it should be the only interview, or it is the most important. But it clearly provides differentiation between candidates. I'm also not saying it is the perfect way to get this differentiation, but I think it is far from "terrible".
- xienze 6y ago
  > * Can the person program at all. * Do they consider the performance of possible solutions. * Are they good at explaining their thought process. * Do they consider edge cases? * Do they write tests? All good things to look for. The problem is, day-to-day you don't have to do all of those things in 45 minutes while several people at the table watch you. Personally I'm a fan of a short programming exercise (perhaps even this problem) that you can take home and walk through with the team at a later time. I know those are detested by some, but I think they're fair (assuming the task is not something outrageous; something that can be knocked out in an evening perhaps) and give a much better idea of what an employee is capable of.
- vanusa 6y ago
  Can the person program at all. Do they consider the performance of possible solutions. * Are they good at explaining their thought process. * Do they consider edge cases? * Do they write tests?* That's what you'd like to think it's testing for. In reality, it's testing for: "Here's a hoop - would you like to jump through it for me please? BTW not only will stumbling or even hesitating pretty much disqualify you - we love to dish after hours about those who fail to make the cut."
6y ago

deleted 6y ago

[deleted]

dudus 6y ago

At the end he hints at a better solution. Now I'm intrigued.

chromatin 6y ago
It's in a follow-on article (or just think back to your undergraduate discrete mathematics or graph theory courses)
deleted 6y ago
[deleted]

umaar 6y ago

On the subject of Google Interview challenges and keypads, I wrote about a Google keypad challenge here: https://umaar.com/blog/my-code-exercise-submissions-part-1/ https://umaar.com/blog/my-code-exercise-submissions-part-1/ - it's all about outputting keypad directions such as "right, right, ⏎" based on the desired input.

jeffbee 6y ago

It might not be obvious but these kinds of questions are terrible for diversity and inclusion because they incorporate too much cultural knowledge that is not universal. A person who has never seen chess will spend more of the interview just trying to figure out what is meant by the Knight's move. That disadvantages people from low-chess cultures, no matter how qualified and intelligent they may be. Chess also has a class aspect, so you are biasing against class background as well. This is the same reason why they had to stop writing SAT questions that started out "Tad and Buffy are at duece in the fifth set of their tennis match ...".

blahyawnblah 6y ago
I doesn't take long to understand how a knight moves, though. Move two squares in a direction and then move one square perpendicular to that.
- notsuoh 6y ago
  Not hard, but still disadvantageous to people who haven't seen it before as that's one more thing they have to learn and keep in mind during a stressful interview.
- bowmessage 6y ago
  Sorry, what is a square? I come from a society that exclusively uses a polar coordinate system and have no such concept of your cartesian-biased constructs. (/s)
  - deleted 6y ago
    [deleted]
  - jeffbee 6y ago
    Well, what is a square in this context? Does a phone dialer have "squares"? If you explain it that way it's nonsensical because there are squares on a chess board and there are not squares on many phone keypads. Those of you who are trying to turn the flaw of this question into a joke are perfectly demonstrating two things: hiring practices in our industry are a joke to many of the people conducting interviews, and your thinking is so weak that you are unable to unambiguously explain this question without resorting to the chess analogy.

mym1990 6y ago

Is it just me or is it somewhat pointless to be lamenting the fact that this may or may not be a terrible part of the hiring process? At the end of the day if you sit down for the interview and are given this question, you can either do your best to solve it or walk out of the interview and go to a company that you feel is 'more worth your time'. When you're playing by Google's rules, there's not much to be accomplished in the form of complaining. My guess is that many hiring practices will change(and are changing) over time based on the internal work that people are doing to drive better initiatives, and less based on comments on HN. Personally, I would like to see what people thing about the actual solution to this particular problem...

xienze 6y ago
> you can either do your best to solve it or walk out of the interview and go to a company that you feel is 'more worth your time'. The problem is so many other companies have copied this practice because hey, Google asks brainteasers and gets the best candidates, so we should do it too!
- mym1990 6y ago
  They have, but we're definitely seeing a turn towards a better direction recently. The software engineering job market has gone through some incredibly fast changes in only the last 10-15 years, and we will likely never perfect the process as the landscape changes, but I guess the optimist in me believes that at least some companies are doing their best. Its just my view that when the first 10 comments on this post echo that this is a terrible practice, it makes it difficult to have a more technical conversation about the OP.
UncleMeat 6y ago
It isn't pointless. Criticizing leetcode style interviews produces an infinite supply of social media comments and upvotes. The conversation will never progress, but it lets people argue on the internet, which is a key value proposition of headlines today.
itronitron 6y ago

murgindrag 6y ago

So here's the thing. And I know I'll get knocked to r/iamverysmart for this. It timed myself. It took less than 10 minutes from reading the problem to coding up a working dynamic programming solution (no peaking at the rest of the article). A big chunk of that was (unsuccessfully) trying to come up with a closed-form solution. I didn't get the log(n) solution until I found it existed at the bottom, but once the author mentioned it's existence, that took less than 5 minutes to figure out. I didn't code that up, though. I'm probably an above-average programmer, but I'm not a 99.99% outlier. I interviewed early Google. The questions were tough for me (much more so than this one). Things which jumped out at me: "The better the candidate, the fewer hints I tend to have to give, but I have yet to see a candidate who required no input from me at all." I read this as "We're scraping the bottom of the barrel for candidates. Our candidates are nothing like those who applied to Google circa 2000" And: "I didn’t even know it existed until one of my colleagues came back to his desk with a shocked look on his face and announced he had just interviewed the best candidate he’d ever seen." I read this as: "Our employees are dumb. In using this interview question for years, none of us ever noticed the obvious." What's going on there? I mean I can see messing up an interview question like this under the stress of an interview (I literally confused linked lists and arrays in probably my worst interview ever). But no candidate? Ever? And no employee? Come on. There's something deeply wrong at Google. It's been deeply wrong for a few years. I hope someone fixes it.

chromatin 6y ago
Likewise I was surprised at how trivial this seemed? My first solution was matrix multiplication -- I remember distinctly in undergraduate discrete mathematics learning that matrix exponentiation solved the hops-on-graph problem. I did not think to convert to binary to make logarithmic time, however.
- murgindrag 6y ago
  The "convert to binary" is a standard algorithm for modular exponentiation. Anyone who has taken a cryptography course will know it. It's not the fastest algorithm (by big-O; probably is in practice), though. You can do a matrix decomposition, exponentiate the eigenvalues, and convert back. Speed will depend on how you do the exponentiation, and that's gets into a pile of optimized numerical methods.

zinclozenge 6y ago

For anybody wondering, this is a disguised 'count number of walks of length k on a graph' problem. On a more general note, anytime a problem admits a dynamic programming solution, there almost always is a graph based approach.

tyrust 6y ago
>On a more general note, anytime a problem admits a dynamic programming solution, there almost always is a graph based approach. This concept was introduced to me back in my algorithms class and is pretty useful. For anyone looking for a longer explanation, page 167 of the textbook [0] has the nugget and some examples: >Every dynamic program has an underlying dag (directed acyclic graph) structure: think of each node as representing a subproblem, and each edge as a precedence constraint on the order in which the subproblems can be tackled. [0] - PDF: http://algorithmics.lsi.upc.edu/docs/Dasgupta-Papadimitriou-Vazirani.pdf http://algorithmics.lsi.upc.edu/docs/Dasgupta-Papadimitriou-...
avinassh 6y ago
> On a more general note, anytime a problem admits a dynamic programming solution, there almost always is a graph based approach. Whoa, this is something new for me. For e.g. how would you transform calculating nth fibonacci number into a graph problem?
- anandoza 6y ago
  Draw a graph with vertices labeled 0 through N, then add edges i->(i+1) and i->(i+2). The answer is the number of paths from 0 to N. This is still pretty specific to counting paths in the same way the original knight problem is, though. The other comment is talking about how you represent each state for the recursive function as a vertex, then connect it to its dependencies (basically taking the recursion tree, but merging identical calls).
  - deleted 6y ago
    [deleted]
- 6y ago

jtchang 6y ago

Random question but why is it called memoization instead of just caching? Isn't it the same thing? For some reason I never ran across the word memoization when I was doing CS a number of years ago.

shajznnckfke 6y ago
The term is over 50 years old: https://en.m.wikipedia.org/wiki/Memoization#Etymology https://en.m.wikipedia.org/wiki/Memoization#Etymology Probably been used in CS longer than “caching”.
- AnimalMuppet 6y ago
  If you include hardware in CS, no, caching is older. If you don't, I'm not sure.
phendrenad2 6y ago
CS is full of needless jargon and buzzwords, which only serve to make the field seem more impressive to outsiders.
username90 6y ago
Memoization is only when you cache the results of a referentially transparent function in software, caching is more general. You have cpu caches, browser bashes, even entire servers can be caches of common web requests etc. So using the word "memoization" is more specific and leads to less confusion.
chimtim 6y ago
caching a computation result is called memoization.

dmurray 6y ago

I was surprised none of the solutions exploited the symmetry of the graph. There are 4 sets of numbers you can be on in a path of length 2+, and it only matters which set you are in: {0}, {1, 3, 7, 9}, {2, 8} and {4, 6}. 5 should be special cased since only paths of length 1 are possible. That doesn't give you a big-O speedup, but it should be a 2x performance improvement for the algorithm that is linear in the number of hops.

egsmi 6y ago

Nice variant of the Knight Tour. The 0 makes the board shape a bit odd and therefore interesting. https://en.m.wikipedia.org/wiki/Knight%27s_tour https://en.m.wikipedia.org/wiki/Knight%27s_tour

sjg007 6y ago

Algorithm questions are the tech version of word problems. What they tell you is how good someone is at solving these types of problems. Solve a lot of these problems if you want to work at Google.

colinmhayes 6y ago
The point of these problems is to find out how committed an applicant is. If you can ace them the interviewer knows that you have enough critical thinking skills to succeed and enough commitment skills to learn whatever you need.

sethammons 6y ago

This problem was used at my work years ago. We now have a hiring guild dedicated to making a better interview process. Multiple people said they were originally in the guild to prevent this problem from being used haha.

tupputuppu 6y ago
It really makes you wonder whether puzzles like this are a valid measure for real life performance at Google. Probably not.
- dekhn 6y ago
  They are not (except for a very limited number of developers working on very specific things).

lostmsu 6y ago

I would stop at "level 3" in this blog post intentionally. Writing an unrolled dynamic solution as opposed to a simple cache is an extremely error-prone mental gymnastics in my experience. The initialization procedure and indexing are especially susceptible. Moreover, the resulting code is usually barely readable. I wish people would stop expecting it. In practice, the memoization approach is sufficient in 99% cases, and having a 3% chance to make an error in unroll code that causes user data to be misplaced is a much worse option.

techie128 6y ago

Unpopular opinion here: These type of questions are horrible at filtering out bad software engineers. Employers should be focusing on principles of software engineering rather than random math problems. Most new grad will write code like they were solving leetcode problems. It is sad that we need to teach them standard tools, protocols, concurrency, software engineering practices right out of college.

deleted 6y ago

[deleted]

guenthert 6y ago

I got a more general comment / question regarding this form of interview. Is this some kind of hidden age discrimination? Now I just might not be the target audience for those interviews or exactly one of those they mean to filter out, but after more than two decades of experience in the field (in various roles, but my first paid job as programmer was in '92) I feel uncomfortable with the kind of brain teasers I find on leetfree.org. Some are outright silly (e.g. "wiggle-sort"), some might be valid in some niche, but hardly common place (e.g. sparse matrix multiplication -- I haven't ever had the need to multiply matrices since leaving the University, but I haven't done any 3D graphics or robot control since then either). If the companies which employ such interviews are aware of the distance of those puzzles to the day-to-day labor of a software engineer, then I suppose it's OK. But seeing that the interviewer himself was direct hire from University with no outside professional experience makes me wonder whether they are creating their own ivory tower. In case of Google this seems to work out for them (they decidedly wanted to make things different than then already established enterprises and having seen those, I say more power to them), but will it for others?

stmw 6y ago
There is probably some of that, no process is perfect... If nothing else, at least it's more objective than a more bias-prone personality fit approach. But it's also possible to practice - even 20+ years after University - if one wants to interview at Google or another company that uses those kinds of interviews. Reading a few blogs like this and some live interviews on a site like interviewing.io or some such will put you back to graph walks or sparse matrix multiplication in no time.