Amazon Interview Question for SDE-2s


Country: United States
Interview Type: In-Person




Comment hidden because of low score. Click to expand.
5
of 5 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.

- technoapurva September 22, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

good solution.

- codealtecdown September 23, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- zortlord September 23, 2015 | Flag
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.

- technoapurva September 23, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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?

- PoWerOnOff November 17, 2015 | Flag
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[0].length == 0){
        return 0;
    }
    if(map.length[0] == 1){
        int sum = 0;
        for(int i = 0; i < map.length; i++){
            sum += map[i][0];
        }
        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][0];
    }
    for(int i = 1; i < map.length; i++){
        for(int j = 0; j < map[0].length; j++){
            if(j == 0){
                working[j] = Math.max(subtotal[j], subtotal[j+1]) + map[j][i];
            }
            else if(j == map[0].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;
}

- zortlord September 22, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Shouldn't your for loop conditions really be:

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

- thedude November 01, 2015 | Flag
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][0] 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[0][0], I can go to mat[0][1], mat[1][1] and then from mat[0][1] I can go to any of the 2 cells and from mat[1][1] 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.

- justaguy September 23, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- codealtecdown September 23, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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}

- justaguy September 23, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- zortlord September 23, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- zortlord September 23, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- justaguy September 23, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- justaguy September 23, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- justaguy September 23, 2015 | Flag
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[0].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;
}
}}

- EPavlova September 23, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- JustAGuy2 November 01, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

This is not a correct solution

- hhh123 November 01, 2015 | Flag
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);
}

}

- seetaram September 28, 2015 | Flag Reply
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);
	}

}

- seetaram September 28, 2015 | Flag Reply
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);
	}

}

- seetaram September 28, 2015 | Flag Reply
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);
	}

}

- seetaram September 28, 2015 | Flag Reply
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;
		
	}

- seetaram September 28, 2015 | Flag Reply
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[0].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][0] = grid[j][0];
		res = max(res, gold[j][0]);
	}
	
	// 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;
}

- PoWerOnOff November 17, 2015 | Flag Reply


Add a Comment
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.

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