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.
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)`?
> 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.
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.
This is not about the programming language. Arbitrary-size integers make complexity analysis much more nuanced because arithmetic operations are no longer constant time.
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.
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 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.
Note that the article describes this Berlekamp-Massey approach as involving a step of complexity on the order of EV, which is V^3 in the worst-case. So this is only beneficial for sparse matrices. It does seem like Berlekamp-Massey is used to efficiently but non-guaranteedly compute determinants for sparse matrices, as described at https://en.wikipedia.org/wiki/Block_Wiedemann_algorithm
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).
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.
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)`?
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.
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.
> 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?
This is not about the programming language. Arbitrary-size integers make complexity analysis much more nuanced because arithmetic operations are no longer constant time.
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.
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 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.
Note that the article describes this Berlekamp-Massey approach as involving a step of complexity on the order of EV, which is V^3 in the worst-case. So this is only beneficial for sparse matrices. It does seem like Berlekamp-Massey is used to efficiently but non-guaranteedly compute determinants for sparse matrices, as described at https://en.wikipedia.org/wiki/Block_Wiedemann_algorithm
CH gives you recurrence on the matrix. You want recurrence on an individual element (indexed by [start][end]).
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).