## Amazon Interview Question for SDE-2s

Team: Payments
Country: India
Interview Type: In-Person

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

int[,] m = new m[3,3]
FindMinimumPath(m, 0, 0, 3, 3)

public static int FindMinimumPath(int[,] m, int x, int y, int tx, int ty)
{
int path1 = int.MaxValue;
int path2 = int.MaxValue;
int path3 = int.MaxValue;

if(x+1 == tx && y+1 == ty)
return m[x,y];

if(x+1 < tx)
path1 = FindMinimumPath(m, x+1, y, tx, ty);

if(y+1 < ty)
path2 = FindMinimumPath(m,x,y+1, tx,ty);

if(x+1 < tx & y+1 < ty)
path3 = FindMinimumPath(m, x+1, y+1, tx, ty);

return m[x,y] + Math.Min(path1, Math.Min(path2, path3));

}

you can solve this problem by recursion.

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

I have implemented it using Iterative Dynamic Programming.

``````public class Main {

public static void main(String[] args) {
int[][] costMatrix = { {4, 5, 6},
{1, 2, 3},
{0, 1, 2} };

System.out.println("Minimum cost to traverse = "+minCost(costMatrix));

}

public static int minCost(int[][] costMatrix){
int[][] mat = new int[costMatrix.length][costMatrix[0].length];
mat[mat.length-1][mat[0].length-1] =
costMatrix[mat.length-1][mat[0].length-1];
for(int j=mat[0].length-2; j>=0; j--){
int lastRow = mat.length-1;
mat[lastRow][j] = mat[lastRow][j+1] + costMatrix[lastRow][j];
}
for(int i=mat.length-2; i>=0; i--){
int lastCol = mat[0].length-1;
mat[i][lastCol] = mat[i+1][lastCol] + costMatrix[i][lastCol];
for(int j=mat[0].length-2; j>=0; j--){
mat[i][j] = costMatrix[i][j] + Math.min(mat[i+1][j+1],
Math.min(mat[i+1][j], mat[i][j+1]));
}
}
return mat[0][0];
}
}``````

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

int[,] m = new int[3,3]
FindMinimumPath(m, 0, 0, 3, 3)

``````public static int FindMinimumPath(int[,] m, int x, int y, int tx, int ty)
{
int path1 = int.MaxValue;
int path2 = int.MaxValue;
int path3 = int.MaxValue;

if(x+1 == tx && y+1 == ty)
return m[x,y];

if(x+1 < tx)
path1 = FindMinimumPath(m, x+1, y, tx, ty);

if(y+1 < ty)
path2 = FindMinimumPath(m,x,y+1, tx,ty);

if(x+1 < tx & y+1 < ty)
path3 = FindMinimumPath(m, x+1, y+1, tx, ty);

return m[x,y] + Math.Min(path1, Math.Min(path2, path3));

}``````

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

We can create directed graph from the matrix. like the value to the next node as the cost of traversal. Then we can use standard algorithms like Dijkstra’s Algorithm , Prim’s Algorithm etc to find out the path between the start and end node.

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

``````int GetMinimalCost(vector<vector<int>>& grid)
{
for (int i = 0; i < grid.size(); i++)
{
for (int j = 0; j < grid[i].size(); j++)
{
if (i == 0 && j > 0)
grid[i][j] += grid[i][j-1];

if (j == 0 && i > 0)
grid[i][j] += grid[i-1][j];

if (i > 0 && j > 0)
grid[i][j] += min(min(grid[i][j-1], grid[i-1][j]), grid[i-1][j-1]);
}
}

return grid[grid.size()-1][grid[0].size()-1];
}

int main()
{
vector<vector<int>> grid;
int arr[3][3] = {{4,5,6},{1,2,3},{0,1,2}};
for (int i = 0; i< 3; i++)
{
vector<int> vArr(begin(arr[i]), end(arr[i]));
grid.push_back(vArr);
}

int cost = GetMinimalCost(grid);

return 0;
}``````

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

int minPathSum(vector<vector<int> > &A)
{
int m = A.size();
int n = A[0].size();
vector<vector<int>> dp(m, vector<int>(n,0));

dp[0][0] = A[0][0];

for(int i=1;i<m;i++)
dp[i][0] = A[i][0] + dp[i-1][0];
for(int i=1;i<n;i++)
dp[0][i] = A[0][i] + dp[0][i-1];

for(int i=1;i<m;i++)
{
for(int j=1;j<n;j++)
{
dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + A[i][j];
}
}

return dp[m-1][n-1];

}

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

I think your code will give incorrect result for:
4, 2, 0
1, 3, 0
4, 1, 2

in this case: your code will give: 4+1+3+0+2 : 10
but ans should be: 4+2+0+0+2 : 8

correct me, if i'm understanding the question wrong.

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

the before comment was meant for @mk

Can someone tell me why i'm not able to give comments on reply? I have tried several times, but it doesn't take it.

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

the total cost should be minimum right? Then why is everybody taking min of(right, down , diagonal) ?

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

