Facebook Interview Question for Software Developers


Team: Infrastructure
Country: United States
Interview Type: In-Person




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

If it was one start and one end-point in a graph one would do
BFS either from start or two BFSs from start and end which is
considerably faster (one origin vs. two origin)

But this question is for multiple end-points from a single
start in a map. Let's assume one can go left, right, up, down
(from 0,0 to 1,1 is two steps, not one --> manhatten distance)

The problem with BFS on a map is, that it will explore into all
direction with equal priority which builds up a big frontier
very quickly and explore therefore a lot of space. A* helps here
because it will introduce a heuristic that will pull the
exploration to the target (similar like hill climbing, with
similar issues). If the heuristic is guaranteed to not over-
estimate the effective distance it will find the shortest path
much faster. If the heuristic overestimates, it gets faster
(explores less left and right) but is not guaranteed to find
the shortest path.

The question with many destinations (houses) and a single
start, what is the best approach?

1. Single origin BFS vs. BFS originating at all houses and start:
if many houses form a narrow cluster in the map and the start is
far away, that's the best case for single origin because it will
more or less discover all houses together.
But the effort for single origin grows exponentially with the
distance from origin as the frontier advances vs. a factor for
each house. Mutliple origin is faster.

2. Multi origin vs A*
A* can't be done starting from start and end because there is no
guarantee the two frontiers will meet and form a shortest path.
It will depend on the size of the map and the amount of trees. A*
in worst case is worse than BFS due to the priority queues.
One can construct an example that is significant slower with A*.

the core of the A* version is (fully commented version further below):

def find_shortest_path_to_all(map):
    def estimated_distance(start, end): 
        return abs(start[0] - end[0]) + abs(start[1] - end[1])

    tot_distance = 0
    for house in map.houses:
        distance_to_house = -1
        explored = {}
        queue = [(0, 0, map.start)] 
        while queue:
            top = heapq.heappop(queue)
            if top[2] == house:
                distance_to_house = top[1]
                break

            for v in map.get_adjacents(top[2]):
                d_v = top[1] + 1 
                d_v_tot = d_v + estimated_distance(v, house) 
                current_d_to_v = explored.get(v) 
                if current_d_to_v is None or current_d_to_v > d_v: 
                    explored[v] = d_v 
                    heapq.heappush(queue, (d_v_tot * 100000 - len(queue), d_v, v)) 
            
        if distance_to_house == -1:
            return -1
        else:
            tot_distance += distance_to_house

    return tot_distance

Below an implemenation using a simple A* implementation printing the map and explored
coordinates.

in python 3

import random
import heapq

def find_shortest_path_to_all_astar(map):
    def estimated_distance(start, end):
        return abs(start[0] - end[0]) + abs(start[1] - end[1]) * 1 # replace 1 with 2 to see effect when overestimating

    tot_distance = 0
    for house in map.houses:                
        distance_to_house = -1
        explored = {}
        queue = [(0, 0, map.start)] # start-point, with highest prio and distance 0 from origin (start)
        while queue:
            top = heapq.heappop(queue) # most promising option to further explore
            if top[2] == house: # reached the house? 
                distance_to_house = top[1] # reached house
                break
            explored[top[2]] = -1 # explored the node (coordinate)

            for v in map.get_adjacents(top[2]):
                d_v = top[1] + 1 # distance to next node v = distance to current + 1
                d_v_tot = d_v + estimated_distance(v, house) # distance to v + estimated distance to house
                visit_d = explored.get(v)  # check if already explored or placed in queue for exploring
                if visit_d is None or visit_d > d_v: # only if we can reach with shorter distance
                    explored[v] = d_v # distance needed to reach v
                    heapq.heappush(queue, (d_v_tot * 100000 - len(queue), d_v, v)) 
                    # - len(...): is a trick to prefer recently added coordinates over existing with same estimate to house, this will 
                    # force the algorithm to stay with a branch instead of going through all branches of same estimated distance 
                    # and exploring them in parallel... 
                                
        if distance_to_house == -1:
            print('cant reach house {0}, map:'.format(house))
            map.print(explored)
            print('')
            return -1 # abort, return -1
        else:
            tot_distance += distance_to_house
            print('{0} to reach house {1}, map:'.format(distance_to_house, house))
            map.print(explored)
            print('')            
    return tot_distance

