Facebook Interview Question
Software EngineersCountry: United States
@majia168 - questions: " And choosing successive digits " - what does that mean ? Also, what exactly is a path. If a knight chooses to move between 4 and 9 and then back again a path of length INFINITY could be formed. So what is the definition of path? It seems that a path can visit the same digits more than once as long as the path leading to that digit is different. Please provide more clarification. Thanks
A valid path of length n=4 would be 1,8,3,4 an other is 1,8,1,8 and yet an other is 1,8,3,8
I think there is no closed form, or at least no obvious one because from some fields you can do two moves, from others 3, so we might need to calculate using the recursion
rec(num, i) = rec(8, i-1) + rec(6, i-1) if i >= 0 and num = 1
rec(7, i-1) + rec(9, i-1) if i >= 0 and num = 2
etc..
0 if i < 0
result = sum(num, n-1) for each 0 <= num < 9
instead of hardcoding the moves it might be neater to create a table of moves and use that one.
this recursion has a common subproblem, that is for each pair (num, i) the number of combinations. I can iteratively build it up in an O(n) with O(1) space or just insert memoization on the recursion using a HT (using O(n) memory)
package com.puzzle;
import java.util.*;
/**
* Phone path combinations
*
*/
public class PhonePaths {
private int[][] PHONE_MATRIX = {{1, 2, 3}, {4, 5, 6}, {7, 8, 9}, {-1, 0, -1}};
private int ROW_SIZE = PHONE_MATRIX.length;
private int COL_SIZE = PHONE_MATRIX[0].length;
private Map<Integer, Set<Integer>> states = new HashMap<>();
/**
* Returns number of possible paths starting from given digit of size n
*
* @param digit Starting digit
* @param n Path size
* @return Number of paths
*/
public int findNumberOfPaths(int digit, int n) {
return _find(digit, n);
}
/**
* Find number of possible paths starting from given digit of size n
*
* @param digit Starting digit
* @param n Path size
* @return Number of paths
*/
private int _find(int digit, int n) {
if (n == 0)
return 0;
else if (n == 1)
return 1;
Set<Stack<Integer>> results = new HashSet<>();
// start the flow from given digit
Queue<Stack<Integer>> queue = new LinkedList<>();
Stack<Integer> path = new Stack<>();
path.add(digit);
queue.add(path);
while (!queue.isEmpty()) {
path = queue.poll();
if (path.size() == n && !results.contains(path)) {
results.add(path);
continue;
}
Integer currentPathDigit = path.peek();
Set<Integer> states = getStates(currentPathDigit);
if (states != null && states.size() > 0) {
for (Integer state : states) {
Stack<Integer> newPath = new Stack<>();
newPath.addAll(path);
newPath.add(state);
queue.add(newPath);
}
}
}
results.forEach(System.out::println);
return results.size();
}
/**
* Returns possible next states for a given digit; use memoization for optimization
*
* @param digit Digit
* @return All possible states
*/
private Set<Integer> getStates(int digit) {
if (states.containsKey(digit)) {
return states.get(digit);
}
int digitRow = -1;
int digitCol = -1;
for (int row = 0; digitRow == -1 && row < PHONE_MATRIX.length; ++row) {
for (int col = 0; digitCol == -1 && col < PHONE_MATRIX[row].length; ++col) {
if (PHONE_MATRIX[row][col] == digit) {
digitRow = row;
digitCol = col;
break;
}
}
}
Set<Integer> nextStates = getNextState(digit, digitRow, digitCol);
states.put(digit, nextStates);
return states.get(digit);
}
/**
* This method returns the possible states for a given digit
*
* @param digit Digit
* @param row Row index for the given digit
* @param col Column index for the given digit
* @return List of possible states
*/
private Set<Integer> getNextState(int digit, int row, int col) {
Set<Integer> set = new HashSet<>();
// 1 to 6
if (row - 2 >= 0 && col - 1 >= 0 && PHONE_MATRIX[row - 2][col - 1] != -1) {
set.add(PHONE_MATRIX[row - 2][col - 1]);
}
// 4 to 9
if (row + 1 < ROW_SIZE && col + 2 < COL_SIZE && PHONE_MATRIX[row + 1][col + 2] != -1) {
set.add(PHONE_MATRIX[row + 1][col + 2]);
}
// 1 to 8
if (row + 2 < ROW_SIZE && col + 1 < COL_SIZE && PHONE_MATRIX[row + 2][col + 1] != -1) {
set.add(PHONE_MATRIX[row + 2][col + 1]);
}
// 6 to 7
if (row + 1 < ROW_SIZE && col - 2 >= 0 && PHONE_MATRIX[row + 1][col - 2] != -1) {
set.add(PHONE_MATRIX[row + 1][col - 2]);
}
// 3 to 4
if (row - 1 >= 0 && col + 2 < COL_SIZE && PHONE_MATRIX[row - 1][col + 2] != -1) {
set.add(PHONE_MATRIX[row - 1][col + 2]);
}
// 8 to 3
if (row + 2 < ROW_SIZE && col - 1 >= 0 && PHONE_MATRIX[row + 2][col - 1] != -1) {
set.add(PHONE_MATRIX[row + 2][col - 1]);
}
// 7 to 2
if (row - 2 >= 0 && col + 1 < COL_SIZE && PHONE_MATRIX[row - 2][col + 1] != -1) {
set.add(PHONE_MATRIX[row - 2][col + 1]);
}
return set;
}
public static void main(String... args) {
PhonePaths pc = new PhonePaths();
System.out.println(pc.findNumberOfPaths(1, 0));
System.out.println(pc.findNumberOfPaths(1, 1));
System.out.println(pc.findNumberOfPaths(1, 4));
}
}
#include <iostream>
#include <string>
#include <vector>
#include <unordered_map>
static const int COLS = 3;
static const int ROWS = 4;
struct Digit {
std::vector<int> _nei;
};
struct Paths {
std::unordered_map<int, Digit> digits;
int getNei(int* mat, int offSet1, int offSet2, int row, int col) {
row += offSet1;
col += offSet2;
int retVal = -1;
if (row >= 0 && row < ROWS && col >= 0 && col < COLS ) {
int off = row*COLS + col;
//std::cout << "row, " << row << " col, " << col<< " off, " << off << "!\n";
retVal = *(mat + off);
}
return retVal;
}
void createDigitsPaths() {
int matrix[ROWS][COLS] = {1,2,3,4,5,6,7,8,9,-1,0,-1};
for (int i=0; i<ROWS; i++) {
for (int j=0; j<COLS; j++) {
int num=matrix[i][j];
if (num <0 ) {
continue;
}
int* mat = (int*) matrix;
Digit& dig = digits[num];
std::cout << "num, " << num << "!\n";
for (int offSet1 = 1; offSet1 <=2; offSet1++ ) {
int offSet2 = 2 - offSet1+1;
int nei = getNei(mat, offSet1, offSet2, i, j);
if (nei >= 0 ) {
std::cout << "nei1, " << nei << "!\n";
dig._nei.push_back(nei);
}
nei = getNei(mat, offSet1, -offSet2, i, j);
if (nei >= 0 ) {
std::cout << "nei2, " << nei << "!\n";
dig._nei.push_back(nei);
}
nei = getNei(mat, -offSet1, offSet2, i, j);
if (nei >= 0 ) {
std::cout << "nei3, " << nei << "!\n";
dig._nei.push_back(nei);
}
nei = getNei(mat, -offSet1, -offSet2, i, j);
if (nei >= 0 ) {
std::cout << "nei4, " << nei << "!\n";
dig._nei.push_back(nei);
}
}
std::cout << "size, " << dig._nei.size() << "!\n";
}
}
}
int getNumberOfPaths(int digit, int n) {
std::cout << "paths, " << digit << n << "!\n";
if (n == 0 ) {
return 1;
}
int paths = 0;
Digit& dig = digits[digit];
for (unsigned int i=0 ; i < dig._nei.size(); i++) {
int neiDigit = dig._nei[i];
paths += getNumberOfPaths(neiDigit, n-1);
}
return paths;
}
};
int findNumberOfPaths(int digit, int n) {
Paths p;
p.createDigitsPaths();
return p.getNumberOfPaths(digit, n);
}
#include <iostream>
#include <string>
#include <vector>
#include <unordered_map>
static const int COLS = 3;
static const int ROWS = 4;
struct Digit {
std::vector<int> _nei;
};
struct Paths {
std::unordered_map<int, Digit> digits;
int getNei(int* mat, int offSet1, int offSet2, int row, int col) {
row += offSet1;
col += offSet2;
int retVal = -1;
if (row >= 0 && row < ROWS && col >= 0 && col < COLS ) {
int off = row*COLS + col;
//std::cout << "row, " << row << " col, " << col<< " off, " << off << "!\n";
retVal = *(mat + off);
}
return retVal;
}
void createDigitsPaths() {
int matrix[ROWS][COLS] = {1,2,3,4,5,6,7,8,9,-1,0,-1};
for (int i=0; i<ROWS; i++) {
for (int j=0; j<COLS; j++) {
int num=matrix[i][j];
if (num <0 ) {
continue;
}
int* mat = (int*) matrix;
Digit& dig = digits[num];
std::cout << "num, " << num << "!\n";
for (int offSet1 = 1; offSet1 <=2; offSet1++ ) {
int offSet2 = 2 - offSet1+1;
int nei = getNei(mat, offSet1, offSet2, i, j);
if (nei >= 0 ) {
std::cout << "nei1, " << nei << "!\n";
dig._nei.push_back(nei);
}
nei = getNei(mat, offSet1, -offSet2, i, j);
if (nei >= 0 ) {
std::cout << "nei2, " << nei << "!\n";
dig._nei.push_back(nei);
}
nei = getNei(mat, -offSet1, offSet2, i, j);
if (nei >= 0 ) {
std::cout << "nei3, " << nei << "!\n";
dig._nei.push_back(nei);
}
nei = getNei(mat, -offSet1, -offSet2, i, j);
if (nei >= 0 ) {
std::cout << "nei4, " << nei << "!\n";
dig._nei.push_back(nei);
}
}
std::cout << "size, " << dig._nei.size() << "!\n";
}
}
}
int getNumberOfPaths(int digit, int n) {
std::cout << "paths, " << digit << n << "!\n";
if (n == 0 ) {
return 1;
}
int paths = 0;
Digit& dig = digits[digit];
for (unsigned int i=0 ; i < dig._nei.size(); i++) {
int neiDigit = dig._nei[i];
paths += getNumberOfPaths(neiDigit, n-1);
}
return paths;
}
};
int findNumberOfPaths(int digit, int n) {
Paths p;
p.createDigitsPaths();
return p.getNumberOfPaths(digit, n);
}
Here is the C++ solution for this problem:
1. We build the graph
2. Then we traverse the graph from the starting node ("keypad key") to each node and sum its adjacent count (we do this recursively). Then we do this for each adjacent recursively
struct KeypadNode {
int number;
std::vector<int> adjacents;
KeypadNode(int num, const std::vector<int>& adj)
: number(num)
, adjacents(adj)
{
}
};
std::unordered_map<int, KeypadNode> build_keypad_graph()
{
// 1 2 3
// 4 5 6
// 7 8 9
// 0
std::unordered_map<int, KeypadNode> g;
g.insert(std::make_pair(0, KeypadNode(0, { 4, 6 })));
g.insert(std::make_pair(1, KeypadNode(1, { 8, 6 })));
g.insert(std::make_pair(2, KeypadNode(2, { 7, 9 })));
g.insert(std::make_pair(3, KeypadNode(3, { 4, 8 })));
g.insert(std::make_pair(4, KeypadNode(4, { 3, 9, 0 })));
g.insert(std::make_pair(5, KeypadNode(5, {})));
g.insert(std::make_pair(6, KeypadNode(6, { 1, 7, 0 })));
g.insert(std::make_pair(7, KeypadNode(7, { 2, 6 })));
g.insert(std::make_pair(8, KeypadNode(8, { 1, 3 })));
g.insert(std::make_pair(9, KeypadNode(9, { 2, 4 })));
return g;
}
void get_keypad_knight_path_count(
const std::unordered_map<int, KeypadNode>& G, int initialDigit, int length, int& pathCount)
{
if(length == 0) return;
const KeypadNode& key = G.find(initialDigit)->second;
pathCount += key.adjacents.size();
std::for_each(key.adjacents.begin(), key.adjacents.end(),
[&](int adj) { get_keypad_knight_path_count(G, adj, length - 1, pathCount); });
}
int main(int argc, char** argv)
{
// print_task_order();
{
std::unordered_map<int, KeypadNode> G = build_keypad_graph();
int pathCount = 0;
get_keypad_knight_path_count(G, 6, 2, pathCount);
std::cout << "There are " << pathCount << " possible paths" << std::endl;
}
}
def get_count(digit, n):
digit_mapping = {
0: [4, 6],
1: [6, 8],
2: [7, 9],
3: [4, 8],
4: [3, 9],
5: [],
6: [2, 7, 0],
7: [2, 6],
8: [1, 3],
9: [4, 2]
}
num_distinct_digits = len(digit_mapping)
table = []
for i in xrange(n + 1):
table.append([0] * num_distinct_digits)
for i in xrange(num_distinct_digits):
table[1][i] = len(digit_mapping[i])
for row_index in xrange(2, n + 1):
for digit_index in xrange(num_distinct_digits):
for adjacent_digit_index in digit_mapping[digit_index]:
table[row_index][digit_index] += table[row_index - 1][adjacent_digit_index]
return table[n][digit]
def get_count(digit, n):
digit_mapping = {
0: [4, 6],
1: [6, 8],
2: [7, 9],
3: [4, 8],
4: [3, 9],
5: [],
6: [2, 7, 0],
7: [2, 6],
8: [1, 3],
9: [4, 2]
}
num_distinct_digits = len(digit_mapping)
table = []
for i in xrange(n + 1):
table.append([0] * num_distinct_digits)
for i in xrange(num_distinct_digits):
table[1][i] = len(digit_mapping[i])
for row_index in xrange(2, n + 1):
for digit_index in xrange(num_distinct_digits):
for adjacent_digit_index in digit_mapping[digit_index]:
table[row_index][digit_index] += table[row_index - 1][adjacent_digit_index]
return table[n][digit]
public static void main(String[] args){
int n = findNumberOfPaths(1, 4);
System.out.println(n);
}
static int findNumberOfPaths(int digit, int step){
int[][] keypad = new int[4][3];
for(int i = 0; i < 3; i++){
for(int j = 0; j < 3; j++){
keypad[i][j] = i*3 + j+1;
}
}
keypad[3][0] = -1;
keypad[3][2] = -1;
keypad[3][1] = 0;
int x = -1;
int y = -1;
if(digit == 0){
x = 3;
y = 1;
}else{
x = digit / 3;
y = (digit % 3) -1;
}
return findNumberOfPaths(keypad, x, y, step, 0);
}
static int findNumberOfPaths(int[][] keypad, int x, int y, int step, int count){
if(x < 0 || y < 0 || x > 3 || y > 2)
return count;
if(keypad[x][y] < 0)
return count;
if(step == 0)
return count+1;
int[] mx = {2, 2, -2, -2, -1, 1, 1, -1};
int[] my = {-1, 1, 1, -1, 2, 2, -2, -2};
for(int i = 0; i < 8; i++){
count = findNumberOfPaths(keypad, x+mx[i], y+my[i], step-1, count);
}
return count;
}
public int[][] moves = new int[10][]{
new int[]{4, 6},
new int[]{6, 8},
new int[]{7, 9},
new int[]{4, 8},
new int[]{0, 3, 9},
new int[]{},
new int[]{0, 1, 7},
new int[]{2},
new int[]{1, 3},
new int[]{2}
};
public int paths = 0;
public int findNumberOfPaths(int digit, int steps) {
goOnPaths(digit, steps, 0);
return paths;
}
public void goOnPaths(int digit, int steps, int step) {
if (step == steps) {
paths++;
return;
}
for (int move : moves[digit]) {
goOnSteps(move, steps, step + 1);
}
}
I am not sure, moving to zero from 4,6
would be allowed since there is no board below 7 or 9.
Yes, example mention's it, but I am confused,
since the emphasis is on finding the number of the paths.
That being said, if 4 and 6 appears in the path,
now, the next will have three options.
that basically means traverse once through the graph for the number of the nodes for
each none 4 and 6 node put a factor of 3 everything else 2.
I am not sure a brute force answer of traversing through
counting is what interview is looking for
- amistaad September 05, 2017