## Amazon Interview Question for SDE-2s

• 0

Country: United States
Interview Type: In-Person

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

Dynamic programming O(mn) time.
a[i][j]=max{a[i-1][j-1],a[i][j-1],a[i+1][j-1]} +a[i][j] for j=0 to n-1
and a[i][j]=0 for i<0 or i>=m

Finally the max element in the last column is the solution.

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

good solution.

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

not the best because it consumes O(mn) memory rather than only O(n).

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

@zortlord: This solution consumes O(1) memory as I am storing the results in the same array. However, if there was a condition that we cannot modify the input array then it can be done in O(m) space as we just need to store the result of the most recent column.

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

I know to use O(n) space to solve it. But can you tell me how you use only O(1) to solve the problem?

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

``````package test;

import java.util.HashMap;
import java.util.Map;

/**
*  Calculate the maximum god for each row and max of all rows is the solution
*
* @author ram
*
*/

public class GoldenGrid {

//static Integer[][] data = { { 1, 1, 1000, 10 }, { 2, 0, 100, 200 },
//	{ 3, 1, 1, 2000 }, { 5, 0, 0, 1 } };

static Integer[][] data = {{2,4,6,0},{10,20,30,40},{200,1,300,800},{1000,2000,3000,4000}};

static Map<String,Integer> visitedGrids = new HashMap<String,Integer>();

private static int calcilateGoldVolue(int row, int col) {

if(col<0 || col > 3 || row > 3 || row <0 ){
return 0;
}

if(visitedGrids.get(row+","+col) != null){
//System.out.println("Visited Grid : "+row+","+col);
return visitedGrids.get(row+","+col);
}

int result = data[row][col]
+ Math.max(Math.max(calcilateGoldVolue(row - 1, col + 1),
calcilateGoldVolue(row, col + 1)),
calcilateGoldVolue(row + 1, col + 1));

visitedGrids.put(row+","+col,result);

return result;

}

public static void main(String[] args) {

int maxValue = 0;
int result = 0;
for(int row = 0; row<data.length; row++){

result = calcilateGoldVolue(row,0);
// System.out.println(row +"="+result);
if(result > maxValue){
maxValue = result;
}
}

System.out.println(maxValue);
}

}``````

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

O(n * m) runtime and O(n) memory using dynamic programming:

``````public static int getBestPath(int[][] map){
//handle simpler base cases
if(map == null){
throw new NullPointerException("\"map\" may not be null");
}
if(map.length == 0 || map.length == 0){
return 0;
}
if(map.length == 1){
int sum = 0;
for(int i = 0; i < map.length; i++){
sum += map[i];
}
return sum;
}

//now compute the value of each path through the map
//each position is the best predecessor of the 3 possible choices
//plus the current position in the map
//ie: working[j] = Max(subtotal[j-1], subtotal[j], subtotal[j+1]) + map[i][j]
int[] working = new int[map.length];
int[] subtotal = new int[map.length];
int[] temp;
for(int j = 0; j < subtotal.length; j++){
subtotal[j] = map[j];
}
for(int i = 1; i < map.length; i++){
for(int j = 0; j < map.length; j++){
if(j == 0){
working[j] = Math.max(subtotal[j], subtotal[j+1]) + map[j][i];
}
else if(j == map.length -1){
working[j] = Math.max(subtotal[j], subtotal[j-1]) + map[j][i];
}
else{
working[j] = Math.max(subtotal[j-1], Math.max(subtotal[j], subtotal[j+1])) + map[j][i];
}
}
temp = subtotal;
subtotal = working;
working = temp;
}

//now pick the best score out of the final results
int best = Integer.MIN_VALUE;
for(int i : subtotal){
if(i > best){
best = i;
}
}
return best;
}``````

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

Shouldn't your for loop conditions really be:

