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

121–130 of 134 posts

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

#121

Post by joshuamorton »

murgindrag wrote: post #112
joshuamorton wrote: post #105

Earlier quoted context omitted.

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

You didn't address anything I said. Nothing I said was related to early Google.

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

#122

Post by boyobo »

avinassh wrote: post #107
zinclozenge wrote: post #46

For 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?

https://ibb.co/BGj5nDn

Consider the following graph. The nth fibonnaci number is the number of possible walks from n to 1.

(I made a mistake in the picture, there should be an edge from 2 to 1).

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

#123

Post by [deleted] »

anandoza wrote: post #114
avinassh wrote: post #107

Earlier quoted context omitted.

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

[deleted]

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

#124

Post by guenthert »

I got a more general comment / question regarding this form of interview. Is this some kind of hidden age discrimination? Now I just might not be the target audience for those interviews or exactly one of those they mean to filter out, but after more than two decades of experience in the field (in various roles, but my first paid job as programmer was in '92) I feel uncomfortable with the kind of brain teasers I find on leetfree.org. Some are outright silly (e.g. "wiggle-sort"), some might be valid in some niche, but hardly common place (e.g. sparse matrix multiplication -- I haven't ever had the need to multiply matrices since leaving the University, but I haven't done any 3D graphics or robot control since then either).

If the companies which employ such interviews are aware of the distance of those puzzles to the day-to-day labor of a software engineer, then I suppose it's OK. But seeing that the interviewer himself was direct hire from University with no outside professional experience makes me wonder whether they are creating their own ivory tower. In case of Google this seems to work out for them (they decidedly wanted to make things different than then already established enterprises and having seen those, I say more power to them), but will it for others?

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

#125

Post by dang »

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.

Whoa can you please not break the site guidelines like this, regardless of how wrong or un-smart someone is or you feel they are? Taking nasty shots at other users is the fastest way to poison the commons, and entirely unnecessary.

https://news.ycombinator.com/newsguidelines.html

Edit: we've already had to ask you repeatedly not to do this. Continuing to do it will get you banned here. I don't want to ban you, so would you please review the guidelines and stick to them, regardless of what other commenters do?

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

#126

Post by dang »

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.

Swipes like "This reads like satire" break the site guideline against calling names. This comment would be just fine without it. Please edit them out in the future.

https://news.ycombinator.com/newsguidelines.html

Edit: we've had to ask you this more than once before. Worse, you've been doing it in other places too, e.g. https://news.ycombinator.com/item?id=24683603. We ban accounts that do this. I don't want to ban you, so would you please review the guidelines and stick to them?

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

#127

Post by pb7 »

dang wrote: post #126
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.

Swipes like "This reads like satire" break the site guideline against calling names. This comment would be just fine without it. Please edit them out in the future. https://news.ycombinator.com/newsguidelines.html Edit: we've had to ask you this more than once before. Worse, you've been doing it in other places too, e.g. https://news.ycombinator.com/item?id=24683603 . We ban accounts that do this. I don't want to ban…

https://news.ycombinator.com/threads?id=FriendlyNormie

What does “banned” mean exactly? Because this individual continues to post heinous garbage day after day and they’re “banned”.

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

#128

Post by dang »

pb7 wrote: post #127
dang wrote: post #126

Earlier quoted context omitted.

Swipes like "This reads like satire" break the site guideline against calling names. This comment would be just fine without it. Please edit them out in the future. https://news.ycombinator.com/newsguidelines.html Edit: we've had to ask you this more than once before. Worse, you've been doing it in other places too, e.g. https://news.ycombinator.com/item?id=24683603 . We ban accounts that do this. I don't want to ban…

https://news.ycombinator.com/threads?id=FriendlyNormie What does “banned” mean exactly? Because this individual continues to post heinous garbage day after day and they’re “banned”.

Banned means that an account's posts are killed, and only users with 'showdead' turned on in their profile can see them (with the exception of posts that enough users vouch for as good, which certainly hasn't happened in this case). If you turn on 'showdead' on, you're committing to see the worst of what the internet has to offer. If you don't want to see the bottom of the barrel, turn off the setting and you won't.

We don't delete posts outright except when the user who posted it asks us to. So yes, banned accounts can continue to post, except the posts go into [dead] status immediately, which removes them from public view. Only the tiny minority of users who've signed up for 'showdead' see them.

That balance is the best we can hope for on a site that allows anyone to create an account. If we stopped banned users from posting altogether, they'd just make a new account, and post the same stuff except now they wouldn't be banned anymore. Edit: In other words, it's an optimization problem and this seems to be the optimum, even though it's not entirely satisfactory.

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

#129

Post by pb7 »

dang wrote: post #128
pb7 wrote: post #127

Earlier quoted context omitted.

https://news.ycombinator.com/threads?id=FriendlyNormie What does “banned” mean exactly? Because this individual continues to post heinous garbage day after day and they’re “banned”.

Banned means that an account's posts are killed, and only users with 'showdead' turned on in their profile can see them (with the exception of posts that enough users vouch for as good, which certainly hasn't happened in this case). If you turn on 'showdead' on, you're committing to see the worst of what the internet has to offer. If you don't want to see the bottom of the barrel, turn off the setting and you won't.…

Thanks.

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

#130

Post by stmw »

guenthert wrote: post #124

I got a more general comment / question regarding this form of interview. Is this some kind of hidden age discrimination? Now I just might not be the target audience for those interviews or exactly one of those they mean to filter out, but after more than two decades of experience in the field (in various roles, but my first paid job as programmer was in '92) I feel uncomfortable with the kind of brain teasers I find…

There is probably some of that, no process is perfect... If nothing else, at least it's more objective than a more bias-prone personality fit approach. But it's also possible to practice - even 20+ years after University - if one wants to interview at Google or another company that uses those kinds of interviews. Reading a few blogs like this and some live interviews on a site like interviewing.io or some such will put you back to graph walks or sparse matrix multiplication in no time.
Post reply on HN