Note: This is former Google interview question which was leaked and thus blacklisted. Because of this, a former Google interviewer decided to write an excellent blog post breaking down how he asked this question and what he expected from candidates who attempt it. I highly recommend you to read the blog post by the interviewer which talks in detail about the approach to solve the problem and common pitfalls.
Question
Imagine you place a knight chess piece on a phone dial pad. This chess piece moves in an uppercase “L” shape: two steps horizontally followed by one vertically, or one step horizontally then two vertically. Suppose you dial keys on the keypad using only hops a knight can make. Every time the knight lands on a key, we dial that key and make another hop. The starting position counts as being dialed.
How many distinct numbers can you dial in N hops from a particular starting position?
Solution
If you start writing the path starting from any key, you’ll soon notice that the paths come back to the same key frequently. Even logically, we only have 10 keys and N can go upto 5000. This should give a hint for recursion.
The recurrence relation is: T(key, N) = T(neighbor1, N-1) + T(neighbor2, N-1) +...+ T(neighbor[key],N-1)
Try finding paths starting from key 6 with N=4. When you graw the graph like structure, you’ll notice that there are several repeated calls to the function having same key and N. This calls for memoization (recursive) or DP (iterative)!
Let’s see a DP approach here. Suppose you have a 2D DP array having N rows and 10 columns (corresponding to each key). Let dp[i][j] be defined as number of distinct paths starting at key j after i hops.
Initialization: When N=1, given that you can start at any key, for each key the path consists of only that key so no. of paths=1 for each key.
DP relation: Further, for N>1, no. of paths for key j is = noOfPaths(neighbor[j], N-1) = dp[i-1][neighbor1(j)] + dp[i-1][neighbor2(j)] + .. + dp[i-1][neighbor(j)]
Notice that we only need dp[i-1] to find values for dp[i]. So we don’t really need a 2D DP. We are in fact wasting a lot of space as N can be huge. Below is a solution with 1D DP:
int knightDialer(int N) {
const long long int modNum = 1000000007;
vector<vector<int>> neighbors {
{4, 6},
{6, 8},
{7, 9},
{4, 8},
{0, 3, 9},
{},
{0, 1, 7},
{2, 6},
{1, 3},
{2, 4}
};
vector<long long int> dp(10, 1);
for (int i=1; i<N; i++) {
vector<long long int> temp(10, 0);
for (int i=0; i<10; i++) {
for (int neighbor : neighbors[i]) {
temp[i] = (temp[i]+dp[neighbor])%modNum;
}
}
swap(temp, dp);
}
return accumulate(dp.begin(), dp.end(), 0, [modNum](long long int a, long long int b) {return (a+b)%modNum;});
}
Time complexity: O(N)
Space complexity: O(1)