## Amazon Interview Question for SDE1s

• 1
of 1 vote

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

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.length && maze[i][j+1]) 	// move right
stk.push(new Node(i, j+1, m, n, this));
return stk;
}
}``````

Comment hidden because of low score. Click to expand.
0

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.

Comment hidden because of low score. Click to expand.
0

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

Comment hidden because of low score. Click to expand.
0

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

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

Comment hidden because of low score. Click to expand.
0

``int cols = matrix.length;``

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.

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