Facebook Interview Question
Software DevelopersTeam: Infrastructure
Country: United States
Interview Type: In-Person
@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
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;}
}
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.
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
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):
Below an implemenation using a simple A* implementation printing the map and explored
coordinates.
in python 3
- Chris July 06, 2017