Google Interview Question for Software Engineer / Developers


Country: United States
Interview Type: In-Person




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

DFS is a natural selection for searching a maze.

- Murali Mohan January 21, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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?

- Guy January 21, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- Amiad February 09, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

We can use bellman-ford algoritham for unweighted graph..
please correct me if i am wrong

- SUMIT KESARWANI January 16, 2015 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

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

- Alessandro Sena January 21, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

My question is for a graph like the following, how do we retrieve the adjacent list? 1 is passable, 0 is wall and 3 is our destination. This is a 2d array matrix, not an adjacent matrix.
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

- Guy January 21, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- Dave January 21, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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() + " -> ");
		}
	}

}

- DevGuy January 22, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- DevGuy January 22, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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() + " -> ");
		}
	}

}

- DevGuy January 22, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Use a Dijkstra and on encountering a wall at a position make the distance to that position as infinity or do not add it to heap for consideration.

- Anonymous January 24, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

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

- alex January 21, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
2
of 2 votes

This looks like a DFS to me though. I don't think bfs should recursively call itself, but rather use a queue and while loop to walk through the matrix.

- Guy January 21, 2014 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

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

- DevGuy January 21, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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?

- Guy January 21, 2014 | Flag


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