## Amazon Amazon Interview Question for Software Engineer / Developers

• 0

Country: India
Interview Type: In-Person

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

It seems that BFS is sufficient. You just need to remember the number of hops away from the source.

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

+1

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

of course it is a BFS problem

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

is the given matrix is adjacency matrix? then why it is MxN ?

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

No man, it's not an adjacency matrix. All the cells are different nodes. If you want to create an adjacency matrix, then the size of that would be (M*N) X (M*N)

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

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.

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

``````#include <stdio.h>

int outArr;
int grid;

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]=x;
outArr[count++]=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;
outArr[count]=0;
}

return;
}

int main() {

int i =0;
populateGridValue();

findPath(0, 0);

printf("%2d %2d\n", outArr, outArr);
for(i=1; i<500;i++) {
if (outArr[i] == 0 && outArr[i] == 0)
break;
printf("%2d %2d\n", outArr[i], outArr[i]);
}

}``````

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

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

Find "Lee algorithm" in wiki

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

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;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=func(i,j+1,i,j,m,n,fr,fc,arr,hash);
temp=func(i,j-1,i,j,m,n,fr,fc,arr,hash);
temp=func(i+1,j,i,j,m,n,fr,fc,arr,hash);
temp=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;
}``````

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

Why not just A-Star ?

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

A-star with what heuristic? possibly manhattan. But the the limit should be set to the max possible route and that again becomes BFS clearly!

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

Can we have DP here

SP(m,n) = min(SP(m-1, n-1), SP(m-1,n), SP(m,n-1), SP(m+1,n+1), SP(m+1,n), SP(m,n+1)) + 1 if x[m,n] != 0;
if x[m,n] = 0 then return 0

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

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

``````#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.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.size() - 1);
find_shortest_path(src, dst, matrix);
return 0;
}``````

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

use djikstra with path weight 1

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

The complexity of Djikstra will be extremely high here, as the total number of nodes are (M*N). BFS will me more helpful.

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

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.

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

test

Comment hidden because of low score. Click to expand.
-2
of 2 vote

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)

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

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.

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

This will work as we will change direction if we don't find something in that direction. Putting a direction just to reach the node faster

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.