# represents the map (houses and trees)
class Map:
    # generates a reproducable, random map
    def __init__(self, m, n, no_trees, no_houses):
        self.m = m
        self.n = n
        self.matrix = [[' ' for j in range(n)] for i in range(m)]
        self.houses = []
        random.seed(1317)
        
        for i in range(no_trees):
            pos = self._get_random_unused_coordinate()
            self.matrix[pos[0]][pos[1]] = 'T'

        for i in range(no_houses):
            pos = self._get_random_unused_coordinate()
            self.houses.append(pos)
            self.matrix[pos[0]][pos[1]] = 'H'
        
        self.start = self._get_random_unused_coordinate()
        self.matrix[self.start[0]][self.start[1]] = 'S'

    def _get_random_unused_coordinate(self):
        while True:
            x = random.randrange(0, self.m)
            y = random.randrange(0, self.n)
            if self.matrix[x][y] == ' ':
                return (x, y)

    def print(self, explored=None):
        for y in range(self.n):      
            for x in range(self.m):
                if self.matrix[x][y] == ' ':
                    state = explored.get((x,y))
                    if state == -1:
                        print('e', end='') # explored
                    elif state is not None:
                        print('ยด', end='') # in the queue but not explored
                    else:
                        print(' ', end='')
                else:
                    print(self.matrix[x][y], end='')
            print('')        

    def get_adjacents(self, pos):
        adj = []
        for d in [(0,1),(0,-1),(1,0),(-1,0)]:
            nx = pos[0] + d[0]
            ny = pos[1] + d[1]
            if nx >= 0 and ny >=0 and nx < self.m and ny < self.n and self.matrix[nx][ny] != 'T':
                adj.append((nx, ny))
        return adj


m = Map(80, 25, 150, 5)
find_shortest_path_to_all_astar(m)

- Chris July 06, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

@sxs155933: Dijkstra is good on graphs with a weight function that will result in different positive weights for edges. if weights are always the same, Dijkstra isn't helping, it's actually just an over complicated BFS - so it doesn't hurt either, except maybe of the performance hit of the heap in the prio queue... A* with its heuristics is a natural enhancement of Dijkstra because it does not only look at the already explored paths an pick the shortest of those, but it does as well "guess" the unexplored and use that hint as well for selecting the best node. That's all the magic... I mean if you remove all the boilerplate and comments from my code above, it's maybe 10 lines of code... and once you understand it, it kind of hurts seeing people runing BFS or Dijkstra on a map problem... that's why I tried to print the map with the explored nodes, compare it to BFS, you'll be surprised.
But anyway, for the interviews you probably don't need it, so it's a question on how to optimize your personal strategy

- Chris July 17, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

Here's my Java solution, it makes a BFS going through all the discovered coordinates that are accessible remembering how many steps have been taken to get there.

public static int minDistancesSumToHouses(char[][] map, int x, int y) {
    int n = map.length;
    int[][] distances = new int[n][n]; // hold the min distance from (x,y) to each coordinate

    for ( int i = 0; i < n; ++i ) {
        for (int j = 0; j < n; ++j) {
            distances[i][j] = -1; // initialize them as unreachable with distance -1
        }
    }

    List<Coord> toVisit = new LinkedList<>(); // list of coordinates I will be visiting next iteration
    toVisit.add(new Coord(x, y)); // start with the starting position (x,y)
    distances[x][y] = 0; // distance to itself is 0
    int level = 0; // how many steps have I walked up to this point
    int result = 0; // sum of all the min distances to each house

    while ( !toVisit.isEmpty() ) { // stop when there are no more points available to visit
        List<Coord> newToVisit = new LinkedList<>(); // discovered coordinates that we will visit next
        for ( Coord visited : toVisit ) {
            int i = visited.x;
            int j = visited.y;
            if ( distances[i][j] < 0 ) { distances[i][j] = level; } // non visited coordinate
            else { distances[i][j] = Math.min(distances[i][j], level); }
            if ( 'H' == map[i][j] ) { result += distances[i][j]; } // found a house, add its distance to the result
            map[i][j] = '*'; // mark the coordinate as visited

            Coord left = toLeft(visited);
            Coord right = toRight(visited);
            Coord up = toUp(visited);
            Coord down = toDown(visited);

            if ( canMoveTo(map, left) ) { newToVisit.add(left); }
            if ( canMoveTo(map, right) ) { newToVisit.add(right); }
            if ( canMoveTo(map, up) ) { newToVisit.add(up); }
            if ( canMoveTo(map, down) ) { newToVisit.add(down); }
        }
        level++; // at the next iteration we will have taken one more step
        toVisit = newToVisit;
    }

    return result;
}

