Amazon Amazon Interview Question
Software Engineer / DevelopersCountry: India
Interview Type: In-Person
Algorithm :
step 1 : check weather source and destination cell of the matrix having 1 or not, if not output Infinite, else
step 2 : create a boolean matrix of same size, and set all entries to false,
step 3 : start from source, set corresponding boolean matrix entry to true,
Lets M is given matrix and N is boolen matrix, so at any (i,j)th node we do following
if(M[i][j+1]&!N[i][j+1]) add it into queue, similarly others, update matrix M entries such that they repersent distance from source cell using BFS algorithm
then we set N[i][j] = true;
go on to new element from queue.
once queue is empty
then print what is written at destination cell.
#include <stdio.h>
int outArr[500][2];
int grid[5][10];
int MAX_X = 4;
int MAX_Y = 9;
int populateGridValue() {
int j =0;
int k =0;
for(j=0;j<=MAX_X;j++) {
for(k=0;k<=MAX_Y;k++) {
if(j==0 && k ==0) grid[j][k] = 1;
else if(j==MAX_X && k ==MAX_Y) grid[j][k] = 1;
else grid[j][k] = (rand() % 5)==0?0:1;
printf("%d ", grid[j][k]);
}
printf("\n");
}
printf("\n\n");
}
int getGridValue(int x, int y) {
return grid[x][y];
}
void findPath(int x, int y) {
static int count = 0;
static int done = 0;
if (count >= 500 || done == 1) return;
outArr[count][0]=x;
outArr[count++][1]=y;
if(y < MAX_Y && getGridValue(x,y+1) == 1) {
findPath(x,y+1);
}
if(x < MAX_X && getGridValue(x+1,y) == 1) {
findPath(x+1,y);
}
if (x ==MAX_X && y==MAX_Y) {
done = 1;
return;
}
if (done == 0) {
outArr[--count][0]=0;
outArr[count][1]=0;
}
return;
}
int main() {
int i =0;
populateGridValue();
findPath(0, 0);
printf("%2d %2d\n", outArr[0][0], outArr[0][1]);
for(i=1; i<500;i++) {
if (outArr[i][0] == 0 && outArr[i][1] == 0)
break;
printf("%2d %2d\n", outArr[i][0], outArr[i][1]);
}
}
output:
grid:
1 1 1 1 1 0 1 1 1 1
1 0 0 1 1 1 1 1 1 0
1 1 1 1 1 0 1 1 1 1
0 1 1 1 1 0 1 1 1 1
1 1 1 1 1 0 0 1 1 1
path:
0 0
0 1
0 2
0 3
0 4
1 4
1 5
1 6
1 7
1 8
2 8
2 9
3 9
4 9
Solution can be devised through dynamic programming. Maintain a 2-D hash of m*n such that each location (if not zero) contains the distance to reach the destination.
Will be divided into two steps:
1) recursively creating the hash.
2) Recursively traversing the hash to print elements.
Below code gives an idea for 1st step. 2nd step can be coded easily on similar lines.
int func(in i,int j,int pr,int pc,int m,int n,int fr,int fc,int arr[][],int hash[][])
{
int temp[4];min,k;
if(i<0||i>m||j<0||j>n||(i==pr&&j==pc))
return 0;
if(i==fr&&j==fc)
{
hash[i][j]=1;
return 1;
}
if(hash[i][j]!=-1)
return hash[i][j];
if(arr[i][j]==0)
{
hash[i][j]=0;
return 0;
}
min=0;
temp[0]=func(i,j+1,i,j,m,n,fr,fc,arr,hash);
temp[1]=func(i,j-1,i,j,m,n,fr,fc,arr,hash);
temp[2]=func(i+1,j,i,j,m,n,fr,fc,arr,hash);
temp[3]=func(i-1,j,i,j,m,n,fr,fc,arr,hash);
//choose the minimum positive
for(k=0;k<4;k++)
{
if(temp[k]!=0)
{
if(min==0||min>temp[i])
min=arr[i];
}
}
if(min==0)
{
hash[i][j]=0;
return 0;
}
hash[i][j]=min+1;
return min+1;
}
Below is a C++11 solution that finds the shortest path using backtracking. The code is quite fast as it immediately abandons any partial solution that is larger than a previously found partial solution. This implementation uses depth first search and works best with sparse matrices. For dense matrices an implementation based on breadth first search runs faster.
$ c++ -std=c++11 shortest_path.cpp -o shortest_path
$ ./shortest_path
[0][0], [1][0], [2][1], [1][2], [0][3], [0][4], [0][5], [1][6], [0][7], [1][8], [2][9],
[3][9], [4][8], [5][7], [4][6], [4][5], [4][4], [5][3], [4][2], [4][1], [5][0], [6][0],
[7][0], [8][1], [7][2], [7][3], [7][4], [7][5], [8][6], [7][7], [7][8], [8][9],
#include <iostream>
#include <vector>
#include <utility>
#include <limits>
typedef std::pair<int, int> indices_t;
typedef std::vector<std::vector<int> > matrix_t;
typedef std::vector<indices_t> solution_t;
bool out_of_bounds(indices_t& current, matrix_t& matrix)
{
return (current.first < 0 ||
current.second < 0 ||
current.first >= (int) matrix.size() ||
current.second >= (int) matrix[0].size());
}
void backtracking(indices_t current,
indices_t& dst,
matrix_t& matrix,
matrix_t& visited,
matrix_t& distances,
solution_t& solution,
solution_t& shortest_path)
{
// reject current indices if previously visited
// or solution larger than shortest_path
if (out_of_bounds(current, matrix) ||
visited[current.first][current.second] == 1 ||
matrix[current.first][current.second] == 0 ||
(int) solution.size() >= distances[current.first][current.second])
return;
// add current [i][j] indices to solution
solution.push_back(current);
visited[current.first][current.second] = 1;
distances[current.first][current.second] = (int) solution.size();
// check if destination reached
if (current.first == dst.first && current.second == dst.second)
shortest_path = solution;
else
{
// visit all indices adjacent to [i][j] i.e. [first][second]
// [i-1][j-1] [i-1][j] [i-1][j+1]
// [i][j-1] [i][j] [i][j+1]
// [i+1][j-1] [i+1][j] [i+1][j+1]
for (int k = 1; k >= -1; k--)
for (int l = 1; l >= -1; l--)
backtracking(std::make_pair(current.first + k, current.second + l),
dst, matrix, visited, distances, solution,
shortest_path);
}
solution.pop_back();
visited[current.first][current.second] = 0;
}
void find_shortest_path(indices_t& src, indices_t& dst, matrix_t& matrix)
{
solution_t shortest_path;
solution_t solution;
// initialize visited matrix to all 0
matrix_t visited;
matrix_t distances;
visited.resize(matrix.size());
distances.resize(matrix.size());
for (std::size_t i = 0; i < visited.size(); i++)
{
distances[i].resize(matrix[i].size(), std::numeric_limits<int>::max());
visited[i].resize(matrix[i].size(), 0);
}
// find shortest path
backtracking(src, dst, matrix, visited, distances, solution, shortest_path);
// print shortest path
for (std::size_t i = 0; i < shortest_path.size(); i++)
std::cout << "[" << shortest_path[i].first
<< "][" << shortest_path[i].second << "], ";
std::cout << std::endl;
}
int main()
{
matrix_t matrix {
{ 1, 0, 1, 1, 1, 1, 0, 1, 1, 1 },
{ 1, 0, 1, 0, 1, 1, 1, 0, 1, 1 },
{ 1, 1, 1, 0, 1, 1, 0, 1, 0, 1 },
{ 0, 0, 0, 0, 0, 0, 0, 0, 0, 1 },
{ 1, 1, 1, 0, 1, 1, 1, 0, 1, 0 },
{ 1, 0, 1, 1, 1, 1, 0, 1, 0, 0 },
{ 1, 0, 0, 0, 0, 0, 0, 0, 0, 1 },
{ 1, 0, 1, 1, 1, 1, 0, 1, 1, 1 },
{ 1, 1, 0, 0, 0, 0, 1, 0, 0, 1 }
};
indices_t src(0, 0);
indices_t dst((int) matrix.size() - 1, (int) matrix[0].size() - 1);
find_shortest_path(src, dst, matrix);
return 0;
}
One possible approach is that,
1.) Use the original matrix as a data structure, else create a copy of it, if we are not allowed to change the matrix.
2.) Maintain a queue/list to store the coordinates of the matrix that need to be visited.
[That makes the worst case space complexity as O(mxn).]
3.) Now, put the source node into the queue.
4.) WHILE the queue is not empty AND (||) the destination coordinates have not reached,
4.1) pull out one 'coordinate Node' from the queue let us name it as 'currentcell'.
4.2) For each of the eight surrounding cells,
4.2.1) If the value in matrix cell is 1, increase the value by ['currentcell' value + 1] and add the coordinate Node into the queue.
4.2.2) If the value in matrix cell is > ['currentcell' value + 1], replace the value in the matrix cell by ['currentcell' value + 1] and add the coordinate Node to the queue.
5.) Now to find the shortest path, start from the DESTINATION/SOURCE coordinate in the matrix and printout the cell coordinate that has the least value.
The idea is that, the cells themselves hold the distance from the source. This is the same as the dijkstra's algorithm but a bit modified.
Use BFS search with small modification - get the direction of search, i.e. if first cell is (5,5) and second cell is (10,10), then don't search all (5,4), (4,4), (4,5), (4,6), (5,6), (6,6), (6,5), (6,4). Rather search elements only in the direction like - (5,6), (6,6) (6,5). Then recurse for the elements in that direction.
If in a particular direction, you are not able to find the node, then change direction. This algo is sort of a mix of BFS and DFS (DFS giving direction)
This won't work if there is a path to 10 from 5 only via 4!! A normal BFS would suffice. You don't need to modify this.
It seems that BFS is sufficient. You just need to remember the number of hops away from the source.
- freshboy January 22, 2013