Amazon Interview Question for Software Engineer / Developers


Country: India




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

Do a BFS and be done with it.

- Anonymous August 13, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

As all the nodes are at equi-distance a simple bfs will do the job. There is no need of Dijkstra.

#include <cstdio>
#include <queue>
using namespace std ;

#define SIZE 6

typedef struct point {
        int x ;
        int y ;
        int length ;
}point ;

static int visited[SIZE][SIZE] ;

int matrix[SIZE][SIZE] = {
    {1,1,0,1,0,0},
    {0,1,0,1,1,1},
    {1,1,1,1,0,1},
    {0,1,1,1,0,1},
    {0,0,1,0,0,1},
    {0,0,1,1,0,1}
};

bool isValidMove (int x, int y) {
    if ( x >=0 && x < SIZE && y >= 0 && y < SIZE ){
       if ( (matrix[x][y] == 1) && (visited[x][y] != 1) )
         return true ;
    }
    return false ;
}

int shortestPathLengthBFS () {
     queue<point> q ;
     int x = 0, y = 0, pLength = 0;
     point p ;
          
     p.x = x ;
     p.y = y ;
     p.length = pLength ;
//     printf ( "x = %d, y = %d, length = %d", x, y, pLength );
     visited[p.x][p.y] = 1 ;
     q.push(p);
     
     while (!q.empty()) {
        p = q.front() ;
        q.pop () ;
        pLength = p.length ;
        x = p.x ;
        y = p.y ;

//        printf ( "\nx = %d, y = %d, length = %d", x, y, pLength );
        if ( p.x == SIZE-1 && p.y == SIZE-1 )
           return p.length ;

        if ( isValidMove(x-1,y) ) {
           p.x = x - 1 ;
           p.y = y ;
           p.length = pLength + 1 ;
           visited[p.x][p.y] = 1 ;
//           printf ("\nup" ) ;
           q.push (p) ;
        }
        if ( isValidMove(x,y+1) ) {
           p.x = x ;
           p.y = y + 1 ;
           p.length = pLength + 1 ;
           visited[p.x][p.y] = 1 ;           
//           printf ("\nright" ) ;           
           q.push (p) ;
        }
        if ( isValidMove (x,y-1) ) {
           p.x = x;
           p.y = y - 1 ;
           p.length = pLength + 1 ;
           visited[p.x][p.y] = 1 ;
//           printf ("\nleft" ) ;
           q.push (p) ;
        }
        if ( isValidMove(x+1,y) ) {
           p.x = x + 1 ;
           p.y = y ;
           p.length = pLength + 1 ;
           visited[p.x][p.y] = 1 ;
//           printf ("\ndown" ) ;
           q.push (p) ;             
        }
     }
     return -1 ;
}
     
int main () {
    printf ("\n%d\n", shortestPathLengthBFS() );    
}

- Psycho August 15, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

How to print path ? You are supposed to print co-ordinates that come in path, not all co-ordinate fatched by BFS.

- ninja August 18, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Please see below (scroll down a bit), I also have coded for it.

- Psycho August 20, 2012 | Flag
Comment hidden because of low score. Click to expand.
2
of 2 vote

this is flood fill algorithm

- algos August 13, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Your idea is great!
and I implemented your idea,
here is my code:
public static int get_shortest_path(int[][] test){
if(test[0][0]==0||test[test.length-1][test[0].length-1]==0){
return Integer.MAX_VALUE;
}
int[][] map=new int[test.length][test[0].length];
map[0][0]=1;
boolean change=true;
while(change){ //If there is no update, then we finish.
change=false;
for(int i=0;i!=test.length;i++){
for(int j=0;j!=test[0].length;j++){
if(test[i][j]==1){
int up=Integer.MAX_VALUE;
int down=Integer.MAX_VALUE;
int left=Integer.MAX_VALUE;
int right=Integer.MAX_VALUE;

if(i>0){
up=(map[i-1][j]==0?Integer.MAX_VALUE:map[i-1][j]);
}//check up
if(i<test.length-1){
down=(map[i+1][j]==0?Integer.MAX_VALUE:map[i+1][j]);
}//check down
if(j>0){
left=(map[i][j-1]==0?Integer.MAX_VALUE:map[i][j-1]);
}//check left
if(j<test[0].length-1){
right=(map[i][j+1]==0?Integer.MAX_VALUE:map[i][j+1]);
}//check right
int a=Math.min(up, down);
int b=Math.min(left,right);
int update=Math.min(a, b);
if(update==Integer.MAX_VALUE){
continue;
}
if(map[i][j]==0){
map[i][j]=update+1;
change=true;
}
else{
if(map[i][j]>update+1){
map[i][j]=update+1;
change=true;
}
}
}
}
}
}

int results=map[map.length-1][map[0].length-1];
if(results==0){
return Integer.MAX_VALUE;
}
else
return results-1;
}

