Amazon Interview Question SDE-2s
Country: India
Interview Type: In-Person
can we assume:
1. starting point could be any co-ordinate (x,y)
2. exit refers to reaching boundary
3. valid path is 'littered' with 1's
?
Given a start and end point, this finds the shortest path using BFS. I start count at 1 instead of 0 (and subtract 1 from count at the end) to keep the counting of squares from being mistaken as open spaces (1s). Not entirely sure how to have it *only* print the correct path, though....
def maze_bfs(maze, current, end_point, count=1)
current_x, current_y = current[0], current[1]
count += 1
maze[current_x][current_y] = count
if current == end_point
puts "*** count = #{count - 1}"
maze.each do |array|
puts array.inspect
end
return
end
if current_x > 0 && maze[current_x - 1][current_y] == 1
maze_bfs(maze, [current_x - 1, current_y], end_point, count)
end
if current_y > 0 && maze[current_x][current_y - 1] == 1
maze_bfs(maze, [current_x, current_y - 1], end_point, count)
end
if current_x < maze[0].length - 1 && maze[current_x + 1][current_y] == 1
maze_bfs(maze, [current_x + 1, current_y], end_point, count)
end
if current_y < maze.length - 1 && maze[current_x][current_y + 1] == 1
maze_bfs(maze, [current_x, current_y + 1], end_point, count)
end
end
maze = [
[0,0,1,1,1,0,0,0,1,1],
[0,0,1,0,0,0,0,0,1,0],
[0,0,1,1,1,1,1,1,1,0],
[0,0,0,1,0,0,0,0,1,0],
[0,0,0,1,1,1,0,0,0,0],
[0,0,0,0,1,0,0,0,0,0],
[0,0,1,0,1,0,0,0,0,0],
[0,0,1,1,1,0,0,0,0,0],
[0,0,0,1,0,0,0,0,0,0],
[0,0,0,1,0,0,0,0,0,0]
]
>> maze_bfs maze, [0, 9], [9, 3]
[0, 0, 12, 13, 14, 0, 0, 0, 2, 1]
[0, 0, 11, 0, 0, 0, 0, 0, 3, 0]
[0, 0, 10, 9, 8, 7, 6, 5, 4, 0]
[0, 0, 0, 10, 0, 0, 0, 0, 1, 0]
[0, 0, 0, 11, 12, 1, 0, 0, 0, 0]
[0, 0, 0, 0, 13, 0, 0, 0, 0, 0]
[0, 0, 18, 0, 14, 0, 0, 0, 0, 0]
[0, 0, 17, 16, 15, 0, 0, 0, 0, 0]
[0, 0, 0, 17, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 18, 0, 0, 0, 0, 0, 0]
My solution, given a starting 'square':
-assign a value to every 'square', initially -1
-assign the starting square the value 0
-from the starting square, add the four surrounding squares iff they are within the matrix to a set to be visited next. However, if one of them is outside the matrix we are done and return the starting square as the path
-now in a loop at every stage visit all to be visited squares, assigning them the value of the current round, which is incremented every iteration. So the first time round squares are assigned 1, then 2 and so on. Don't visit squares which have been previously visited.
-repeat until you reach a square that is adjacent to a square outside the matrix. Then backtrack by from the current square choosing a square with a value that is curValue-1. So if we end up at 4, we look for a square with value 3, from there one with 2, then one with 1 and then we get back to the origin at 0. Return this path (well, you could reverse it first)
-if at any point we run out of squares to visit, there's no path
import java.util.HashSet;
import java.util.Set;
import java.util.Vector;
public class FindShortestMatrixPath {
/**
* @param args
*/
public static void main(String[] args)
{
// boolean [][] matrix =
// {
// {0, 0, 0, 0, 0},
// {0, 0, 1, 0, 0},
// {0, 1, 1, 0, 0},
// {0, 0, 1, 1, 0},
// {0, 0, 0, 1, 0}
// };
boolean [][] matrix =
{
{false, false, false, false, false},
{false, false, true, false, false},
{false, true, true, false, false},
{false, false, true, true, false},
{false, false, false, true, false}
};
Vector <Point> path = findShortestPath(matrix, 1, 2);
for(Point p : path)
{
System.out.print(p.strRep() + ", ");
}
System.out.println();
}
public static class Point
{
public int x, y;
public Point(int x, int y)
{
this.x = x;
this.y = y;
}
public String strRep() {
return "(" + x + ", " + y + ")";
}
public boolean insideBounds(int w, int h)
{
if(x < 0 || x >= w || y < 0 || y >= h)
return false;
return true;
}
public boolean atEdge(int w, int h)
{
if(x-1 < 0 || x+1 >= w || y-1 < 0 || y+1 >= h)
return true;
return false;
}
public Set <Point> getAdjacents(boolean[][] matrix, int [][] costs)
{
Set <Point> adj = new HashSet();
Point p = new Point(x+1, y);
if(p.insideBounds(matrix.length, matrix[0].length) && costs[x+1][y] == -1 && matrix[x+1][y])
adj.add(p);
p = new Point(x-1, y);
if(p.insideBounds(matrix.length, matrix[0].length) && costs[x-1][y] == -1 && matrix[x-1][y])
adj.add(p);
p = new Point(x, y+1);
if(p.insideBounds(matrix.length, matrix[0].length) && costs[x][y+1] == -1 && matrix[x][y+1])
adj.add(p);
p = new Point(x, y-1);
if(p.insideBounds(matrix.length, matrix[0].length) && costs[x][y-1] == -1 && matrix[x][y-1])
adj.add(p);
return adj;
}
}
public static Vector <Point> findShortestPath(boolean [][] matrix, int xStart, int yStart)
{
int [][] costs = new int[matrix.length][matrix[0].length];
costs[xStart][yStart] = 0;
for(int i = 0; i < matrix.length; i++)
{
for(int j = 0; j < matrix.length; j++)
{
costs[i][j] = -1;
}
}
Set <Point> nextToVisit = new HashSet();
nextToVisit.add(new Point(xStart, yStart));
int at = 0;
while(!nextToVisit.isEmpty())
{
Set <Point> newNextToVisit = new HashSet();
for(Point p : nextToVisit)
{
System.out.println("At " + p.strRep());
if(costs[p.x][p.y] == -1)
costs[p.x][p.y] = at;
if(p.atEdge(matrix.length, matrix[0].length))
{
System.out.println("Backtracking");
return backTrack(p, costs);
}
else
{
newNextToVisit.addAll(p.getAdjacents(matrix, costs));
}
}
at++;
nextToVisit = newNextToVisit;
}
return new Vector();
}
private static Vector<Point> backTrack(Point p, int [][] matrix)
{
Vector <Point> path = new Vector();
int curAt = matrix[p.x][p.y];
int xAt = p.x;
int yAt = p.y;
path.add(new Point(xAt, yAt));
while(curAt != 0)
{
if(xAt - 1 > 0 && matrix[xAt-1][yAt] == curAt-1)
{
xAt--;
}
else if(xAt + 1 < matrix.length && matrix[xAt+1][yAt] == curAt-1)
{
xAt++;
}
else if(yAt - 1 > 0 && matrix[xAt][yAt-1] == curAt-1)
{
yAt--;
}
else if(yAt + 1 > 0 && matrix[xAt][yAt+1] == curAt-1)
{
yAt++;
}
else
{
throw new RuntimeException("This should NOT happen");
}
path.add(new Point(xAt, yAt));
curAt--;
}
return path;
}
}
A typical recursive solution can be as :-
int func(int x,int y)
{
if(x==0 || y==0 || x==n-1 || y==n-1)
return 0;
else
{
int k=32767,l=32767,m=32767,n=32767;
if(x-1>=0 && a[x-1][y]==1)
k=func(x-1,y)+1;
if(x+1<n && a[x+1][y]==1)
l=func(x+1,y)+1;
if(y-1>=0 && a[x][y-1]==1)
m=func(x,y-1)+1;
if(y+1<n && a[x][y+1]==1)
n=func(x,y+1)+1;
return min(k,l,m,n);
}
}
But this will have overlapping subproblems. So a DP solution will be preferable. Working out for a DP solution.. :)
BFS via C# :
class Point
{
public int X { get; set; }
public int Y { get; set; }
}
public int FindTheShortestExit(byte[,] matrix, int n, int x, int y)
{
if (!(x >= 0 && y >= 0 && x < n && y < n))
{
throw new Exception("Invalid input data");
}
int[] dx = { 1, 0, 0, -1 };
int[] dy = { 0, 1, -1, 0 };
int[,] a = new int[n, n];
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
a[i, j] = int.MaxValue;
}
}
a[x, y] = 0;
int result = int.MaxValue;
Queue<Point> q = new Queue<Point>();
q.Enqueue(new Point { X = x, Y = y });
while (q.Count != 0)
{
Point curr = q.Dequeue();
if ((curr.X == 0 || curr.Y == 0 || curr.X == n - 1 || curr.Y == n - 1) && a[curr.X, curr.Y] + 1 < result)
{
result = a[curr.X, curr.Y] + 1;
}
for (int i = 0; i < 4; i++)
{
if (
curr.X + dx[i] >= 0 && curr.X + dx[i] < n &&
curr.Y + dy[i] >= 0 && curr.Y + dy[i] < n &&
matrix[curr.X + dx[i], curr.Y + dy[i]] == 1 &&
a[curr.X + dx[i], curr.Y + dy[i]] > a[curr.X, curr.Y] + 1)
{
q.Enqueue(new Point { X = curr.X + dx[i], Y = curr.Y + dy[i] });
a[curr.X + dx[i], curr.Y + dy[i]] = a[curr.X, curr.Y] + 1;
}
}
}
if (result == int.MaxValue)
{
return -1; // can't find exit
}
return result;
}
C++ code here:
#include<stdio.h>
#include<stdlib.h>
int st_row,st_col;
int end_row, end_col;
int min_path_length = 99999;
int a[6][6]= { {0,1,0,0,1,0},
{1,1,0,1,1,1},
{0,1,1,1,0,1},
{1,1,1,0,0,0},
{1,0,0,1,1,1},
{0,1,1,1,0,0},
};
#define N 6
int is_valid(int row, int col, int val)
{
return (a[row][col] && ( a[row][col]==1 || a[row][col] > val ));
} // end is_valid
int is_start(int row, int col)
{
return (row==st_row) && (col==st_col);
} // end is_start
void find_path( int row, int col )
{
// Check if border
if( row ==0 || row == N-1 || col == 0 || col == N-1 )
{
if( a[row][col] < min_path_length )
{ min_path_length = a[row][col];
end_row = row;
end_col = col;
}
return;
}
int new_len = a[row][col]+1;
// top ?
if( is_valid(row-1,col,new_len) && ! is_start(row-1,col) )
{
a[row-1][col] = new_len;
find_path(row-1, col);
}
// bottom
if( is_valid(row+1,col,new_len) && ! is_start(row+1,col))
{
a[row+1][col] = new_len;
find_path(row+1, col);
}
// left
if(is_valid(row,col-1,new_len) && ! is_start(row,col-1) )
{
a[row][col-1] = new_len;
find_path(row, col-1);
}
// right
if( is_valid(row,col+1,new_len) && ! is_start(row,col+1) )
{
a[row][col+1] = new_len;
find_path(row, col+1);
}
} // end find_path
void trace_path ( int r, int c )
{
printf("\n%d %d", r,c);
if(r== st_row && c==st_col)
return;
//top
if( r!=0 && a[r-1][c] == (a[r][c]-1) )
{
trace_path(r-1,c);
}
//bottom
else if( r!=N-1 && a[r+1][c] == (a[r][c]-1) )
{
trace_path(r+1,c);
}
//left
else if( c!=0 && a[r][c-1] == (a[r][c]-1) )
{
trace_path(r,c-1);
}
//right
else if( c!=N-1 && a[r][c+1] == (a[r][c]-1) )
{
trace_path(r,c+1);
}
} //end trace_path
void print_matrix( )
{
printf("\nPrinting matrix..");
for( int i=0; i< N; i++ )
{
printf("\n");
for(int j=0; j<N; j++ )
{
printf("%d ", a[i][j]);
}
}
} //end print_matrix
int main()
{
print_matrix();
st_row=2; st_col =3;
find_path(st_row,st_col );
print_matrix();
printf("\nTracing path..");
trace_path(end_row,end_col);
return 0;
}
Hello Guys,
Here is very simple, clean code to follow.
#include <iostream>
#include <queue>
using namespace std;
const char LEFT = 0x01;
const char RIGHT = 0x02;
const char DOWN = 0x04;
const char UP = 0x08;
class Cord{
public:
int _r, _c;
Cord(int r = 0, int c = 0) : _r(r), _c(c){}
};
bool isValid(int r, int c, int M, int N){
return (r >= 0 && r < M && c >= 0 && c < N);
}
bool isEdge(int r, int c, int M, int N){
return (r == 0 || c == 0 || r == M-1 || c == N-1);
}
int predecesor(int ra, int ca, int rb, int cb){
if(ca < cb)
return LEFT;
else if(ca > cb)
return RIGHT;
else if(ra < rb)
return UP;
else if(ra > rb)
return DOWN;
else
return -1;
}
void find_path(int (*matrix)[5], int (*visited)[5], char (*pred)[5], int r, int c, int M, int N){
queue<Cord> q;
bool found = false;
q.push(Cord(r, c));
Cord t;
while(!q.empty()){
t = q.front();
q.pop();
r = t._r, c = t._c;
//std::cout << "visiting (" << t._r << ", " << t._c << ")" << std::endl;
if(isEdge(t._r, t._c, M, N) && matrix[t._r][t._c]){
found = true;
break;
}
for(int i = -1; i <= 1; i++){
for(int j = -1; j <= 1; j++){
if(i ^ j && i != -j && isValid(r+i, c+j, M, N) && matrix[r+i][c+j] && !visited[r+i][c+j]){
q.push(Cord(r+i, c+j));
pred[r+i][c+j] = predecesor(r, c, r+i, c+j);
}
}
}
visited[t._r][t._c] = 1;
}
if(found){
//std::cout << "Path is found" << std::endl;
while(true){
std::cout << "(" << t._r << ", " << t._c << ")";
if(!pred[t._r][t._c])
break;
std::cout << " -> ";
if(pred[t._r][t._c] & LEFT)
t._c -= 1;
else if(pred[t._r][t._c] & RIGHT)
t._c += 1;
else if(pred[t._r][t._c] & UP)
t._r -= 1;
else if(pred[t._r][t._c] & DOWN)
t._r += 1;
else {
std::cout << "Error constructing path" << std::endl;
break;
}
}
}
else
std::cout << "Path is not found" << std::endl;
}
int main(){
int matrix[7][5] = {
{0, 0, 0, 0, 0},
{0, 1, 1, 1, 0},
{0, 1, 0, 1, 0},
{0, 1, 0, 1, 1},
{0, 1, 0, 1, 0},
{0, 1, 0, 1, 0},
{0, 1, 0, 1, 0}
};
int visited[7][5] = {};
char pred[7][5] = {};
find_path(matrix, visited, pred, 1, 1, 7, 5);
}
How about a simple recursive one
public int runToTheEdge(int M[][], int x, int y, int len){
int l = M[0].length;
int b = M.length;
if (x==0 || y ==0 || x==(l-1) || y==(b-1)){
return len;
}
if (M[x][y+1]==0 && M[x+1][y]==0 && M[x-1][y]==0 && M[x][y-1]==0){
return 0;
}
if(M[x][y+1]==1){ // Do same for (x,y-1) (x+1,y) (x-1,y)
len = runToTheEdge(M,x,y+1,len+1);
}
return len;
}
is the starting point given?
- xiaoxipan April 16, 2013