// can I move to the target coordinate in the map
private static boolean canMoveTo(char[][] map, Coord target) {
    int n = map.length;
    int x = target.x;
    int y = target.y;

    if ( x < 0 || x >= n || y < 0 || y >= n ) {
        return false;
    }
    
    return map[x][y] != 'T' && map[x][y] != '*';
}

// move from src 1 space in a certain direction
private static Coord toLeft(Coord src) { return new Coord(src.x-1, src.y); }
private static Coord toRight(Coord src) { return new Coord(src.x+1, src.y); }
private static Coord toUp(Coord src) { return new Coord(src.x, src.y-1); }
private static Coord toDown(Coord src) { return new Coord(src.x, src.y+1); }

// convenience class to hold values x and y
private static class Coord { int x; int y; Coord(int x, int y) {this.x = x; this.y = y;}

}

- funk July 17, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

cant we use dijkistra algorithm for this question as it is directly single source shortest path question?

- sxs155933 July 17, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

The distance from a node to all it's adjacent nodes is always 1, dijkistra does solve the problem but all it does is a BFS search through all the nodes. If you were to program a solution using dijkistra I'd recommend skipping the algorithm to select the next node and just select any node within reach.

- funk July 17, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Time complexity O(n2) i.e. n square
Space complexity O(n)

Solution using simple recursion to find distance from each house to target:

import java.util.*;

class Main {
    static char[][] arr = {{'h','_','_','_'},{'_','t','_','t'},{'_','h','t','h'},{'t','h','_','t'}};
    static int[][] trav = new int[arr.length][arr.length];
    static int[][] distances = new int[arr.length][arr.length];
    static int finali=1,finalj=2; //position to find paths from

    public static void main(String[] args) {

        for(int i=0;i<arr.length;i++){
            //init traversed and distances arrays
            for(int k=0;k<distances.length;k++){
                Arrays.fill(distances[k],Integer.MAX_VALUE);
                Arrays.fill(trav[k],0);
            }
            for(int j=0;j<arr.length;j++){
                if(arr[i][j]=='h'){
                    trav[i][j]=1;
                    System.out.println("i:"+i+"|j:"+j+"|dist:"+finddistance(i,j,0));
                }
            }
        }

    }

    public static int finddistance(int r, int c, int sum){
        //reached point
        if(r==finali && c==finalj)return sum;

        //right
        int rightsum=Integer.MAX_VALUE;
        if((c+1)<arr.length && arr[r][c+1]!='t' && trav[r][c+1]!=1){
            trav[r][c+1]=1;
            rightsum=finddistance(r,c+1,sum+1);
        }
        
        //bottom
        int bottomsum=Integer.MAX_VALUE;
        if((r+1)<arr.length && arr[r+1][c]!='t'&& trav[r+1][c]!=1){
            trav[r+1][c]=1;
            bottomsum=finddistance(r+1,c,sum+1);
        }
        
        //left
        int leftsum=Integer.MAX_VALUE;
        if((c-1)>=0 && arr[r][c-1]!='t'&& trav[r][c-1]!=1){
            trav[r][c-1]=1;
            leftsum=finddistance(r,c-1,sum+1);
        }
        
        //top
        int topsum=Integer.MAX_VALUE;
        if((r-1)>=0 && arr[r-1][c]!='t'&& trav[r-1][c]!=1){
            trav[r-1][c]=1;
            topsum=finddistance(r-1,c,sum+1);
        }
        
        // System.out.println("r"+r+"|c:"+c+"| rightsum:"+rightsum+"|bottomsum:"+bottomsum+"|leftsum:"+leftsum+"|topsum:"+topsum);
        return Math.min(Math.min(rightsum,bottomsum),Math.min(leftsum,topsum));

    }
}

Input:

H _ _ _
_ T X T 
_ H T H
T H _ T

X -> target

Output:

i:0|j:0|dist:3
i:2|j:1|dist:6
i:2|j:3|dist:2147483647
i:3|j:1|dist:7

- krupen.ghetiya July 26, 2017 | Flag Reply


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