## Amazon Interview Question Software Engineer / Developers

• 0

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;
}

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

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

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

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

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

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.

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

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).

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.

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

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

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

/**
* 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;
else{
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();
while (pointer.next != null){
printOut += pointer + "-->";
pointer = pointer.next;
}
return printOut + pointer;
}

}
}

Path aPath = new Path();
Node[][] nodeArray;
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){
nextRow = pathArray[currentRow][currentCol].x;
nextCol = pathArray[currentRow][currentCol].y;
currentRow = nextRow;
currentCol = nextCol;
}
}
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());
}
}

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

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

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)

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

@ 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.

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

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

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)).

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

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.

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

@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.

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();
List<Point> neighbours = new ArrayList<Point>();
for(int i = 0; i < m; i++) {
}
for(int i = 0; i < n; 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;
}``````

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

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;
}
}

{
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];
b[minX][minY] = -1;
}
}
int main()
{
cout<<dig()<<endl;
return 0;
}``````

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]) )

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

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

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;
};

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);
printf("Min path: %d\n", jumpath.difficulty);

// print the list
printf("The list: ");
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;
}``````

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];
}``````

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.

### 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.

### 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.

### 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.