3 ms·
How many paths of length K are there between A and B? (2021)
- Chinjut 1y agoOdd 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 1y agoBut 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 1y agoI 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.
- Chinjut 1y agoNote 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 https://en.wikipedia.org/wiki/Block_Wiedemann_algorithm
- Labo333 1y agoCH gives you recurrence on the matrix. You want recurrence on an individual element (indexed by [start][end]).
- Chinjut 1y agoAny 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 1y agoI'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 1y agoI 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 1y agoYes, 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.
- stephenlf 1y agoI 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 1y 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 1y agoThis is not about the programming language. Arbitrary-size integers make complexity analysis much more nuanced because arithmetic operations are no longer constant time.
- deleted 1y ago[deleted]