Knight Dialer: Count Dialable Digit Sequences
Company: Whatnot
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
# Knight Dialer: Count Dialable Digit Sequences
A chess **knight** is placed on a telephone keypad and dials a number by hopping between buttons. Each time it lands on a button, that button's digit is appended to the sequence being dialed.
The keypad is laid out as a 4-row by 3-column grid. Only the ten digit buttons are usable; the two bottom corners are blank and the knight may never land on them:
```
| 1 | 2 | 3 |
| 4 | 5 | 6 |
| 7 | 8 | 9 |
| | 0 | |
```
A **knight move** is the standard chess L-shape: two cells in one orthogonal direction and one cell in the perpendicular direction (8 possible offsets). A move is **legal** only if it lands on a usable digit button (it must stay on the grid and must not land on either blank corner).
Write a function
```
count_dialed_numbers(start_digit, num_of_hops)
```
that returns the number of **distinct digit sequences** the knight can dial when it starts on `start_digit` and makes exactly `num_of_hops` legal moves. The dialed sequence includes the starting digit followed by the digit landed on after each hop, so a run of `num_of_hops` moves produces a sequence of `num_of_hops + 1` digits. Two outcomes are considered the same sequence only if they produce the identical ordered list of digits.
## Examples
- `count_dialed_numbers(1, 1) = 2`
From `1`, the only legal knight moves land on `6` or `8`, giving the sequences `1 -> 6` and `1 -> 8`. That is 2 distinct sequences.
- `count_dialed_numbers(1, 0) = 1`
With zero hops the knight never moves; the single dialed sequence is just `1`.
- `count_dialed_numbers(5, 1) = 0`
No legal knight move from `5` lands on any usable button, so no sequence of length 2 can be dialed.
## Reference: legal knight moves from each digit
To remove any ambiguity about the board geometry, the legal destination digits from each starting digit are:
- `0 -> {4, 6}`
- `1 -> {6, 8}`
- `2 -> {7, 9}`
- `3 -> {4, 8}`
- `4 -> {0, 3, 9}`
- `5 -> {}` (no legal moves)
- `6 -> {0, 1, 7}`
- `7 -> {2, 6}`
- `8 -> {1, 3}`
- `9 -> {2, 4}`
## Constraints
- `0 <= start_digit <= 9`
- `0 <= num_of_hops <= 5000`
- The count can grow exponentially, so return the answer **modulo** $10^9 + 7$.
- Target an efficient solution: `O(num_of_hops)` time using dynamic programming over the 10 digits (a constant-size transition), rather than enumerating every path.
Quick Answer: This question evaluates a candidate's ability to model constrained state transitions with dynamic programming, using a knight's legal moves on a phone keypad as the domain. It tests recognition that counting sequences under fixed transition rules reduces to tracking per-digit counts over discrete steps, a common way to probe DP-over-graph thinking in coding interviews. The problem sits at a practical application level, requiring an efficient algorithm rather than brute-force path enumeration.
A chess knight is placed on a telephone keypad and dials a number by hopping between buttons. Each time it lands on a button, that button's digit is appended to the sequence being dialed.
The keypad is a 4-row by 3-column grid. Only the ten digit buttons are usable; the two bottom corners are blank and the knight may never land on them:
```
| 1 | 2 | 3 |
| 4 | 5 | 6 |
| 7 | 8 | 9 |
| | 0 | |
```
A knight move is the standard chess L-shape (8 possible offsets). A move is legal only if it lands on a usable digit button (on the grid, never a blank corner).
Implement `count_dialed_numbers(start_digit, num_of_hops)` returning the number of distinct digit sequences the knight can dial when it starts on `start_digit` and makes exactly `num_of_hops` legal moves. The dialed sequence is the starting digit followed by the digit landed on after each hop, so `num_of_hops` moves produce a sequence of `num_of_hops + 1` digits. Two outcomes are the same sequence only if they produce the identical ordered list of digits.
Examples:
- `count_dialed_numbers(1, 1) = 2` (from 1 you can only reach 6 or 8)
- `count_dialed_numbers(1, 0) = 1` (no hops: just the single digit 1)
- `count_dialed_numbers(5, 1) = 0` (5 has no legal knight move)
Legal destination digits from each start:
- `0 -> {4, 6}`, `1 -> {6, 8}`, `2 -> {7, 9}`, `3 -> {4, 8}`, `4 -> {0, 3, 9}`, `5 -> {}`, `6 -> {0, 1, 7}`, `7 -> {2, 6}`, `8 -> {1, 3}`, `9 -> {2, 4}`
Constraints:
- `0 <= start_digit <= 9`
- `0 <= num_of_hops <= 5000`
- The count grows exponentially, so return the answer modulo 1_000_000_007.
- Aim for O(num_of_hops) time using DP over the 10 digits (constant-size transition), not path enumeration.
Constraints
- 0 <= start_digit <= 9
- 0 <= num_of_hops <= 5000
- Return the answer modulo 1_000_000_007 because the count can grow exponentially.
- Aim for O(num_of_hops) time with a constant-size (10-digit) DP transition.
Examples
Input: (1, 1)
Expected Output: 2
Explanation: From 1 the only legal knight moves land on 6 or 8, giving sequences 1->6 and 1->8.
Input: (1, 0)
Expected Output: 1
Explanation: Zero hops means the knight never moves; the only dialed sequence is the single digit 1.
Input: (5, 1)
Expected Output: 0
Explanation: Digit 5 has no legal knight move, so no length-2 sequence can be dialed.
Input: (5, 0)
Expected Output: 1
Explanation: Zero hops from 5 still dials the single-digit sequence 5.
Input: (0, 0)
Expected Output: 1
Explanation: Edge: any digit with zero hops yields exactly one sequence (itself).
Input: (1, 2)
Expected Output: 5
Explanation: 1->6 branches to {0,1,7} and 1->8 branches to {1,3}, totaling 3 + 2 = 5 distinct sequences.
Input: (4, 2)
Expected Output: 6
Explanation: 1->{0,3,9} then expanding each reachable digit gives 6 distinct two-hop sequences.
Input: (6, 3)
Expected Output: 16
Explanation: Three hops from 6; the DP accumulates 16 distinct four-digit sequences.
Input: (9, 10)
Expected Output: 3728
Explanation: Ten hops from 9; the DP over 10 digits yields 3728 distinct sequences.
Input: (0, 5000)
Expected Output: 896001470
Explanation: Large-N stress case: the raw count is astronomically large, so it is reported modulo 1_000_000_007.
Hints
- Let dp[d] be the number of distinct sequences that currently end on digit d. Start with dp[start_digit] = 1 and all others 0.
- Each hop is a fixed transition: for every digit d, push its count forward to each legal destination in the move table. This is a constant-size (at most 10-digit) step repeated num_of_hops times.
- The distinct-sequence count equals the number of distinct move paths, since a path is exactly the ordered list of digits landed on. After all hops, the answer is the sum of dp over all digits, taken modulo 1_000_000_007.
- Handle num_of_hops == 0 naturally: no transitions run, so the answer is 1 (just the starting digit).