the total cost should be minimum, right?
Why is everybody taking min of {right,down and diagonal} ?
take this example:
{3,2,0}
{1,3,1}
{4,5,2}
If we try with everybody's method, then it will give 3+1+3+1+2
but min cost is: 3+2+0+1+2

can op shed some light on it?

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

To me, the idea is to find ALL POSSIBLE ways of going from the upper left to the lower right corner, and to keep the cost of each way in a vector.
Then we find the minimal vector element.
We can traverse the matrix a directed graph using a recursion.

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

``````int findMinCost(int[][] inputMatrix)
{
if (inputMatrix == null || inputMatrix.length == 0)
return -1;

int[][] minCost = new int[inputMatrix.length][inputMatrix[0].length];

minCost[0][0] = inputMatrix[0][0];
for (int i = 1; i < inputMatrix.length(); i++)
{
minCost[0][i] = minCost[0][i-1] + inputMatrix[0][i];
}

for (int i = 1; i < inputMatrix[0].length(); i++)
{
minCost[i][o] = minCost[i-1][0] + inputMatrix[i][0];
}

for (int i = 1; i < inputMatrix.length(); i++)
{
for (int j = 1; j < inputMatrix[0].length(); j++)
{
minCost[i][j] = Math.min(minCost[i-1][j-1], Math.min(minCost[i-1][j], minCost[i][j-1])) + inputMatrix[i][j];
}
}

return minCost[inputMatrix.length - 1][inputMatrix[0].length -1];
}``````

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

``````mat = [[4,5,6],[1,2,3],[0,1,2]]

def minPath(mat):
m,n = len(mat),len(mat[0])
cost = [[0]*n for i in range(m)]
for i in range(0,m):
for j in range(0,n):
if i == 0 and j == 0:
cost[i][j] = mat[i][j]
elif i == 0:
cost[i][j] = mat[i][j] + cost[i][j-1]
elif j == 0:
cost[i][j] = mat[i][j] + cost[i-1][j]
if i > 0 and j > 0:
cost[i][j] = mat[i][j] + min(cost[i-1][j-1],cost[i-1][j],cost[i][j-1])
return cost[m-1][n-1]``````

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

This is simple. Compute from bottom-right all the way to the top - left.

``````int[,] best = new int[R, C];
Arrays.fill(best[R], Integer.MAX_VALUE);
for(int i =0; i < R; ++i)
best[i, C] = Integer.MAX_VALUE;

for(row = R-1; row >= 0; row--)
{
for(col = C-1; col >= col; col--)
{
best[row][col] = min (best[row+1][col], best[row][col+1], best[row+1][col+1]);
}
}
return best[0][0];``````

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

private static int[] getPath(int i, int j, int[] currPath) {
if (i <= 2 && j <= 2) {
final int currValue = matrix[i][j];
final int[] currTotalPath = mergeArrs(currPath, new int[]{currValue});
if (i == 2 && j == 2) {
return currTotalPath;
}

int arrRight[] = getPath(i, j + 1, currTotalPath);
int arrDown[] = getPath(i + 1, j, currTotalPath);
int arrDiag[] = getPath(i + 1, j + 1, currTotalPath);
return getMin(arrRight, arrDown, arrDiag);
} else {
return mergeArrs(currPath, new int[]{-1});
}
}

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

Its a DP problem.
F(i,j) = Min (F(i-1,j), F(i-1,j-1), F(i,j-1))

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

We need to find all the possible paths and then find the minimum cost path
My solution is in Scala
Note: the M x N matrix is modeled as a vector but accessed with x,y by vector(y*m + x), fairly common technique

``````val xSize = m
val ySize = n

val inputMatrix:Vector = Vector(4,5,6,1,2,3,0,1,2)
def getValueFromPos(p:Position): Int = {
inputMatrix(p.y*xSize + p.x)
}

type Position = (Int, Int)

trait Move {
def execute(p: Position): Position
}

case class Right extends Move {
def execute(p: Position): Position = (p.x + 1, p.y)
}
case class Down extends Move {
def execute(p: Position): Position = (p.x, p.y + 1)
}
case class Diagnol extends Move {
def execute(p: Position): Position = (p.x + 1, p.y + 1)
}
def getMoves(pos:Position): List[Moves] {
if(pos.x < m-1) Right ++
if(pos.y < n-1) Down ++
if(pos.x < m-1 && pos.y < n-1) Diagnol
}

class Path(history: List[Moves], endPos: position, sumCost: Int) {
def extend(m: Move) = new Path(m :: history, m.execute(endPos), sumCost + getValueFromPos(m.execute(endPos)))
}
val initialPath: Path = new Path(Nil, (0,0), 0)

//To get all the paths
def getAllPaths(paths: List[Path]): List[Path] = {
if(paths.isEmpty) List[]
else {
val morePaths = for {
path <- paths
next <- path.endPos getMoves map path.extend
} yield next
paths :: getAllPaths(morePaths)
}

//To find min path between two paths
def minPath(path1: Path, path2: Path) {
if(path1.sum < path2.sum) path1
else path2
}

//Solution to find minimum path
val minPath = getAllPaths(List(initialPath)).reduceLeft(_ minPath _)``````

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.