Amazon Interview Question Software Engineer / Developers

  • amazon-interview-questions
    0
    of 0 votes
    22
    Answers

    Given a 2-D MxN matrix having each value as difficulty for the block. A frog is starting from a point Matrix[0][0] and will have to reach Matrix[M-1][N-1]. It can jump any step in one go [ 1, 2, ..... M-1] horizontally OR [ 1,2,3,.... N-1] vertically
    Each difficulty value is positive. Write code to give path trace for frog.
    Two structure to use -

    struct node
    {
    int x;
    int y;
    struct node *next;
    };

    struct path
    {
    int difficulty;
    struct node *pathlink;
    }

    Ex matrix - 4X4 matrix

    7 9 2 11
    13 23 1 3
    14 11 20 6
    22 44 3 15

    Minimum difficulty = 7 (a[0][0])+ 2(a[0][2]) +3(a[3][2])+15(a[3][3]) = 27
    Path trace will have = 7->2->3->15

    - sachinism on November 12, 2012 in India Report Duplicate | Flag
    Amazon Software Engineer / Developer

Country: India


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

@amir: just considering the right and below positions may not suffice for example
1 50 1 50
50 1 50 1
50 1 1 50
50 50 50 1

- The Artist on November 12, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Build a graph with all the numbers in same column and same row as its neighbours.
Run Dijikstra algo to find shortest path.

- bharat on November 12, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

You are right. I did this last night 2 minutes before falling asleep, woke up in the morning and realized it was wrong :)

We need all the links as bharat suggested.

- Amir on November 12, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Please suggest code .....

- sachinism on November 12, 2012 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

Input:-
------------------
1 50 1 50
50 1 50 1
50 1 1 50
50 50 50 1

Output
-------------------
1 51 2 51
51 52 52 52
51 52 52 102
51 101 101 52


Start from element (0,0). Calculate lowest difficulty for row (0) and col(0).

element(1,1) --> Calculate the row (1) and col(1) starts from element (1,1)

element (2,2) --> Calculate the row(2) and col(2) starts from element (2,2)
--> Since Frog can jump any number of steps .
--> You need to consider the row(0) and row(1) for calculation of row(2)
-->also consider the col (As per Row)

element (n,n) --> Generalize it from element (2,2).

- Anonymous on November 23, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I'm not sure, but I'd do something like this:
1- Build a graph by connecting i,j to all the elements row i on its right and column j located below i,j.

2- Use shortest path algorithm to reach a particular cell from 0,0 using dijkstra.

- Amir on November 12, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Correction: You need all the links between all the cells in each row or column.

- Amir on November 12, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Assume a m*n array, the total block is m*n vertices, therefore Dijikstra need O(m^2 n^2 ) time to find a path. Using a dynamic programming can reduce it to O (m*n*(m+n)), which seems better. Anybody has better ideas?

The Java code is shown as below
import java.util.LinkedList;


/**
* Dynamic programming method
* Complexity is time O(m*n*(m+n)) and space O(m*n)
* PathFinder.java
* Nov 12, 2012
*/

