Amazon Amazon Interview Question for Software Engineer / Developers


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.

- freshboy January 22, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

+1

- Anonymous January 23, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

of course it is a BFS problem

- guoyipeng.516 January 25, 2013 | Flag
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 ?

- Crazy Tesla January 23, 2013 | Flag Reply
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)

- Biru January 23, 2013 | Flag
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.

- sonesh January 23, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#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

- Rahul January 23, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Find "Lee algorithm" in wiki

- Igor Kim January 25, 2013 | Flag Reply
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[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;
}

- k2 January 27, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Why not just A-Star ?

- testing February 17, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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!

- Ravi Vooda March 14, 2013 | Flag
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

- DashDash February 17, 2013 | Flag Reply
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
[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;
}

- iumzlinol November 02, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 5 vote

use djikstra with path weight 1

- bbarodia January 22, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Biru January 23, 2013 | Flag
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.

- nik January 23, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

test

- Rahul January 23, 2013 | Flag Reply
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)

- Biru January 23, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- alex January 23, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Biru January 23, 2013 | Flag


Add a Comment
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.

Learn More

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.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More