Facebook | Phone screen | Shortest Path with Obstacles
Anonymous User
6277

Facebook Phone Interview Question.
I couldn't solve the problem of enumerating the path itself. Please share your working solution if you figure it out.

Given a 2D matrix where some of the elements are filled with 1 and the rest of the elements are filled with X, except 2 elements, of which one is S (start point) and E (endpoint). Here X means you cannot traverse to that particular point. From a cell you can either traverse to left, right, up or down. Given two points in the matrix find the shortest path between these points.
For example, if the matrix is
1 1 1 1 1
S 1 X 1 1
1 1 1 1 1
X 1 1 E 1
1 1 1 1 X

One of the shortest paths (from E to S both exclusive) is: [(3, 2), (3, 1), (2, 1), (2, 0)]. Return null if there is no path between S and E.

Comments (12)