/**
*
*
*/
public class PathFinder {

private class Node{
int x;
int y;
int difficulty;
Node next;
public Node(int x, int y, int difficulty){
this.x = x;
this.y = y;
this.difficulty = difficulty;
}
public String toString(){
return "<" + difficulty + "(" + x + "," + y + ")" + ">";
}
}
private class Path{
int difficulty;
Node pathLink;
public void add(Node newNode){
if (pathLink == null)
pathLink = newNode;
else{
Node pointer = pathLink;
while(pointer.next != null){
pointer = pointer.next;
}
pointer.next = newNode;
}
difficulty += newNode.difficulty;
}
public String toString(){
if (pathLink == null) return null;
else{
String printOut = new String();
Node pointer = pathLink;
while (pointer.next != null){
printOut += pointer + "-->";
pointer = pointer.next;
}
return printOut + pointer;
}

}
}

Path aPath = new Path();
Node[][] nodeArray;
LinkedList<Node> bestPath = new LinkedList<Node>();
public PathFinder(int[][] difficulty){
int sizeRow = difficulty.length;
int sizeColumn = difficulty[0].length;
nodeArray = new Node[sizeRow][sizeColumn];
for (int index = 0; index < sizeRow; index ++){
for (int index1 = 0; index1 < sizeColumn; index1++){
nodeArray[index][index1] = new Node(index, index1, difficulty[index][index1]);
}
}
findPath();
}
public void findPath(){
int sizeRow = nodeArray.length;
int sizeColumn = nodeArray[0].length;
Node[][] pathArray = new Node[sizeRow][sizeColumn];
pathArray[0][0] = nodeArray[0][0];
for (int indexRow = 1; indexRow < sizeRow; indexRow++){
pathArray[indexRow][0] = new Node(0, 0, nodeArray[0][0].difficulty + nodeArray[indexRow][0].difficulty);
}
for (int indexCol = 1; indexCol < sizeRow; indexCol++){
pathArray[0][indexCol] = new Node(0, 0, nodeArray[0][0].difficulty + nodeArray[0][indexCol].difficulty);
}
for (int indexRow = 1; indexRow < sizeRow; indexRow++){
for (int indexCol = 1; indexCol < sizeColumn; indexCol++){
int minimumDif = pathArray[0][indexCol].difficulty;
int minRow = 0, minCol = indexCol;
// find minimum cost previous node
// search horizontally
for (int indexMin = 0; indexMin < indexCol; indexMin ++){
if (pathArray[indexRow][indexMin].difficulty < minimumDif){
minimumDif = pathArray[indexRow][indexMin].difficulty;
minCol = indexMin;
minRow = indexRow;
}
}
// search vertically
for (int indexMin = 0; indexMin < indexRow; indexMin++){
if (pathArray[indexMin][indexCol].difficulty < minimumDif){
minimumDif = pathArray[indexMin][indexCol].difficulty;
minCol = indexCol;
minRow = indexMin;
}
}
pathArray[indexRow][indexCol] = new Node(minRow, minCol, minimumDif + nodeArray[indexRow][indexCol].difficulty);
}
}
//System.out.println(pathArray[sizeRow - 1][sizeColumn - 1].difficulty);
int currentRow = sizeRow -1;
int currentCol = sizeColumn - 1;
int nextRow = 0;
int nextCol = 0;
while (currentRow > 0 || currentCol > 0){
aPath.add(nodeArray[currentRow][currentCol]);
//bestPath.add(new Node(currentRow, currentCol, nodeArray[currentRow][currentCol].difficulty));
nextRow = pathArray[currentRow][currentCol].x;
nextCol = pathArray[currentRow][currentCol].y;
currentRow = nextRow;
currentCol = nextCol;
}
aPath.add(nodeArray[currentRow][currentCol]);
}
public static void main(String[] args){
int[][] dif = {{1,50,1,50}, {50,1,50,1}, {1,50,1,50}, {50,1,50,1}};
PathFinder myPath = new PathFinder(dif);
System.out.printf("Easiest path is of difficulty %d by ", myPath.aPath.difficulty);
System.out.println(myPath.aPath.toString());
}
}

- Anonymous on November 13, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Please explain u'r algo rather than giving code.. It would be difficult to follow.

- bharat on November 13, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 2 vote

You can make one auxiliary matrix for the minimum difficulty as ...
mat[][] dif[][]
7 9 2 11 ----> 7 16 9 18
13 23 1 3 ----> 20 39 10 13
14 11 20 6 ----> 21 27 29 19
22 44 3 15 ----> 29 60 12 27

You can take this matrix as Matrix of pointers to nodes with structure ...
struct node{ int data; node parent};
First, Dynamically provide the required space for dif[][];

Now for making the above matrix do following ...

void PrintPath(int mat[][4],node *diff[][4]) //m*n*n
{
dif[0][0]->data = mat[0][0];
dif[0][0]->parent = NULL;
for(int i=0;i<m;i++)
{
for(int j=0;j<n;j++)
{
node *temp;
if(i==0 || j==0) temp = dif[0][0]
else temp = FindMinimum(dif,i,j); //It returns the pointer to node with minimum value/data in jth column and ith row with in range of row(0,i) and column(0,j) in O(m+n) time complexity
dif[i][j]->data = temp->data + mat[i][j];
diff[i][j]->parent = temp;
}
}
temp = dif[m-1][n-1];
while(temp!=NULL)
{
cout<<temp->data;
temp = temp->parent;
}
} // Function ends Here


