Amazon Interview Question
SDE-2sTeam: Payments
Country: India
Interview Type: In-Person
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];
}
}
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));
}
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;
}
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];
}
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];
}
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]
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];
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});
}
}
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 _)
int[,] m = new m[3,3]
- Rajesh Kumar July 26, 2016FindMinimumPath(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.