I'm not sure what to make of the fact that for the abstract matrix problem in the original post, I thought about it for a moment without making any progress, but then for the knights on the phone pad problem it took me just two moments (about twenty seconds) to come up with the third solution -- and for context, I'm a product manager with a history as a developer. It would take me less than five minutes to code it up.
I wish I hadn't read the fourth solution description -- the language used wasn't clear at all to me, but it was enough to point me in the right direction, or maybe I'm just that clever?
That said, I don't like interview questions like that -- there's very much a component of you either get it or you don't. The interviewer says they talk people through it, and if they're good at that, great. But if not, a question like that is (in my book) unfair.
stephenlf · 2h ago
I am struggling to understand some of the explanations offered here. It’s certainly a skill issue on my part. I never learned DP in school and tabular DP has never clicked for me. However, I think there are a few things you could clarify.
> queue = [(A, 0)] # We track (length of walk, current node)
Surely the comment should be reversed, right?
Also, how are we encoding “current node”? Is it an integer? Does A=0, and the rest of the nodes have some arbitrary value? How do we calculate `neighbors(node)`?
Chinjut · 5h ago
Odd to use Berlelamp-Massey to recover a linear recurrence, when Cayley-Hamilton already directly gives you a linear recurrence whose characteristic polynomial is that of the matrix.
Labo333 · 41m ago
CH gives you recurrence on the matrix. You want recurrence on an individual element (indexed by [start][end]).
efavdb · 3h ago
But to get the polynomial you need to take the determine of A -lambda I, which runs in n^3. Next question then why doesn’t this Berlelamp-Massey method then effectively give you determinants in n^2?
I wish I hadn't read the fourth solution description -- the language used wasn't clear at all to me, but it was enough to point me in the right direction, or maybe I'm just that clever?
That said, I don't like interview questions like that -- there's very much a component of you either get it or you don't. The interviewer says they talk people through it, and if they're good at that, great. But if not, a question like that is (in my book) unfair.
> queue = [(A, 0)] # We track (length of walk, current node)
Surely the comment should be reversed, right?
Also, how are we encoding “current node”? Is it an integer? Does A=0, and the rest of the nodes have some arbitrary value? How do we calculate `neighbors(node)`?