node *FindMinimum(node *dif[][4],int m,int n) //O(m+n)
{
node *min = dif[0][n];
for(int i=0;i<=m;i++)
if(min->data > dif[i][j]->data) min = dif[i][j];
for(int j=0;j<=n;j++)
if(min->data > dif[i][j]->data) min = dif[i][j];
return min;
}

Total Time Complexity O(m*n*(m+n))
Space Complexity O(m*n)

- explorer.bit on November 14, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

@ explorer : As per my understanding, u initialise d[][] with some high values.
1 50 1 50
50 1 50 1
50 1 1 50
50 50 50 1
| |
V
1 51 2 51
51 52 101 52
51 52 3 52
51 101 52 52

actual ans is (0,0)->(0,2)->(2,2)->(2,1)->(1,1)->(1,3)->(3,3) = 7.

u'r algo fails when there is need to go back.

- bharat on November 14, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Actually, what I understood was that you can only go right or below.....So, if it is not that, then it wont work.

- explorer.bit on November 14, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

why not use Bellman-Ford's single-source algorithm.

d[v][i] is the shortest path from v to matrix[0][0] using i edges.

d[v][i] = min(d[x][i-1] + len(v,x)).

- amyue.xing on November 14, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

I changed my idea, since this question is very simple, for each node, the shortest path either comes from its left node or its upper node, thus I changed the d matrix. The following is my code:

// d for memorize
// m, M-1, N-1
int _ssp(int [][]m, int **d, int x, int y)
{
	if(d[x][y]) return d[x][y];

	int min = INT_MAX,
		left = ssp(m, x-1, y),
		up = ssp(m, x, y-1);
	if(left < up){
		min = left;
	}else {
		min = up;
	}
	d[x][y] = min
	return min;
}

int ssp(int [][]m, int w, int h){
	int **d = (int **)malloc(sizeof(int)*w*h);
	int i = 0;

	for(i = 0; i < w; i++){
		d[0][i] = m[0][i];
	}
	for(i = 0; i < h; i++){
		d[i][0] = m[i][0];
	}
	_ssp(m, d, w-1, h-1);
}

Here we need d for memorization, or we have to caculate for multiple times. Once we have run over the code, it's easy to populate some code to generate the path.

- amyue.xing on November 14, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@amyue.xing : u said that "the shortest path either comes from its left node or its upper node,". No, path can come from its right or down node also as per question. Look at the examples mentioned in this post.

- bharat on November 20, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Dijkstra Algorithm

ideone.com/AgQ1e4

Point - represent a point with the total difficulty from the source
override the equals, hashCode and implement Comparable interface so that it can be put to the priority queue

calculate all points difficulty using Dijkstra algorithm
use an auxiliary array holding all points and a map which store the predecessor for each point

in the end construct the path using the predecessors map