- Chengyun Zuo August 15, 2012 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

The Matrix is a representation of a graph. Using, shortest path algorithms like Dijkstra's would fetch u the result.

- Chander Shivdasani August 13, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

How is this a matrix representation of a graph?
In graph a[i][j] represents the edge between node i and j but dont seem to be the case here. Could you please explain.

- Anonymous August 14, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Thats what I feel.. its not directed, so you can't apply Dijkstra... You might reach to a weird state of graph if you do that.. We will have too many ties and we will will be jumping back and forth on two forks (if there is one)

- godzilaa August 14, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

To ashutosh.dhiman: search the Dijkstra algo in wikipedia. There is an example.

- Vincent August 14, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Vincet.. ok, So what would be the complexity of this algo? Won't the starting from (0,0) and keep following the 1 by updating the path by +1 and using the stack for backtracking be efficient? It will be linear in number of 1s in matrix..

- godzilaa August 14, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

I think your algo may potentially more efficient than using Dijkstra. How about the spaces?

- Vincent August 14, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

You mean space complexity? I will use a stack for backtraacking thats it. Even in case of Dijkstra you will use a binary heap or fibbonaci which will be more or same expensive as stack...

- godzilaa August 14, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

My frd, do you mind to post your code solution here? I am afraid of misunderstanding your algo. Thank you

- Vincent August 14, 2012 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

Shorest path and prints the path from backward

#include <cstdio>
#include <queue>
using namespace std ;

#define SIZE 6

typedef struct point {
        int x ;
        int y ;
        int length ;
}point ;

typedef struct path {
        int x;
        int y;
        bool visited ;        
}path ;

static path visited[SIZE][SIZE] ;

int matrix[SIZE][SIZE] = {
    {1,1,0,1,0,0},
    {0,1,0,1,1,1},
    {1,1,1,1,0,1},
    {0,1,1,1,0,1},
    {0,0,1,0,0,1},
    {0,0,1,1,0,1}
};

bool isValidMove (int x, int y) {
    if ( x >=0 && x < SIZE && y >= 0 && y < SIZE ){
       if ( (matrix[x][y] == 1) && !(visited[x][y].visited ) )
         return true ;
    }
    return false ;
}


