Facebook Interview Question for Software Engineers


Country: United States




Comment hidden because of low score. Click to expand.
2
of 2 vote

adj = {}
adj[1] = [6,8]
adj[2] = [9,7]
adj[3] = [4,8]
adj[4] = [3,9,0]
adj[5] = []
adj[6] = [1,7,0]
adj[7] = [6,2]
adj[8] = [3,1]
adj[9] = [4,2]
adj[0] = [6,4]

def findNumPaths(digit, step):
    neighbors = adj[digit]
    if step == 1:
        return len(neighbors)
    count = 0
    for neighbor in neighbors:
        count+= findNumPaths(neighbor, step-1)
    return count

print(findNumPaths(5,20))

- amistaad September 05, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

@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

- undefined September 04, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

@majia168 - please define what a path is ? For example - a knight may choose to move between 4 and 9 and back again ( and again) and form a path of any length.

- Makarand September 04, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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)

- Chris September 04, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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));
    }
}

- learnsomething247 September 05, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#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);
}

- Jay September 05, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#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);
}

- jay September 05, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
    }
}

- PenChief September 05, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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]

- codesolver September 07, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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]

- codesolver September 07, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
  }

- sudip.innovates September 25, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

def find_paths_count(i, j, n):
	if n == 0:
		return 0
	p = 0
	for m1 in [-2, -1, 1, 2]:
		for m2 in [-2, -1, 1, 2]:
			if math.abs(m1) != math.abs(m2) and 
				i + m1>= 0 and i + m1 < 4 and 
				j + m2>= 0 and j + m2 < 3 and 
				(i + m1 !=3 or j + m2 == 1):
				p = p + find_paths_count(i + m1, j + m2, n-1)

- Alireza September 27, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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);
	}
}

- Vova January 26, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.
0
of 0 votes

"except 5 every digits has only 2 adjacent nodes..."

uhh...what about 4 and 6?

- rando September 06, 2017 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- codemerlin September 06, 2017 | Flag


Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Learn More

Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More