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

81–90 of 134 posts

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

#81

Post by jeffbee »

xienze wrote: post #75
jeffbee wrote: post #52

Earlier quoted context omitted.

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.

> and if it takes 5 minutes to discuss with a non-chess-playing candidate how a knight moves If it takes 5 minutes to explain how a knight moves I think that person might not be Google material...

We've already established that there are at least four different people in this thread alone who cannot clearly explain how a knight moves.

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

#82

Post by razius »

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…

This is my feeling as well, I think it's the difference between a computer scientist and an engineer. You just need to know who you are and what roles you prefer.

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

#83

Post by username90 »

itronitron wrote: post #78
pc86 wrote: post #37

Earlier quoted context omitted.

Why would managers get employees' scores on random interview questions? Why would that affect project assignments months or years later? Why would we assume folks at Google in charge of creating effective interview processes wouldn't be capable of the most basic statistical analysis, by making sure they had a large enough sample, enough performance reviews for each employee, etc?

Because it is common for managers to be very engaged in the hiring process.

Not at Google, they don't even decide who is going to be your manager until after these steps.

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

#84

Post by username90 »

pc86 wrote: post #43
thdc wrote: post #28

Earlier quoted context omitted.

I agree that this isn't a brainteaser. The problem itself appears to be nonsensical with no real world value but as long as it is a well defined problem with a concrete solution then it should be fine. Ideally the interviewer should be looking for how you approach the problem and what you do to obtain an answer (whether they do or not is a separate topic) Granted, the 747 question also technically does have a concret…

Now I'm just thinking about how I would survive in a giant blender. Whether or not someone is about to add ice seems like a pretty important variable.

The blender questions relies on knowing that muscle strength scales with the square and body mass scales with cube. This is why insects for example can be so strong relative to their weight. So if we scaled you down you would be strong enough to just jump out.

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

#85

Post by username90 »

joshbuckler wrote: post #64
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...

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.

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

#88

Post by phendrenad2 »

jtchang wrote: post #57

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.

CS is full of needless jargon and buzzwords, which only serve to make the field seem more impressive to outsiders.

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

#89

Post by CydeWeys »

joshuamorton wrote: post #71
CydeWeys wrote: post #42

Earlier quoted context omitted.

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…

They don't (for SWEs), or at least you aren't supposed to. I think for PMs there may be questions more in this realm, but for SWEs, your questions should all be programming problems.

A System Design interview is required for all senior+ SWE candidates, plus other roles like at least SRE: https://www.youtube.com/watch?v=Gg318hR5JY0

Similar but smaller questions along these lines are given to more junior candidates often enough too, as one of multiple questions.

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

#90

Post by shajznnckfke »

jtchang wrote: post #57

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.

The term is over 50 years old: https://en.m.wikipedia.org/wiki/Memoization#Etymology

Probably been used in CS longer than “caching”.

Post reply on HN