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...
When you're playing by Google's rules, there's not much to be accomplished in the form of complaining.
The problem that so by now many companies have been infected with the idea of using "Google's rules" as a playbook that it's still going to take several years for the contagion to wash out of the system.
Meaning we need to keep pushing back on multiple fronts. Given the insidiousness of the problem (and the psychological cost it has imposed on a generation of engineers; not to mention the sheer time cost) -- public exposure, followed by heaping mounds of ridicule (you can call that "complaining" if you like) would seem to be not only a valid, but unfortunately necessary part of our suppression strategy.
Otherwise, the people who keep foisting these questions us (as if they were a cool and nifty way to size up candidates) -- just aren't going to get it through their heads.
Personally, I would like to see what people thing about the actual solution to this particular problem...
I used to enjoy solving problems like these, during my high school and college years. Sometimes really, really enjoy it.
But now that I build real systems for a living (which generally involves much meatier problems to solve) -- and it's become part of the standard hazing process in far too many shops, for far too long -- I couldn't begin to care less.
One of the problems I have with these types of questions where the interviewer is going to 'help guide' the candidate is that there is way too much opportunity for the interviewer to stall the candidate, either intentionally or not, based on their own bias toward the candidate.
At the most extreme, these questions are a test for whether the candidate had the same CS professors as the interviewer.
> 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!
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.
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.
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.
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.
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.
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".
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.
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]
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.
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.
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.
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?
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.
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/ - it's all about outputting keypad directions such as "right, right, ⏎" based on the desired input.
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.
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.
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.
This isn't a brain teaser, they actually correlate with on-the-job performance. When I worked at Google I looked up their internal reports on the subject and they showed that the score people got on these algorithm interviews correlated pretty well with their performance ratings after they got hired. In other words the group of people who got hired even though they had low scores performed significantly worse than the people who got hired with excellent scores.
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."
While I get this sentiment, and agree with it, I would like to also point out that there are almost no clear cut and dry problems in the real world. One needs to be able to know how to ask questions in order to get a good enough grasp to begin formulating some kind of solution.
When you are taking an SAT question, there is no opportunity to ask 'can you tell me how tennis is scored?' That is not the case in some/most interviews.
I have a worse example of this -- I've seen a programming question going around that involves tournament brackets (specifically how they're seeded). I'm not particularly into sports, but if you were, you would have a huge leg up on this problem because you'd already have an intuitive sense of how brackets work and are constructed, that I wouldn't.
Given how primitive and easy to understand the movement constraints in this particular case are, this seems like an unnecessary concern. Note that I am not dismissing the rest of your post.
> 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.
I mean he explicitly spells it out as part of the problem. I highly doubt in an interview they'll just plop down a term like "knight's move" and refuse to clarify what is meant by it, if necessary. It's not exactly the sort of thing that takes living a life of privilege to understand.
[+] [-] mym1990|5 years ago|reply
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...
[+] [-] vanusa|5 years ago|reply
The problem that so by now many companies have been infected with the idea of using "Google's rules" as a playbook that it's still going to take several years for the contagion to wash out of the system.
Meaning we need to keep pushing back on multiple fronts. Given the insidiousness of the problem (and the psychological cost it has imposed on a generation of engineers; not to mention the sheer time cost) -- public exposure, followed by heaping mounds of ridicule (you can call that "complaining" if you like) would seem to be not only a valid, but unfortunately necessary part of our suppression strategy.
Otherwise, the people who keep foisting these questions us (as if they were a cool and nifty way to size up candidates) -- just aren't going to get it through their heads.
Personally, I would like to see what people thing about the actual solution to this particular problem...
I used to enjoy solving problems like these, during my high school and college years. Sometimes really, really enjoy it.
But now that I build real systems for a living (which generally involves much meatier problems to solve) -- and it's become part of the standard hazing process in far too many shops, for far too long -- I couldn't begin to care less.
[+] [-] itronitron|5 years ago|reply
At the most extreme, these questions are a test for whether the candidate had the same CS professors as the interviewer.
[+] [-] xienze|5 years ago|reply
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!
[+] [-] UncleMeat|5 years ago|reply
[+] [-] zinclozenge|5 years ago|reply
On a more general note, anytime a problem admits a dynamic programming solution, there almost always is a graph based approach.
[+] [-] sethammons|5 years ago|reply
[+] [-] tupputuppu|5 years ago|reply
[+] [-] jtchang|5 years ago|reply
[+] [-] username90|5 years ago|reply
[+] [-] shajznnckfke|5 years ago|reply
Probably been used in CS longer than “caching”.
[+] [-] chimtim|5 years ago|reply
[+] [-] phendrenad2|5 years ago|reply
[+] [-] dmurray|5 years ago|reply
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.
[+] [-] mcqueenjordan|5 years ago|reply
[+] [-] kevincox|5 years ago|reply
* 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".
[+] [-] username90|5 years ago|reply
[+] [-] defen|5 years ago|reply
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.
[+] [-] Jabbles|5 years ago|reply
[+] [-] joshbuckler|5 years ago|reply
[1] https://en.wikipedia.org/wiki/Diagonalizable_matrix#Applicat...
[+] [-] unknown|5 years ago|reply
[deleted]
[+] [-] sjg007|5 years ago|reply
[+] [-] colinmhayes|5 years ago|reply
[+] [-] lostmsu|5 years ago|reply
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.
[+] [-] guenthert|5 years ago|reply
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|5 years ago|reply
[+] [-] unknown|5 years ago|reply
[deleted]
[+] [-] umaar|5 years ago|reply
[+] [-] techie128|5 years ago|reply
[+] [-] murgindrag|5 years ago|reply
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.
[+] [-] egsmi|5 years ago|reply
https://en.m.wikipedia.org/wiki/Knight%27s_tour
[+] [-] warmfuzzykitten|5 years ago|reply
[+] [-] username90|5 years ago|reply
Edit: This applies for senior engineers as well.
[+] [-] 2OEH8eoCRo0|5 years ago|reply
[+] [-] joshuamorton|5 years ago|reply
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."
[+] [-] egsmi|5 years ago|reply
How do you know? Maybe the interview was for a position on the AplhaZero team.
[+] [-] zeroxfe|5 years ago|reply
[+] [-] dudus|5 years ago|reply
[+] [-] unknown|5 years ago|reply
[deleted]
[+] [-] chromatin|5 years ago|reply
[+] [-] jeffbee|5 years ago|reply
[deleted]
[+] [-] blahyawnblah|5 years ago|reply
[+] [-] mym1990|5 years ago|reply
When you are taking an SAT question, there is no opportunity to ask 'can you tell me how tennis is scored?' That is not the case in some/most interviews.
[+] [-] CydeWeys|5 years ago|reply
[+] [-] pb7|5 years ago|reply
Edit: Typo, as opposed to the well known capital L-shape that is just one unit wide.
[+] [-] chromatin|5 years ago|reply
[+] [-] xienze|5 years ago|reply
I mean he explicitly spells it out as part of the problem. I highly doubt in an interview they'll just plop down a term like "knight's move" and refuse to clarify what is meant by it, if necessary. It's not exactly the sort of thing that takes living a life of privilege to understand.
[+] [-] unknown|5 years ago|reply
[deleted]