class Point implements Comparable<Point>
        {
                public int x;
                public int y;
                public int d; //the total difficulty from the source
                
                public Point(int x, int y)
                {
                        this.x = x;
                        this.y = y;
                        this.d = Integer.MAX_VALUE;
                }
 
                @Override
                public boolean equals(Object o)
                {
                        Point pt = (Point)o;
                        return x == pt.x && y == pt.y;
                }
 
                @Override
                public int hashCode()
                {
                        return (17 + 31 * x) * 31 + y;
                }
 
                @Override
                public String toString()
                {
                        return "(" + x + ", " + y + ")";
                }
 
                @Override
                public int compareTo(Point pt)
                {
                        return d - pt.d;
                }
        }
 
                
        public int minDifficulty(int[][] a)
        {
                int m = a.length;
                int n = a[0].length;
                Point[][] points = new Point[m][n];
                Map<Point, Point> p = new HashMap<Point, Point>(); //the predecessor map
                Queue<Point> q = new PriorityQueue<Point>();
                for(int i = 0; i < m; i++) {
                        for(int j = 0; j < n; j++) {
                                Point pt = new Point(i, j);
                                points[i][j] = pt;
                                if(i == 0 && j == 0) pt.d = a[0][0];
                                p.put(pt, null);
                                q.offer(pt);
                        }
                }
                while(q.peek() != null) {
                        Point pt = q.poll();
                        //find adjacent points
                        List<Point> neighbours = new ArrayList<Point>();
                        for(int i = 0; i < m; i++) {
                                if(i != pt.x) neighbours.add(points[i][pt.y]);
                        }
                        for(int i = 0; i < n; i++) {
                                if(i != pt.y) neighbours.add(points[pt.x][i]);
                        }
                        for(Point neighbour: neighbours) {
                                //relax
                                if(q.contains(neighbour) && neighbour.d > pt.d + a[neighbour.x][neighbour.y]) {
                                                q.remove(neighbour);
                                                neighbour.d = pt.d + a[neighbour.x][neighbour.y];
                                                p.put(neighbour, pt);
                                                q.offer(neighbour);
                                }
                        }
                }
                //construct path
                List<Point> path = new ArrayList<Point>();
                for(Point pt = points[m - 1][n - 1]; pt != null; pt = p.get(pt)) path.add(0, pt);
                System.out.println(path);
                return points[m - 1][n - 1].d;
        }

- lfenjoy9 on November 15, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Input
--------------------
7 9 2 11
13 23 1 3
14 11 20 6
22 44 3 15

Output
----------------------
7 16 9 18
20 39 10 13
21 27 29 19
29 60 12 27

- Anonymous on November 23, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include<algorithm>
#include<iostream>

#define M 4
#define N 4
#define D 3
#define INF 10000

using namespace std;

int a[M][N] = {{1,50,1,50},
               {50,1,50,1},
               {50,1,1,50},
               {50,50,50,1},
              };

int b[M][N] = {{1,INF,INF,INF},
               {INF,INF,INF,INF},
               {INF,INF,INF,INF},
               {INF,INF,INF,INF}
              };

void findMin(int &x,int &y)
{
    int min=INF;
    for(int i=0;i<M;i++)
    for(int j=0;j<N;j++)
    {
        if(b[i][j]<min && b[i][j]>=0)
        min=b[i][j],x=i,y=j;
    }
}

void spreadMin(int x,int y)
{
    for(int k = 0;k<M;k++)
    b[k][y]=min(b[k][y],b[x][y]+a[k][y]);

    for(int k = 0;k<N;k++)
    b[x][k]=min(b[x][k],b[x][y]+a[x][k]);
    return ;

}
int dig()
{
    int minX,minY;
    while(true)
    {
        findMin(minX,minY);
        if(minX==D && minY == D) return b[D][D];
        spreadMin(minX,minY);
        b[minX][minY] = -1;
    }
}
int main()
{
    cout<<dig()<<endl;
    return 0;
}

- Anonymous on November 27, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Can be done using Dynamic Programming in O(n^3) , Assuming all values are positive
Base cases , a[0.j] = a[0]+a[j]
a[j,0] = a[0]+a[j];
a[i,j] = min( min over all k's from 0to j-1 a[i,k]+a[i,j] ), min (over all k's from 0 to i-1 [k,j]+a[i,j]) )

- Geek on December 09, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Building of graph will take O(n^4) as suggested in other approaches

- Geek on December 09, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Here is a C++ code which solves the problem, using a recursive function call.
The code of course can be optimized by building an identical sized matrix that each cell will contain the shortest jump path from (x,y) cell.

#include <stdio.h> 
#include <stdlib.h> 
#include <iostream> 
#include <sstream> 


struct node {
	int x;
	int y;
	struct node *next;
};

struct path {
	int difficulty;
	struct node *pathlink;
};	

int mat[3][3] = { {1, 100, 100}, {1, 1, 100}, {100, 0, 1} }; 

int rows = 3; 
int cols = 3; 
int sum = 0; 

struct path jumpath; 

