Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Google Interview Questions Deconstructed: The Knight’s Dialer

alexgolec.dev

Post reply on HN
Print view View original

61–70 of 134 posts

Re: Google Interview Questions Deconstructed: The Knight’s Dialer

#61

Post by username90 »

gedy wrote: post #39
username90 wrote: post #9

Earlier quoted context omitted.

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 th…

Maybe for Google-type/scale problems, but I'd say that the engineers I've worked with and hired for "normal" software jobs (e.g. here's a boring business domain, make it CRUD, make an API, make a UI for it) - there is almost an inverse correlation between being a CS/algorithm genius and being happy/successful at these everyday roles. From observation, many super sharp CS people very frequently want to write systems f…

I wouldn't be surprised if the people Google rejects because they lacked technical skills are much better than the people Google rejects because they lacked soft skills. Accumulate that for every company paying more than your company and the people with great algorithm skills left will likely be social misfits in some way.

Re: Google Interview Questions Deconstructed: The Knight’s Dialer

#62

Post by filoleg »

jeffbee wrote: post #53
pb7 wrote: post #49

Earlier quoted context omitted.

This reads like satire. There is no chess knowledge involved. The constraint is that you can only dial in a 2x3 L-shape. Edit: Typo, as opposed to the well known capital L-shape that is just one unit wide.

Seems like you already fucked it up, smart guy.

I think the parent comment just worded it poorly, but is not necessarily wrong.

They were probably just trying to say that a knight's move looks like a straight line of 3 cells in one direction (which includes the starting position of that piece) and then 1 more cell in a perpendicular direction.

Re: Google Interview Questions Deconstructed: The Knight’s Dialer

#64

Post by joshbuckler »

username90 wrote: post #2

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

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#Applicat...

Re: Google Interview Questions Deconstructed: The Knight’s Dialer

#65

Post by jpeterson »

username90 wrote: post #9
warmfuzzykitten wrote: post #3

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 th…

I've been doing this for a long time, and I've never seen any kind of correlation between how well someone solves silly algorithm puzzles in a 45 minute window and any kind of real-world performance. Also, there's no apparent a prior reason why this would be the case. It might be that the way performance rating is done at Google is constructed so as to be correlated with silly brain teaser performance.

Re: Google Interview Questions Deconstructed: The Knight’s Dialer

#66

Post by jeffbee »

bowmessage wrote: post #51
blahyawnblah wrote: post #33

Earlier quoted context omitted.

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.

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)

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.

Re: Google Interview Questions Deconstructed: The Knight’s Dialer

#67

Post by mym1990 »

jeffbee wrote: post #52
xienze wrote: post #44

Earlier quoted context omitted.

> 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.

The difference is on the margin. If typical candidates who reach the optimal solution reach it in the last 5 minutes, and if it takes 5 minutes to discuss with a non-chess-playing candidate how a knight moves, then you have severely disadvantaged that candidate.

Isn't this somewhat dependent on the outlook of the interviewer? I know interviewers will greatly vary, but is it not more important to consider what my path to the solution was, rather than what the actual answer is?

I would be more inclined towards a candidate that knew nothing of a problem but was able to explore a way to the answer vs. a candidate that knew the answer simply because of hours of rehearsal

Re: Google Interview Questions Deconstructed: The Knight’s Dialer

#68

Post by kevincox »

mcqueenjordan wrote: post #8

This 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. 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".

Re: Google Interview Questions Deconstructed: The Knight’s Dialer

#70

Post by kevincox »

defen wrote: post #6
username90 wrote: post #2

Counting 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 comi…

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.

Post reply on HN