[deleted]
Google Interview Questions Deconstructed: The Knight’s Dialer
111–120 of 134 posts
Re: Google Interview Questions Deconstructed: The Knight’s Dialer
#112Earlier quoted context omitted.
Yeah. I'm aware of that. It's a bunch of straightforward questions, a pretty high bar for how many you need to answer, and so it's pretty random how many of them you mess up, so it's kind of like a die roll to get a job. I had a really bad interview at a peer company once, and I'm well aware how it goes. But I kind of miss the old Google where you DID need to be a genius. I interviewed with Google probably around the…
> But I kind of miss the old Google where you DID need to be a genius. I interviewed with Google probably around the year 2000, and there was a genuinely hard ball packing problem. I'm kind of curious what happened. Anyone who could answer that question would find this one trivial -- and not just the dynamic programming solution, but the O(log n) one which apparently no one at Google (or even applying to Google) noti…
Early Google was incredibly arrogant and aggressive around only hiring people they thought were brilliant. The model was small teams of super-elite people. They took some flack for hiring for high caliber people into even relatively menial positions (e.g. random office admins). Even for things like the cafeteria, they wanted a world-class chef.
On the whole, it actually worked very well. Everyone wanted to work there because you were surrounded by top people.
Re: Google Interview Questions Deconstructed: The Knight’s Dialer
#113Earlier quoted context omitted.
> 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.
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 i…
According to the blog post, the interviewers weren't even aware of the matrix solution until one candidate brought it up.
Re: Google Interview Questions Deconstructed: The Knight’s Dialer
#114For 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.
> 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?
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).
Re: Google Interview Questions Deconstructed: The Knight’s Dialer
#115Earlier quoted context omitted.
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.
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…
I'd say it shows that for most day-to-day work in the software industry, a certain percentage of the CS material we learn is simply unnecessary. No one has ever asked me to re-implement well-known algorithms that are found in well-established libraries. There are, of course, people who do this, and they do need such a background. But they are likely outliers.
Re: Google Interview Questions Deconstructed: The Knight’s Dialer
#116So 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 autho…
Note that you need to pass at least 4 out of 5 interviews, each asking about 2 questions. But yeah, you don't have to be a genius to get into Google nowadays. What you need is the creativity to solve problems you haven't seen before (which is why Google bans questions once they get out), basic algorithms skills and the programming skills to implement it at a reasonable pace.
> each asking about 2 questions
Google does not usually ask 2 questions. You may/should get harder follow-ups to the original question, which is a good sign.
Re: Google Interview Questions Deconstructed: The Knight’s Dialer
#117Random 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.
caching a computation result is called memoization.
Re: Google Interview Questions Deconstructed: The Knight’s Dialer
#118Earlier quoted context omitted.
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 i…
According to the blog post, the interviewers weren't even aware of the matrix solution until one candidate brought it up.
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...
Re: Google Interview Questions Deconstructed: The Knight’s Dialer
#119Is 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 accomplis…
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.
Re: Google Interview Questions Deconstructed: The Knight’s Dialer
#120This is a fun problem, but it's a terrible interview question for trying to hire software engineers.
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.…
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."