Hacker News Reader

Comment by username90 | Hacker News Reader

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

View on HN

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 coming up with it in 45 minutes during an interview is not going to happen.

The junior and the senior aren't competing for the same job though, this just checks that you still remember the theory you learned in college. And no, just because you are senior doesn't mean that you get a free pass forgetting everything you learned in college. I haven't practiced problems like this in over 5 years and I still ace them.

> this just checks that you still remember the theory you learned in college.

Sure, but not everyone went to college or studied computer science / math. This seems like one of those problems that's really just testing a very specific type of preexisting knowledge.

You'll get full score even if you don't know the matrix solution, just doing a memoized recursive one is enough. However if you had that specific knowledge then they still test whether they have the skills to apply esoteric knowledge correctly which is also very valuable.

Anyway, Google no longer has this question. Once it gets known outside Google bans it from interviews. Sometimes people give banned questions but in general they don't and it is taken into account. I remember it being popular as a question 4 years ago, popular questions tend to leak quickly and get banned though.

According to the blog post, the interviewers weren't even aware of the matrix solution until one candidate brought it up.

I assume they all immediately handed in their letters of resignation and/or hired the candidate in as a principle engineer.

Sarcasm aside, the very fact that they ban questions demonstrates how useless these types of questions really are.

If you ban it because people might know it due to its popularity then what are you testing for? I thought it was for whether a candidate could solve the problem, but it appears to be to check which percentile of a special 'knowledge' club they belong to...

If you are an experienced programmer, how long does it take you to learn the handful or so algs/concepts you need for these kinds of problems? It'd probably 20-30 hours of learning, which is a reasonable expectation to ace interviews. - And it is not like you have to necessarily come up with a solution all by yourself, communicating your issues well, and the interviewer will probably help you, if you have an otherwise impressive résume it shouldn't pose a problem at all.

I wouldn't be surprised if people occasionally re-create famous math problems, given how many interview questions seem to get created these days.

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.

That is covered in the next blogpost: https://alexgolec.dev/knights-dialer-logarithmic-time-editio...

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.

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.

Reply on news.ycombinator.com