void findPath () {
     int x = visited[SIZE-1][SIZE-1].x , y = visited[SIZE-1][SIZE-1].y  ;
     while (true) {
           printf ( "\nx = %d, y = %d", x , y ) ;
           if ( x == 0 && y == 0 )
              break ;
           int temp_x = visited[x][y].x ;
           int temp_y = visited[x][y].y  ;
           x = temp_x ;
           y = temp_y ;
     }
}
int shortestPathLengthBFS () {
     queue<point> q ;
     int x = 0, y = 0, pLength = 0 ;
     point p ;
     
     for ( int i = 0 ; i < SIZE ; i ++ ) {
         for ( int j = 0 ; j < SIZE ;j ++ ) {
             visited[i][j].visited = false ;
             visited[i][j].x = -1 ;
             visited[i][j].y = -1 ;
         }
     }
     
     p.x = x ;
     p.y = y ;
     p.length = pLength ;
//     printf ( "x = %d, y = %d, length = %d", x, y, pLength );
     visited[p.x][p.y].visited = true ;
     q.push(p);
     
     while (!q.empty()) {
        p = q.front() ;
        q.pop () ;
        pLength = p.length ;
        x = p.x ;
        y = p.y ;

//        printf ( "\nx = %d, y = %d, length = %d", x, y, pLength );
        if ( p.x == SIZE-1 && p.y == SIZE-1 ) {
           printf ( "\n\nPath is : from (x = %d , y = %d)\n\n", x, y ) ;
           findPath () ;
           return p.length ;
        }

        if ( isValidMove(x-1,y) ) {
           p.x = x - 1 ;
           p.y = y ;
           p.length = pLength + 1 ;
           visited[p.x][p.y].visited = true ;
           visited[p.x][p.y].x = x ;
           visited[p.x][p.y].y = y ;
//           printf ("\nup" ) ;
           q.push (p) ;
        }
        if ( isValidMove(x,y+1) ) {
           p.x = x ;
           p.y = y + 1 ;
           p.length = pLength + 1 ;
           visited[p.x][p.y].visited = true ;
           visited[p.x][p.y].x = x ;
           visited[p.x][p.y].y = y ;
//           printf ("\nright" ) ;           
           q.push (p) ;
        }
        if ( isValidMove (x,y-1) ) {
           p.x = x;
           p.y = y - 1 ;
           p.length = pLength + 1 ;
           visited[p.x][p.y].visited = true ;
           visited[p.x][p.y].x = x ;
           visited[p.x][p.y].y = y ;
//           printf ("\nleft" ) ;
           q.push (p) ;
        }
        if ( isValidMove(x+1,y) ) {
           p.x = x + 1 ;
           p.y = y ;
           p.length = pLength + 1 ;
           visited[p.x][p.y].visited = true ;
           visited[p.x][p.y].x = x ;
           visited[p.x][p.y].y = y ;
//           printf ("\ndown" ) ;
           q.push (p) ;             
        }
     }
     return -1 ;
}
     
int main () {
    printf ("\n%d\n", shortestPathLengthBFS() );    
}

- Psycho August 15, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

dijkstra's algorithm

If you encounter 0, then the distance will be infinity

I am not sure whether this is the best solution. I ll think about it later

- Vincent August 13, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Use a stack

set all '1's in the array to be -1 or something

start at your initial point,
look up, down, left right, and add all valid positions onto the stack.
change all valid position to be current distance (0 for initial point) +1 if this number is less than it's current value (or if it's -1).
pop next coordinate off stack, and repeat

By the time the stack is empty, your destination should be either -1 or some positive number. If it's -1 that means no path exists, if it's some positive number, that would be the shortest possible path. To find the path, just start from the end, and move to the adjacent square that is 1 less than the current square. repeat until you hit the starting point

- Anon August 14, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

use A*

- babbupandey August 14, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

import java.util.ArrayList;



class Point{
public int x;
public int y;
public Point(int x,int y){
this.x=x;
this.y=y;
}
}

