Amazon Interview Question SDE-2s
Country: United States
Interview Type: In-Person
@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.
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);
}
}
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;
}
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.
I think solution suggested by technoapurva will work in all cases. Can you give an example where it will not work?
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}
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
@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.
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.
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.
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;
}
}}
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
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);
}
}
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);
}
}
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);
}
}
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;
}
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;
}
Dynamic programming O(mn) time.
- technoapurva September 22, 2015a[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.