Knight Dialer

Knight Dialer

1. What is this problem about?

The Knight Dialer interview question is a combinatorial counting problem based on chess movements. A knight is placed on a standard phone keypad. From its current digit, it can jump to any digit reachable by a valid knight move. You need to find how many unique phone numbers of length $n$ can be dialed. The result should be returned modulo $10^9 + 7$.

2. Why is this asked in interviews?

Companies like Meta, Amazon, and Google use the Knight Dialer coding problem to test a candidate's ability to implement Dynamic Programming. It evaluates whether you can model a problem as a state machine where the number of ways to reach a digit in $k$ steps depends on the number of ways to reach its "jump-source" neighbors in $k-1$ steps.

3. Algorithmic pattern used

This problem follows the Linear Dynamic Programming (State Machine) pattern.

1. Adjacency Map: Define the possible moves for each digit (e.g., 1 can jump to 6 and 8).
2. DP State: dp[k][digit] is the number of sequences of length k ending on digit.
3. Transition: dp[k][digit] = sum(dp[k-1][neighbor]) for all neighbors that can jump to that digit.
4. Optimization: Since step $k$ only depends on $k-1$, you can use $O(1)$ space by only keeping the counts for the current and previous step.

4. Example explanation

For $n = 2$:

• To end at 1 in 2 steps, you must have started at 6 or 8.
• ways to reach 6 in 1 step: 1.
• ways to reach 8 in 1 step: 1.
• Total ways to end at 1 in 2 steps: 2 (sequences "61" and "81"). Sum this for all digits 0-9 to get the total for $n=2$.

5. Common mistakes candidates make

• Recursive TLE: Using recursion without memoization ($O(8^N)$ complexity).
• Ignoring Modulo: Failing to apply the modulo at each addition, leading to overflow for even moderate $n$.
• Digit 5: Forgetting that digit 5 has no knight moves to any other digit.

6. Interview preparation tip

This problem is a specific case of counting paths in a graph. For very large $n$ ($10^{18}$), this can be solved in $O(\log n)$ using Matrix Exponentiation. Mentioning this shows high-level mathematical and algorithmic depth.