public class Walk_from_0_0_to_n_n {

/*
* You have a matrix of size n*n with entries either 1 or 0.
* 1 means there is a path, 0 means no path.
* Find shortest path and print it from (0,0) to (n-1, n-1)
*/
public static void setvalue(int[][]test){
for(int i=0;i!=test.length;i++){
for(int j=0;j!=test[0].length;j++){
if((int)(Math.random()*4)>2){
test[i][j]=0;
}
else{
test[i][j]=1;
}
}
}
}
public static void show(int[][] test){
for(int i=0;i!=test.length;i++){
for(int j=0;j!=test[0].length;j++){
System.out.print(test[i][j]+" ");
}
System.out.println();
}
}
public static int get_shortest_path(int[][]test){
if(test[0][0]==0||test[test.length-1][test[0].length-1]==0){
return Integer.MAX_VALUE;
}

ArrayList<Point> map=new ArrayList<Point>();
int a=find_path(0,0,4,map,test);
int b=find_path(0,0,3,map,test);

if(a==Integer.MAX_VALUE&&b==Integer.MAX_VALUE){
return Integer.MAX_VALUE;
}
else{
return Math.min(a, b);
}

}
public static int find_path(int x,int y,int direct,ArrayList<Point> map,int[][] test){
if(checkHas(map,x,y)){
return Integer.MAX_VALUE;
}
else{
map.add(new Point(x,y));
}

if(x==test.length-1&&y==test[0].length-1){
return 1;
}
int go_down=Integer.MAX_VALUE;
int go_right=Integer.MAX_VALUE;
int go_up=Integer.MAX_VALUE;
int go_left=Integer.MAX_VALUE;
@SuppressWarnings("unchecked")
ArrayList<Point> map1=(ArrayList<Point>) map.clone();
@SuppressWarnings("unchecked")
ArrayList<Point> map2=(ArrayList<Point>) map.clone();
@SuppressWarnings("unchecked")
ArrayList<Point> map3=(ArrayList<Point>) map.clone();
@SuppressWarnings("unchecked")
ArrayList<Point> map4=(ArrayList<Point>) map.clone();

if(x<test.length-1&&test[x+1][y]==1&&direct!=1){
go_down=find_path(x+1,y,3,map1,test);
}
if(y<test[0].length-1&&test[x][y+1]==1&&direct!=2){
go_right=find_path(x,y+1,4,map2,test);
}
if(x>0&&test[x-1][y]==1&&direct!=3){
go_up=find_path(x-1,y,1,map3,test);
}
if(y>0&&test[x][y-1]==1&&direct!=4){
go_left=find_path(x,y-1,2,map4,test);
}
int a=Math.min(go_right, go_down);
int b=Math.min(go_up, go_left);

int result=Math.min(a, b);
if(result==Integer.MAX_VALUE){
return result;
}
else{
return result+1;
}
}

public static boolean checkHas(ArrayList<Point>map,int x,int y){
for(int i=0;i!=map.size();i++){
if(map.get(i).x==x&&map.get(i).y==y){
return true;
}
}
return false;
}

public static void main(String[] args) {
int size=7;

int[][] test=new int[size][size];
setvalue(test);
show(test);
System.out.println("Shortest Path: "+get_shortest_path(test));

}

}

- Chengyun Zuo August 14, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

How to solve this problem by using knowledge of Graph?

- Chengyun Zuo August 14, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Hey did not get the funda of variable "direct", why are u using it, Could you elaborate more ..

- MBIChamps August 15, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include <iostream>

void print_sol(int *x_q,int * y_q,int * l_q,int reer)
{
	if (reer>0) 
	print_sol(x_q,y_q,l_q,l_q[reer]);
	std::cout<<x_q[reer]<<" "<<y_q[reer]<<"\n";
}

int main (int argc, char * const argv[]) {
    
#define N 5
	int map[N][N]={
		{1,1,1,1,1},
		{1,0,0,0,0},
		{1,0,1,1,1},
		{1,0,1,0,1},
		{1,1,1,0,1},
	};
	
	int mark[N][N];
	int offset[4][2]={{0,-1},{-1,0},{0,1},{1,0}};
	int i,j;
	for (i=0;i<N;i++) for (j=0;j<N;j++)
		mark[i][j]=0;
	
	int x_q[N*N];
	int y_q[N*N];
	int l_q[N*N];
	int head=0;
	int reer=0;
	int found=0;
	mark[0][0]=1;
	x_q[0]=0;y_q[0]=0;
	while (head<=reer)
	{
		if (head>=N*N) break;
		int c_p_x=x_q[head];
		int c_p_y=y_q[head];
		
		for (i=0;i<4&&!found;i++)
		{
			int n_p_x=c_p_x + offset[i][0];
			int n_p_y=c_p_y + offset[i][1];
			if (n_p_x<0||n_p_x>=N||
				n_p_y<0||n_p_y>=N)
				continue;
			if (mark[n_p_x][n_p_y])
				continue;
			if (map[n_p_x][n_p_y])
			{
				reer++;
				x_q[reer]=n_p_x;
				y_q[reer]=n_p_y;
				l_q[reer]=head;
				mark[n_p_x][n_p_y]=1;
			}
			if (n_p_x==N-1&&n_p_y==N-1)
			{
				found=1;
				print_sol(x_q, y_q, l_q, reer);
				break;
			}
		}
		
				
		if (found) break;
			
		
		
		head++;
	}
	
	if (!found)
		std::cout<<"No Solution.\n";
    return 0;
}

