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

51–60 of 134 posts

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

#51

Post by bowmessage »

blahyawnblah wrote: post #33
jeffbee wrote: post #29

It might not be obvious but these kinds of questions are terrible for diversity and inclusion because they incorporate too much cultural knowledge that is not universal. 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. That disadvantages people from low-chess cultures, no matter how qualified and intelligent they may be. Chess also has a…

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)

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

#52

Post by jeffbee »

xienze wrote: post #44
jeffbee wrote: post #29

It might not be obvious but these kinds of questions are terrible for diversity and inclusion because they incorporate too much cultural knowledge that is not universal. 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. That disadvantages people from low-chess cultures, no matter how qualified and intelligent they may be. Chess also has a…

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

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

#53

Post by jeffbee »

pb7 wrote: post #49
jeffbee wrote: post #29

It might not be obvious but these kinds of questions are terrible for diversity and inclusion because they incorporate too much cultural knowledge that is not universal. 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. That disadvantages people from low-chess cultures, no matter how qualified and intelligent they may be. Chess also has a…

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.

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

#54

Post by [deleted] »

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)

[deleted]

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

#55

Post by chromatin »

murgindrag wrote: post #31

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

Likewise I was surprised at how trivial this seemed?

My first solution was matrix multiplication -- I remember distinctly in undergraduate discrete mathematics learning that matrix exponentiation solved the hops-on-graph problem. I did not think to convert to binary to make logarithmic time, however.

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

#56

Post by mym1990 »

xienze wrote: post #35
mym1990 wrote: post #30

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

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

They have, but we're definitely seeing a turn towards a better direction recently. The software engineering job market has gone through some incredibly fast changes in only the last 10-15 years, and we will likely never perfect the process as the landscape changes, but I guess the optimist in me believes that at least some companies are doing their best. Its just my view that when the first 10 comments on this post echo that this is a terrible practice, it makes it difficult to have a more technical conversation about the OP.

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

#58

Post by mym1990 »

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.

Hey, its like he said: 'theres no chess knowledge involved' hehe

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

#60

Post by dmurray »

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.

Post reply on HN