Amazon Interview Question
SDE1sTeam: Machine learning
Country: India
Interview Type: Phone Interview
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.
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 :)
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.
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:
- autoboli January 19, 2015