How many paths of length K are there between A and B? (2021)

by jxmorris12 • 11 months ago

34 12 11 months ago

Chinjut3• 11 months 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.

efavdb• 11 months 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?

shiandow• 11 months ago

I think it could generate the minimal polynomiale instead. Though it is curious that this would still make it faster for almost all matrices, just not guaranteed to be correct.

Labo333• 11 months ago

CH gives you recurrence on the matrix. You want recurrence on an individual element (indexed by [start][end]).

Chinjut3• 11 months ago

Any recurrence that holds on the matrix also holds on each individual element (and vice versa, in that a recurrence holds on the matrix just in case it holds on every individual element).

gcanyon• 11 months ago

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.

stephenlf2• 11 months 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)`?

quibono• 11 months ago

Yes, the comment has it backwards.

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)`?

This is the "discussion" part of the interview where you're supposed to ask, and the interviewer will tell you that you can assume the nodes are numbered from 0/1 to N-1/N. I imagine the adjacency modeling is up to you since you'll be judged based off what representation you pick, and that will depend on the proposed solution.

stephenlf2• 11 months ago

I slept on the problem and, much like another commenter, found immense clarity by reading the actual interview question. The question is about knights on a phone pad. This article immediately starts with a generalization of the “knights on a phone pad” problem.

kazinator• 11 months ago

To avoid dealing with very large numbers, assume that we're computing our answer modulo a large prime.

Or tool up and get a better programming language?

xigoi• 11 months ago

This is not about the programming language. Arbitrary-size integers make complexity analysis much more nuanced because arithmetic operations are no longer constant time.

How many paths of length K are there between A and B? (2021)

Related Stories