## Facebook Interview Question for Software Developers

• 0

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 - end) + abs(start - end)

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 == house:
distance_to_house = top
break

d_v = top + 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

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 - end) + abs(start - end) * 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 == house: # reached the house?
distance_to_house = top # reached house
break
explored[top] = -1 # explored the node (coordinate)

d_v = top + 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('')

# 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][pos] = 'T'

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

self.start = self._get_random_unused_coordinate()
self.matrix[self.start][self.start] = '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('')

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

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

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

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

}

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?

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.

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``````

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.

### 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.