Google Interview Question
Software Engineer / DevelopersCountry: United States
Interview Type: In-Person
So for a matrix like 1,0,0,0,0,0
1,1,1,1,1,1
0,1,0,0,0,1
0,1,0,0,0,1
1,1,1,0,1,3
0,0,1,1,1,0
I know how to solve it with DFS, but how should we use Dijkstra to find the shortest path?
DFS will find a path but not necessarily the shortest one.
BFS will do the job in case that there is no cost (wight) for moving from one room (node) to the other (or in the case where all movements have the same cost).
Dijkstra will be the one if there is a different cost for moving from one room (node) to the other.
Since in your graph all the edges have the same weight, you can use a BFS to get the shortest path as well with cost O(|E|+|V|).
Dijkstra is for finding the short path on a weighted graph, that would apply if the edges have weights, otherwise you can use BFS on an unweighted graph. A maze could either be weighted or not. Weighted if you treat long paths without decision points as a longer edge or unweighted if you treat the same as multiple edges. If you have a lot of long paths like that a weighted graph would be smaller in size this way (kinda how some compression works).
kelvin198897, you should have provided this matrix detail about the maze earlier ;)
Also, BFS will reveal the shortest path for graph which has edges of same weight (as is the case here), missed to notice that earlier :)
Here is an attempt to solve this in Java. I have assumed that only row or column movements are allowed, no diagonal ones. Also, it is important to notice that while nodes are being discovered - for current node, only the next one in its row and next one in its column matter (diagonal ones not allowed, previous ones in row and column must have already been discovered). Also, start is at (0,0).
public class MazeGraphBuilder {
public static DirectedGraph<Integer> buildDirectedGraphForMaze(int[][] data) {
Map<Node<Integer>, List<Node<Integer>>> adjacencyLists = new HashMap<Node<Integer>, List<Node<Integer>>>();
int numRows = data.length;
int numCols = data[0].length;
for (int row = 0; row < numRows; row++) {
for (int col = 0; col < numCols; col++) {
if (data[row][col] == 1 || data[row][col] == 3) {
Node<Integer> node = new MazeNode(row, col, data[row][col]);
adjacencyLists.put(node, new ArrayList<Node<Integer>>());
if (isNextCellInThisRowValid(data, numCols, row, col)) {
adjacencyLists.get(node).add(new MazeNode(row, col + 1, data[row][col + 1]));
}
if (isNextCellInThisColumnValid(data, numRows, row, col)) {
adjacencyLists.get(node).add(new MazeNode(row + 1, col, data[row + 1][col]));
}
}
}
}
return new DirectedGraph<Integer>(new AdjacencyLists<Integer>(adjacencyLists));
}
private static boolean isNextCellInThisColumnValid(int[][] data, int numRows, int row, int col) {
return (row < numRows - 1) && (data[row + 1][col] == 1 || data[row + 1][col] == 3);
}
private static boolean isNextCellInThisRowValid(int[][] data, int numCols, int row, int col) {
return (col < numCols - 1) && (data[row][col + 1] == 1 || data[row][col + 1] == 3);
}
public static Stack<MazeNode> findShortestPathInMaze(int[][] data) {
Map<Node<Integer>, Integer> distances = new HashMap<Node<Integer>, Integer>();
DirectedGraph<Integer> graph = buildDirectedGraphForMaze(data);
for (Node<Integer> node : graph.getNodes()) {
distances.put(node, -1); // -1 to represent invalid or infinity
}
MazeNode source = new MazeNode(0, 0, data[0][0]);
distances.put(source, 0);
Queue<MazeNode> queue = new LinkedList<MazeNode>();
queue.offer(source);
boolean found = false;
MazeNode destination = null;
while (!queue.isEmpty()) {
MazeNode node = queue.remove();
for (Node<Integer> neighbour : graph.getNeighbours(node)) {
((MazeNode) neighbour).setParent(node); // keeps track of path
if (distances.get(neighbour) == -1) { // unexplored neighbour
queue.offer((MazeNode) neighbour);
distances.put(neighbour, distances.get(node) + 1);
if (((MazeNode) neighbour).isDestinationNode()) {
found = true;
destination = (MazeNode) neighbour;
break;
}
}
if (found) {
break;
}
}
if (found) {
break;
}
}
Stack<MazeNode> path = new Stack<MazeNode>();
MazeNode currNode = destination;
while (currNode != null) {
path.push(currNode);
currNode = currNode.getParent();
}
return path;
}
public static void main(String[] args) {
// 1,1,1,1,1,1
// 0,1,0,0,0,1
// 0,1,0,0,0,1
// 1,1,1,0,1,3
// 0,0,1,1,1,0
int[][] data = new int[][] { { 1, 1, 1, 1, 1, 1 }, { 0, 1, 0, 0, 0, 1 }, { 0, 1, 0, 0, 0, 1 }, { 1, 1, 1, 0, 1, 3 },
{ 0, 0, 1, 1, 1, 0 } };
Stack<MazeNode> shortestPath = findShortestPathInMaze(data);
System.out.println("Shortest Path is,");
while (!shortestPath.isEmpty()) {
System.out.print(shortestPath.pop() + " -> ");
}
}
}
However, the complexity will now be O(MN) where M is #rows, N is #cols in the input matrix.
Maybe, there is still a simpler method relying on some trick to bring it down, but cannot spot it as of now.
Sorry, that solution should use an undirected graph. And, we can do much better than that solution, we don't need to build the graph first. We can do the BFS straightaway and note down the path. Here is a working solution.
public class MazeGraphBuilder {
private static Collection<? extends Node<Integer>> getNeighbours(MazeNode node, int[][] data) {
List<Node<Integer>> neighbours = new ArrayList<Node<Integer>>();
int row = node.getRow(), col = node.getCol();
int numRows = data.length;
int numCols = data[0].length;
if (col > 0 && (data[row][col - 1] == 1 || data[row][col - 1] == 3)) {
neighbours.add(new MazeNode(row, col - 1, data[row][col - 1]));
}
if (row > 0 && (data[row - 1][col] == 1 || data[row - 1][col] == 3)) {
neighbours.add(new MazeNode(row - 1, col, data[row - 1][col]));
}
if (col < numCols - 1 && (data[row][col + 1] == 1 || data[row][col + 1] == 3)) {
neighbours.add(new MazeNode(row, col + 1, data[row][col + 1]));
}
if (row < numRows - 1 && (data[row + 1][col] == 1 || data[row + 1][col] == 3)) {
neighbours.add(new MazeNode(row + 1, col, data[row + 1][col]));
}
return neighbours;
}
public static Stack<MazeNode> findShortestPathInMaze(int[][] data) {
Map<Node<Integer>, Integer> distances = new HashMap<Node<Integer>, Integer>();
MazeNode source = new MazeNode(0, 0, data[0][0]);
distances.put(source, 0);
Queue<MazeNode> queue = new LinkedList<MazeNode>();
queue.offer(source);
boolean found = false;
MazeNode destination = null;
while (!queue.isEmpty()) {
MazeNode node = queue.remove();
for (Node<Integer> neighbour : getNeighbours(node, data)) {
if (!distances.containsKey(neighbour)) { // unexplored neighbour
((MazeNode) neighbour).setParent(node); // keeps track of path
queue.offer((MazeNode) neighbour);
distances.put(neighbour, distances.get(node) + 1);
if (((MazeNode) neighbour).isDestinationNode()) {
found = true;
destination = (MazeNode) neighbour;
break;
}
}
if (found) {
break;
}
}
if (found) {
break;
}
}
Stack<MazeNode> path = new Stack<MazeNode>();
MazeNode currNode = destination;
while (currNode != null) {
path.push(currNode);
currNode = currNode.getParent();
}
return path;
}
public static void main(String[] args) {
// 1,1,1,1,1,1
// 0,1,0,0,0,1
// 0,1,0,0,0,0
// 1,1,1,0,1,3
// 0,0,1,1,1,0
int[][] data = new int[][] { { 1, 1, 1, 1, 1, 1 }, { 0, 1, 0, 0, 0, 1 }, { 0, 1, 0, 0, 0, 0 }, { 1, 1, 1, 0, 1, 3 },
{ 0, 0, 1, 1, 1, 0 } };
Stack<MazeNode> shortestPath = findShortestPathInMaze(data);
System.out.println("Shortest Path is,");
while (!shortestPath.isEmpty()) {
System.out.print(shortestPath.pop() + " -> ");
}
}
}
You may represent maze in a two dimensional array. BFS should be applicable to find the shortest path from source to the destination. Depending how you can move through the maze, simple iterative approach can be implemented. Suppose right, down and diagonal - distance for each cell from source will be min(a[i-1][j-1], a[i][j-1], a[i-1][j])+1. Another alternative is recursive approach.
Sample code for recursive BFS
void bfs(int [][]a, int n, int i, int j)
{
if (i>=a.length || j>=a[0].length) return ;
a[i][j]=n+1;
bfs(a, n+1, i, j+1);
bfs(a, n+1, i+1, j);
bfs(a, n+1, i+1, j+1);
}
As far as I remember, mazes are generally solved using DFS. In this problem, there are 2 parts (i) find the destination/exit in the maze (ii) find the shortest path from start to destination.
If there is no other information available about the maze, I think we can make 2 assumptions (i) the number of edges in the path is its length (ii) there is only one exit/destination in the maze.
Using the above assumption, a simple solution is: (i) find destination using DFS (ii) apply Dijkstra's algorithm to find shortest path.
Total runtime = O((|V|+|E|)*log|V|) ... Dijkstra's runtime dominates DFS's runtime
DFS is a natural selection for searching a maze.
- Murali Mohan January 21, 2014