``````for (int c = 1; c < map.Length; c++)
{
for (int r = 0; r < map.Length; r++)``````

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

hmm, I first thought about the approaches suggested by technoapurva and zortlord. Those solutions are a good start but I think they don't work correctly.

In my opinion, I think we have to find solutions for all rows and columns starting from column + 1 (next col.), so lets say for mat[i] we have to find total gold for all next i-1,i,i+1 rows and col+1....n since we can move in any of the 3 directions.

For example for mat, I can go to mat, mat and then from mat I can go to any of the 2 cells and from mat I can go to any of the 3 cells. Now, here greedy solution won't work as in getting max of 2 or 3 cells since bigger number can either arrive in any of the later columns and rows.

Its not a complicated problem, it needs a little bit thinking. This problem can be solved using recursion. I've solved it on paper, just don't feel like typing the code.

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

I think solution suggested by technoapurva will work in all cases. Can you give an example where it will not work?

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

For sure,
here's one, its a 4x4 matrix and each cell has some amount of gold:

3,2,9,4
1,7,5,3
2,4,6,9
1,6,2,5

In this case, greedy solution doesn't seem to work. zortlord solution gives 22, but actual solution is 24. Here's the path - (0,0){3}->(1,1){7}->(1,2){5}->(2,3){9}

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

The DP approach PROVES it is the optimal solution.

``TotalValue[i][j] = Max(TotalValue[i-1][j-1], TotalValue[i-1][j], TotalValue[i-1][j+1]) + Value[i][j]``

In other words, this says, total value computed for any location in the map is equal to the maximum total value computed from the only valid predecessor total values plus the value that can be derived for this specific location. Then you just iterate over the final total values and select the largest

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

@Justaguy

The Ideal solution is 25, not 24. And it passes through (0,0), (1,1), (2,2), (3,2).

There was a flaw in my code where I had transposed the coordinates of the value at each location. it should be map[j][i] and NOT map[i][j]. Try it again...

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

@zortlord.
I see, it makes sense now, your solution is correct and I tried again with the fixed coords. it works now. and yeah idea solution is 25, not 24.

hmm, the solution I had is then just another approach of solving this problem then, but DP approach works as well.

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

Is there some limitation in the website where if I'm just a guest I won't see the new comments immediately or is it some flaw? If I submit a comment it does not show up right away.

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

forgot to mention, there is another minor bug in your code where it gives array out of bounds exception if its a 5x4 matrix, its just a trivial error, but the logic is fine.

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

Iterative bottom - up approach
{{
int maxGoldSum(int[][] goldPlate) {
if (goldPlate == null)
throw new NullPointerException();
int M = goldPlate.length;
int N = goldPlate.length;
int maxGold[][] = new int[M + 1][N + 1];
for (int r = M; r >=0; r--) {

for (int c = 1; c <= N; c++) {
if (r > 0)
maxGold[r][c]= Math.max(maxGold[r][c], maxGold[r - 1][c - 1] + goldPlate[r - 1][c - 1]);
if ((r < M)&&(r > 0))
maxGold[r][c]= Math.max(maxGold[r][c], maxGold[r + 1][c - 1] + goldPlate[r - 1][c - 1]);
if (r > 0)
maxGold[r][c]= Math.max(maxGold[r][c], maxGold[r][c - 1] + goldPlate[r - 1][c - 1]);
}
}
int max = Integer.MIN_VALUE;
for(int r = 1; r <= M; r++) {
max = Math.max(max,maxGold[r][N]);
}
return max;
}
}}

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

For the Gold Plate = { 3, 2, 9, 4 },
{ 1, 7, 5, 3 },
{ 2, 4, 6, 9 },
{ 1, 6, 2, 5 }

Your algo returns a Max value of 22, which is incorrect as the max or ideal would be 25

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

This is not a correct solution

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

package test;

import java.util.HashMap;
import java.util.Map;

/**
* Calculate the maximum god for each row and max of all rows is the solution
*
* @author ram
*
*/

public class GoldenGrid {

//static Integer[][] data = { { 1, 1, 1000, 10 }, { 2, 0, 100, 200 },
// { 3, 1, 1, 2000 }, { 5, 0, 0, 1 } };

static Integer[][] data = {{2,4,6,0},{10,20,30,40},{200,1,300,800},{1000,2000,3000,4000}};

static Map<String,Integer> visitedGrids = new HashMap<String,Integer>();

private static int calcilateGoldVolue(int row, int col) {

if(col<0 || col > 3 || row > 3 || row <0 ){
return 0;
}

if(visitedGrids.get(row+","+col) != null){
//System.out.println("Visited Grid : "+row+","+col);
return visitedGrids.get(row+","+col);
}

int result = data[row][col]
+ Math.max(Math.max(calcilateGoldVolue(row - 1, col + 1),
calcilateGoldVolue(row, col + 1)),
calcilateGoldVolue(row + 1, col + 1));

visitedGrids.put(row+","+col,result);

return result;

}

public static void main(String[] args) {

int maxValue = 0;
int result = 0;
for(int row = 0; row<data.length; row++){

result = calcilateGoldVolue(row,0);
// System.out.println(row +"="+result);
if(result > maxValue){
maxValue = result;
}
}

System.out.println(maxValue);
}

}

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

Here is the solution

``````package test;

import java.util.HashMap;
import java.util.Map;

/**
*  Calculate the maximum god for each row and max of all rows is the solution
*
* @author ram
*
*/

public class GoldenGrid {

//static Integer[][] data = { { 1, 1, 1000, 10 }, { 2, 0, 100, 200 },
//	{ 3, 1, 1, 2000 }, { 5, 0, 0, 1 } };

static Integer[][] data = {{2,4,6,0},{10,20,30,40},{200,1,300,800},{1000,2000,3000,4000}};

static Map<String,Integer> visitedGrids = new HashMap<String,Integer>();

private static int calcilateGoldVolue(int row, int col) {

if(col<0 || col > 3 || row > 3 || row <0 ){
return 0;
}

if(visitedGrids.get(row+","+col) != null){
//System.out.println("Visited Grid : "+row+","+col);
return visitedGrids.get(row+","+col);
}

int result = data[row][col]
+ Math.max(Math.max(calcilateGoldVolue(row - 1, col + 1),
calcilateGoldVolue(row, col + 1)),
calcilateGoldVolue(row + 1, col + 1));

visitedGrids.put(row+","+col,result);

return result;

}

public static void main(String[] args) {

int maxValue = 0;
int result = 0;
for(int row = 0; row<data.length; row++){

result = calcilateGoldVolue(row,0);
// System.out.println(row +"="+result);
if(result > maxValue){
maxValue = result;
}
}

System.out.println(maxValue);
}

}``````

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

``````package test;

import java.util.HashMap;
import java.util.Map;

/**
*  Calculate the maximum god for each row and max of all rows is the solution
*
* @author ram
*
*/

public class GoldenGrid {

//static Integer[][] data = { { 1, 1, 1000, 10 }, { 2, 0, 100, 200 },
//	{ 3, 1, 1, 2000 }, { 5, 0, 0, 1 } };

static Integer[][] data = {{2,4,6,0},{10,20,30,40},{200,1,300,800},{1000,2000,3000,4000}};

static Map<String,Integer> visitedGrids = new HashMap<String,Integer>();

private static int calcilateGoldVolue(int row, int col) {

if(col<0 || col > 3 || row > 3 || row <0 ){
return 0;
}

if(visitedGrids.get(row+","+col) != null){
//System.out.println("Visited Grid : "+row+","+col);
return visitedGrids.get(row+","+col);
}

int result = data[row][col]
+ Math.max(Math.max(calcilateGoldVolue(row - 1, col + 1),
calcilateGoldVolue(row, col + 1)),
calcilateGoldVolue(row + 1, col + 1));

visitedGrids.put(row+","+col,result);

return result;

}

public static void main(String[] args) {

int maxValue = 0;
int result = 0;
for(int row = 0; row<data.length; row++){

result = calcilateGoldVolue(row,0);
// System.out.println(row +"="+result);
if(result > maxValue){
maxValue = result;
}
}

System.out.println(maxValue);
}

}``````

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

``````private static int calcilateGoldVolue(int row, int col) {

if(col<0 || col > 3 || row > 3 || row <0 ){
return 0;
}

if(visitedGrids.get(row+","+col) != null){
//System.out.println("Visited Grid : "+row+","+col);
return visitedGrids.get(row+","+col);
}

int result = data[row][col]
+ Math.max(Math.max(calcilateGoldVolue(row - 1, col + 1),
calcilateGoldVolue(row, col + 1)),
calcilateGoldVolue(row + 1, col + 1));

visitedGrids.put(row+","+col,result);

return result;

}``````

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

Time complexity = O(m*n); space complexity = O(m * n).
It can also be solved by compressing the 2-D array to a linear array which only consumes O(n) space.

``````int maxGold(vector<vector<int> > & grid){

int row = grid.size();
int col = grid.size();

vector<vector<int> > gold(row, vector<int>(col, 0));

int res = 0;

// populate the first column
for(int j = 0; j < row; j++){
gold[j] = grid[j];
res = max(res, gold[j]);
}

// start from the second column
for(int i = 1; i < col; i++){
for(int j = 0; j < row; j++){
if(j == 0){
gold[j][i] = max(gold[j][i-1], gold[j+1][i-1]) + grid[j][i];
}
else if(j == row - 1){
gold[j][i] = max(gold[j][i-1], gold[j-1][i-1]) + grid[j][i];
}
else{
gold[j][i] = max(max(gold[j][i-1], gold[j-1][i-1]), gold[j+1][i-1]) + grid[j][i];
}

res = max(res, gold[j][i]);
}
}

return res;
}``````

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.