Google Interview Questions Deconstructed: The Knight’s Dialer
1–10 of 134 posts
Re: Google Interview Questions Deconstructed: The Knight’s Dialer
#2Counting the number of paths when you have loops is easiest using a connection matrix and matrix exponentiation. Then you get log(n) time.
Re: Google Interview Questions Deconstructed: The Knight’s Dialer
#3Typical 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.
Re: Google Interview Questions Deconstructed: The Knight’s Dialer
#4Typical 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 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."
Re: Google Interview Questions Deconstructed: The Knight’s Dialer
#5Counting the number of paths when you have loops is easiest using a connection matrix and matrix exponentiation. Then you get log(n) time.
[deleted]
Re: Google Interview Questions Deconstructed: The Knight’s Dialer
#6Counting the number of paths when you have loops is easiest using a connection matrix and matrix exponentiation. Then you get log(n) time.
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.
Re: Google Interview Questions Deconstructed: The Knight’s Dialer
#7Typical 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 didn't seem like a brain-teaser to me. I thought it was a fun problem to try and solve.
Re: Google Interview Questions Deconstructed: The Knight’s Dialer
#8This is a fun problem, but it's a terrible interview question for trying to hire software engineers.
Re: Google Interview Questions Deconstructed: The Knight’s Dialer
#9Typical 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.
Edit: This applies for senior engineers as well.
Re: Google Interview Questions Deconstructed: The Knight’s Dialer
#10Typical 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.
Not really. Simple recursive backtracking problem. They're more checking that you understand backtracking and recursion.