- hwer.han August 14, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Any graph's shortest path algorithm should work here

- Victor August 14, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Will warshal algorithm work? I guess so...

- victor August 15, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

first made a graph from the given matrix.
then apply shortest path algorithm like dijekstra.
no need to think complicated algorithm.
this is the same problem asked in Amazon_India_Programming_Contest.

- sandeep.masum4685 August 15, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

The approach is very simple. Use the concept of Dynamic programming. No need to go for graphical methods. Below is the code for a simple example:

#include<stdio.h>
#include<limits.h>
#define R 4
#define C 4
#define I 100000
 
int min(int x, int y, int z);
 
int minCost(int cost[R][C], int m, int n)
{
     int i, j,k;
 
     // Instead of following line, we can use int tc[m+1][n+1] or 
     // dynamically allocate memoery to save space. The following line is
     // used to keep te program simple and make it working on all compilers.
     int tc[R][C];  
 
     tc[0][0] = cost[0][0];
 
     /* Initialize first column of total cost(tc) array */
     for (i = 1; i <= m; i++)
     {
         if(cost[i][0]==0)
         break;
        tc[i][0] = tc[i-1][0] + cost[i][0];
     }
     for(k=i;k<=m;k++)
     {
         tc[k][0]=I;
     }
     /* Initialize first row of tc array */
     for (j = 1; j <= n; j++)
     {
         if(cost[0][j]==0)
         break;
         tc[0][j] = tc[0][j-1] + cost[0][j];
     }
      for(k=j;k<=m;k++)
     {
         tc[0][k]=I;
     }
     /* Construct rest of the tc array */
     for (i = 1; i <= m; i++)
     {
        for (j = 1; j <= n; j++)
          { 
            if(cost[i][j]==0)
            {
               tc[i][j]=I;
            }
            else
            {  
            tc[i][j] = min(tc[i-1][j-1], tc[i-1][j], tc[i][j-1]) + 1;
            }
            }
            }
     return tc[m][n];
}
 
/* A utility function that returns minimum of 3 integers */
int min(int x, int y, int z)
{
   if (x < y)
      return (x < z)? x : z;
   else
      return (y < z)? y : z;
}
 
/* Driver program to test above functions */
int main()
{
   int cost[R][C] = { {1, 0, 1, 1},
                      {0, 1, 1, 1},
                      {1, 0, 0, 1},
                      {1, 0, 1, 1}
                       };
   printf(" %d ", minCost(cost, 3, 3));
   getchar();
   return 0;
}

- Nascent_Coder August 15, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Dijstra's algorithm:

vector<int> shortest_path(vector<int> arr, int cols, int rows) {
  if (cols <= 0 || rows <= 0 || arr.size() != cols*rows) return vector<int>();
  vector<float> min_dist(cols*rows, numeric_limits<float>::max());
  vector<bool> visited(cols*rows, false);
  vector<int> previous(cols*rows, -1);
  //
  priority_queue<pair<int, float> > pq;
  min_dist[0] = 0;
  pq.push_back(make_pair(0,0));
  while (!pq.empty()) {
    pair<int, float> elem = pq.front();
    pq.pop();
    vector<int> neighbors = GetNeighbors(elem.first);
    for (int i = 0; i < neighbors.size(); i++) {
      int n_ix = neighbors[i];
      if (visited[n_ix] || arr[n_ix] == 0) continue;
      float dist = elem.first + DistanceBetween(elem.first, neighbors[i]);
      if (dist < min_dist[neighbors[i]]) {
        min_dist[n_ix] = dist;
        previous[n_ix] = elem.first;
        pq.push(make_pair(n_ix, dist));
    }
    visited[elem.first] = true;
  }
  //
  // Back track to get path
  vector<int> path;
  path.push_back(cols*rows); // (n,n)
  while (true) {
    int prev = previous[path.back()];
    if (prev < 0) break;
    path.push_back(prev);
  }  
  reverse(path.begin(), path.end());
  return path;
}

- Martin August 18, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Regard an entry as a node and all of its neighbouring entry as its children, then perform a DFS will do it

- asdfasdf August 19, 2012 | Flag Reply


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