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

91–100 of 134 posts

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

#91

Post by phendrenad2 »

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…

Problem: You need to test if people can do A. No test exists to test this directly.

Solution: Make a test to test if people can do B. Studies correlate ability to do B with ability to do A.

Complication: Lose lots of candidates who can do A but choose not to get good at B.

Solution: Pay tons of recruiters to pound the pavement and turn over every rock and make sure every tech worker in the world applies.

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

#92

Post by joshuamorton »

CydeWeys wrote: post #89
joshuamorton wrote: post #71

Earlier quoted context omitted.

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.

Your right though that candidates can get system design interviews, but "how many servers does it take to run gmail" is not anything like a system design interview. "How would you architect gmail" is. System design questions by their nature don't really have a correct answer. Your right though that candidates can get system design interviews.

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

#93

Post by colinmhayes »

mcqueenjordan wrote: post #8

This is a fun problem, but it's a terrible interview question for trying to hire software engineers.

The point of leetcode problems isn't to find out if you're a good software engineer. It's to find out if you're willing to spend hundreds of hours practicing tedious bullshit to get a job and google. If you can solve this in the interview you can become a good software engineer.

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

#94

Post by colinmhayes »

sjg007 wrote: post #86

Algorithm questions are the tech version of word problems. What they tell you is how good someone is at solving these types of problems. Solve a lot of these problems if you want to work at Google.

The point of these problems is to find out how committed an applicant is. If you can ace them the interviewer knows that you have enough critical thinking skills to succeed and enough commitment skills to learn whatever you need.

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

#96

Post by tyrust »

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.

This concept was introduced to me back in my algorithms class and is pretty useful. For anyone looking for a longer explanation, page 167 of the textbook [0] has the nugget and some examples:

>Every dynamic program has an underlying dag (directed acyclic graph) structure: think of each node as representing a subproblem, and each edge as a precedence constraint on the order in which the subproblems can be tackled.

[0] - PDF: http://algorithmics.lsi.upc.edu/docs/Dasgupta-Papadimitriou-...

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

#97

Post by username90 »

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.

Memoization is only when you cache the results of a referentially transparent function in software, caching is more general. You have cpu caches, browser bashes, even entire servers can be caches of common web requests etc. So using the word "memoization" is more specific and leads to less confusion.

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

#98

Post by twiceaday »

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

I tried but Wolfram Alpha doesn't take inputs that long hah. In any case even if it works you will likely get irrational terms which will make it only theoretically nice but not practically computable, like the closed-form Fibonacci formula.

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

#99

Post by CydeWeys »

joshuamorton wrote: post #92
CydeWeys wrote: post #89

Earlier quoted context omitted.

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.

Your right though that candidates can get system design interviews, but "how many servers does it take to run gmail" is not anything like a system design interview. "How would you architect gmail" is. System design questions by their nature don't really have a correct answer. Your right though that candidates can get system design interviews.

Estimating how much traffic needs to be handled and what kind of resources it would take to handle it are absolutely part of both of those questions, which in reality are the same interview problem because a System Design interview isn't a single question but rather a long series of guided questions that cover architecture, scaling, and a lot more.

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

#100

Post by lostmsu »

I would stop at "level 3" in this blog post intentionally.

Writing an unrolled dynamic solution as opposed to a simple cache is an extremely error-prone mental gymnastics in my experience. The initialization procedure and indexing are especially susceptible. Moreover, the resulting code is usually barely readable.

I wish people would stop expecting it. In practice, the memoization approach is sufficient in 99% cases, and having a 3% chance to make an error in unroll code that causes user data to be misplaced is a much worse option.

Post reply on HN