int findLightestPath(int row, int col, struct node **output) 
{
	struct node *current = new struct node;
	current->x = row; 
	current->y = col;
	*output = current; // return the list from me...  

	if ( (row == (rows - 1) || col == (cols - 1)) ) { 
		printf("find path: mat[%d][%d] = %d (end)\n", row, col, (mat[row][col] + mat[rows - 1][cols - 1]));
		
		struct node *last = new struct node; 
		last->x = (rows - 1); 
		last->y = (cols - 1); 
		last->next = NULL; // end of list 
		current->next = last; 
		return (mat[row][col] + mat[rows - 1][cols - 1]); 
	}

	printf("find path: mat[%d][%d] = %d\n", row, col, mat[row][col]);

	int sum = 10000000; // just a big number because I'm lazy
	int tsum, i; 
	struct node *next = NULL; 

	for (i = 1; i < cols && (i + 1) < cols; i++) { // running horizontal  
		if ((i + 1) == cols) break; 
		tsum = findLightestPath(row, (col + i), &next);

		if (tsum < sum) {
			// delete current->next (am lazy...)
			current->next = next; 
			sum = tsum; 
		} else {
			// delete the list pointed by the next pointer - not needed (am lazy...)
		}
	} // horizontal for 

	printf("\n sum=%d \n", sum);

	for (i = 1; (i < rows) && (i + 1) < rows; i++) { // running vertical  
		tsum = findLightestPath((row + i), col, &next);

		if (tsum < sum) {
			// delete current->next (am lazy...)
			current->next = next; 
			sum = tsum;
		} else {
			// delete the list pointed by the next pointer - not needed (am lazy...)
		}
	} // vertical for 

	printf("\n sum=%d \n", sum);
	return (mat[row][col] + sum);
}


void fillMatrix(int rows, int cols) 
{
	// random mat 
	/*for (int i=0; i < rows; i++) 
		for (int j=0; j < cols; j++) 
			mat[i][j] = ((rand() % 30) + 1); 
	*/

	printf("The matrix: \n\n"); 
	for (int i=0; i < rows; i++) {
		for (int j=0; j < cols; j++) {
			printf("[%d][%d]=%d ", i, j, mat[i][j]);
		}
		printf("\n"); 
	}
}

int main(int argc, char *argv[])
{
	jumpath.difficulty = 0; 
	fillMatrix(rows, cols);
	jumpath.difficulty = findLightestPath(0,0, &jumpath.pathlink);
	printf("Min path: %d\n", jumpath.difficulty);
	
	// print the list
	printf("The list: "); 
	struct node *list = jumpath.pathlink; 
	while (list != NULL) {
		if (list->next == NULL) {
			printf("(%d,%d)[%d]\n", list->x, list->y, mat[list->x][list->y]); 
		} else {
			printf("(%d,%d)[%d]->", list->x, list->y, mat[list->x][list->y]); 	
		}
		
		list = list->next; 
	}


	return 0; 
}

- KTGW on December 17, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

you can do it by dynamic programming. I just implement finding difficulty part. tracing part can be done by keeping another array for path.

private static int find_minimum_difficulty(int[][]a){
		int diff [][] = new int [a.length][a[0].length];
		diff[0][0] = a[0][0];
		for(int i=1;i<a.length;i++){
			diff[i][0] = a[i][0]+a[0][0];
		}
		for(int i=1;i<a[0].length;i++){
			diff[0][i] = a[0][i]+a[0][0];
		}
		for(int i=1;i<a.length;i++){
			for(int j =1 ;j<a[0].length;j++){
				int min = Integer.MAX_VALUE ;
				for(int k=0;k<j;k++){
					if(diff[i][k] < min){
						min = diff[i][k];
					}
				}
				for(int k=0;k<i;k++){
					if(diff[k][j] < min){
						min = diff[k][j];
					}
				}
				diff[i][j] = a[i][j]+min; 
			}
		}
		for(int i=0;i<diff.length;i++){
			for (int j = 0; j < diff[0].length; j++) {
				System.out.print(diff[i][j]+"\t");
			}
			System.out.println();
		}
		return diff[a.length-1][a[0].length-1];
	}

- Anonymous on January 06, 2013 | Flag Reply


Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book walking you through 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