Amazon Interview Question for SDE1s


Team: Machine learning
Country: India
Interview Type: Phone Interview




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

I would probably propose three different solutions: (i) DFS implemented via stack, (ii) BFS adn finally (iii) A* (Best first search) implemented via priority queue. An addmissible heuristic for A* could be for instance Manhattan distance or Euclidean distance.

An eaxmple of A* is shown below:

public Iterable<Node> findPath(boolean[][] maze, int p, int q) {
	int N = maze.length;
	int M = maze.length[0];
	minPQ<Node> q = minPQ<Node>();
	p = N-1-p;	// convert to top left origin
	q.add(new Node(N-1, M-1, p, q, null));
	
	// A* search
	Node curr = null;
	while (!q.isEmpty()) {
		curr = q.remove();
		if (curr.i == p && curr.j == q) 	// is goal
			break;
		for (Node n : curr.adj(maze))
			q.add(n);	
	}

	if (curr.i != p || curr.j != q)		return null;
	
      // Path reconstruction
	Stack<Node> stk = new Stack<Node>();
	while (curr.parent != null) {
		stk.push(curr);
		curr = curr.parent;
	}

	return stk;	
}

private class Node implements Comparable<Node> {
	public int i,j,m,n;
	public double priority;
	public Node parent;

	public Node(int i, int j, int m, int n, Node p) {
		this.i = i; 		// current position
		this.j = j;
		this.m = m; 	  // goal position
		this.n = n;
		this.parent = p;
		this.priority = Math.sqrt((i-m)*(i-m)+(j-n)*(j-n));
	}

	public int compaterTo(Node other) {
		if (this.priority < other.priority) 		return -1;
		if (this.priority > other.priority) 		return +1;
		return 0;
	}

	public Iterable<Node> adj(boolean [][] maze) {
		Stack<Node> stk = new Stack<Node>();
		if (i-1 >= 0 && maze[i-1][j]) 	 			// move up
			stk.push(new Node(i-1, j, m, n, this));
		if (j+1 < maze[0].length && maze[i][j+1]) 	// move right
			stk.push(new Node(i, j+1, m, n, this));
		return stk;
	}
}

- autoboli January 19, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Great solution. But A* is overkill in this case, since there'd be no edges with cost more than 1. BFS would then give the shortest path with lower complexity than Dijkstra and A*, if I recall correctly.

Backtracking also works well.

- Victor January 19, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Not sure about Dijkstra but I think A* should be more effective than BFS even in this simple case with equal edge weights. Well, A* is just informed version of BFS so what is happening in this case is that nodes closer to the goal node are enqueued first which avoids exploring the whole state tree. Hence, less iterations is needed even in this simple case with up/right steps. Nice thing about this problem is that admissible heuristics is straightforward, I wanted to rebrush the best first search :)

- autoboli January 19, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Yes, you are correct. A* does seem to the better. Also the problem provides a very good heuristic, which makes things easier.

- Victor January 20, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Class FindMatrixPath{

	public boolean findMatrixPath(int[][] matrix, int x1, int y1, int x2, int y2){
		if(matrix == null || matrix.length == 0 || matrix[0].length == 0 )
			return false;

		int rows = matrix.length;
		int cols = matrix.length;

		boolean visited[][] = new boolean[rows][cols];
		Stack<Integer> stack = new Stack<Integer>();

		stack.push(x1*cols + y1);

		while(!stack.isEmpty()){

			int temp = stack.pop();
			int x = temp / cols;
			int y = temp % cols;

			if(x == x2 && y == y2)
				return true;

			if(!visited[x][y]){

				visited[x][y] = true;

				//push right element
				if( y < cols - 1 && matrix[x][y+1] == 1){
					stack.push( x * cols + y + 1);
				}	
				//push up element
				if( x > 0 && matrix[x - 1][y] == 1){
					stack.push( (x - 1) * cols + y);
				}

			}
		}

		return false;
	}

}

DFS, please let me know if you find any mistakes.

- The Interview January 23, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

int cols = matrix[0].length;

- The Interview January 23, 2015 | 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