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.