Amazon Interview Question


Country: United States




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

public static int dp(int[][] arr) {
		
		int R=arr.length-1,C=arr[0].length-1;
		
		int[][] tc = new int[R+1][C+1];
		
		tc[0][0] = arr[0][0];
		
		for(int i=1;i<C+1;i++)
			tc[0][i] = tc[0][i-1]+arr[0][i];
		
		for(int j=1;j<R+1;j++)
			tc[j][0] = tc[j-1][0] + arr[j][0];
		
		for(int i=0;i<R;i++)
			for(int j=0;j<C;j++) {
				
				tc[i+1][j+1] = Math.max(tc[i][j+1], tc[i+1][j])+arr[i+1][j+1];
			}
		
		return tc[R][C];
	}

Solution in O(RC)

- shukad333 August 31, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

// Here is my Code

static int[][] grid; // global array

	 public static long max(int r , int c,int R,int C)
	 {
		 if(r<0||r>R-1||c<0||c>C-1)return Long.MIN_VALUE;
		 
		 if(r==R-1&&c==C-1)return grid[r][c];
		 
		 long path1 =max(r,c+1,R,C);
		 long path2=max(r+1,c,R,C);
		 
		 return grid[r][c]+Math.max(path1, path2);
		 
	 }
 // In Main Method
 // Initialize  2D grid
 // call method max(0,0,n,n)

- waledsalah2005 August 30, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Recursion is overkill. would have been better if you had used an array to memoize

- Sathya August 30, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

I know how to optimize this cood , i wrote simple code :)
thx

- waledsalah2005 August 31, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

typedef struct PathResult {
	PathResult() : sum(0), path("") {}
	unsigned long sum;
	string path;
} pathResult_t;

pathResult_t FindMaxPath(vector<vector<unsigned long>>& grid, size_t r, size_t c)
{
	ostringstream oss;
	pathResult_t result;
	
	if (r >= grid.size() || c >= grid[r].size())
		return result;

	if (r == grid.size() - 1 && c == grid[r].size() - 1) {
		result.sum = grid[r][c];
		oss << "[" << r << "][" << c <<"]";
		result.path = oss.str();
		return result;
	}
	pathResult_t path1 = FindMaxPath(grid, r, c + 1);
	pathResult_t path2 = FindMaxPath(grid, r + 1, c);
	oss << "[" << r << "][" << c << "] ";
	if (path1.sum >= path2.sum)
		oss << path1.path;
	else
		oss << path2.path;
	result.sum = grid[r][c] + Max(path1.sum, path2.sum);
	result.path = oss.str();
	return result;
}

- Teh Kok How August 31, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

function pos(row, col, sum) {
        var val = this[row][col]
        return {
                row: row,
                col: col,
                val: val,
                sum: sum + val
        }
}
function dfs(array) {
        var S = []
        , max = 0
        , p
        array.pos = pos
        S.push(array.pos(0, 0, 0))
        while (S.length) {
                p = S.pop()
                down = p.row + 1
                right = p.col + 1
                if (array[down])
                        S.push(array.pos(down, p.col, p.sum))
                if (array[right])
                        S.push(array.pos(p.row, right, p.sum))
                if (undefined === array[down] && undefined === array[right])
                        max = p.sum > max ? p.sum : max
        }
        return max
}

//e.g....
var maze = [
         [0, 9, 2]
        , [7, 50, 100]
        , [10, 6, 6]
]
console.log(dfs(maze))

- srterpe August 30, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public class MazePathMax {
	
	public static void main(String[] args) {
		
	
	int[][] arr = { { 1,5,2},
					{7,9,3},
					{4,9,8} ,
					{3,4,5}};
	
	
	System.out.println(getMaxPathSum(arr, 0, 0, arr.length-1, arr[0].length-1));
	
	
	
	}
	
	public static int getMaxPathSum(int[][] arr , int r , int c , int R , int C) {
		
		if(r>R || c>C)
			return -1;
		
		if(r==R && c==C)
			return arr[r][c];
		
		int s1 = getMaxPathSum(arr, r+1, c, R, C);
		int s2 = getMaxPathSum(arr, r, c+1, R, C);
		
		return arr[r][c] + Math.max(s1, s2);
		
		
		
		
	}

}

- shukad333 August 31, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

if no require the trace, dp can handle it.
if require the tracce, i can only get the dfs method .

- Anonymous August 31, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

you can create a wrapper class for an element, including direction and value. direction means from which direction you get the max, either up or left.

Once reached the last point,use direction backwards to print out the trace, additional m+n steps, overall time complexity is still O(m*n)

Can you elaborate DFS more? what's time and space complexity of that.

- Anonymous September 02, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

this will be directed graph from ra[0][0] to ar[n][n], and depth first research actually yield the result

- mayankshivalik September 01, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

This can be done with temporary array which reduces number of iteration to number of elements only (Dynamic Programming).
And simply by kind of DFS.

IntPair is class with matrix positions

public class MaxMatrixPath {

	int[][] tempMatrix = null;
	
	MaxMatrixPath () {
		tempMatrix = null;
	}

	MaxMatrixPath (int sizeX, int sizeY) {
		tempMatrix = new int [sizeX][sizeY];
		initialise ();
	}

	private void initialise() {
		for (int i = 0; i < tempMatrix.length; i++) {
			for (int j = 0; j < tempMatrix[0].length; j++) {
				tempMatrix[i][j]=Integer.MIN_VALUE;
			}
		}
	}

	int maxSum_less_expensive (int[][] input, IntPair current) {
		int right_sum = 0;
		int down_sum = 0;
		int x = current.getFirst();
		int y = current.getSecond();

		if (tempMatrix[x][y] != Integer.MIN_VALUE) {
			return tempMatrix[x][y];
		}

		if (isLastNode (input, current)) {
			return input[input.length][input[0].length];
		}
		if (rightPathValid (input, current)) {
			right_sum = maxSum_less_expensive (input, rightNode(input, current));
		}
		if (downPathValid (input, current)) {
			down_sum = maxSum_less_expensive (input, downNode(input, current));
		}
		int max_sum = Math.max(right_sum, down_sum);
		int sumTillNode = max_sum + input[x][y];
		tempMatrix [x][y] = sumTillNode;
		return sumTillNode;
	}

	int maxSum (int[][] input, IntPair current) {
		int right_sum = 0;
		int down_sum = 0;

		if (isLastNode (input, current)) {
			return input[input.length][input[0].length];
		}
		if (rightPathValid (input, current)) {
			right_sum = maxSum (input, rightNode(input, current));
		}
		if (downPathValid (input, current)) {
			down_sum = maxSum (input, downNode(input, current));
		}
		int max_sum = Math.max(right_sum, down_sum);
		return max_sum + input[current.getFirst()][current.getSecond()];
	}

	private IntPair downNode(int[][] input, IntPair current) {
		return new IntPair ((current.getFirst()+1), current.getSecond());
	}

	private IntPair rightNode(int[][] input, IntPair current) {
		return new IntPair (current.getFirst(), (current.getSecond() + 1));
	}

	private boolean downPathValid(int[][] input, IntPair current) {
		if (input.length > (current.getFirst() + 1)){
			return true;
		}
		return false;
	}

	private boolean rightPathValid(int[][] input, IntPair current) {
		if (input[0].length > (current.getSecond() + 1)){
			return true;
		}
		return false;
	}

	private boolean isLastNode(int[][] input, IntPair current) {
		if (current.getFirst() == input.length
				&& current.getSecond() == input[0].length) {
			return true;
		}
		return false;
	}
}

- SK September 02, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

import Foundation

struct Matrix {
    var rows : Int
    var cols : Int
    var data : [[Int]]
    
    init(rows:Int, cols:Int) {
        self.rows = rows
        self.cols = cols
        self.data = [[Int]]()
    }
}

class Rover {
    private var matrix : Matrix
    private var max : Int = 0
    private var path : String = ""
    
    init () {
        self.matrix = Matrix(rows:5, cols:5)
        self.matrix.data.append([2,34,1,1,11])
        self.matrix.data.append([13,8,4,10,6])
        self.matrix.data.append([5,82,9,34,17])
        self.matrix.data.append([5,8,19,2,77])
        self.matrix.data.append([71,18,96,5,34])
    }
    
    // Returns the path that leads to the maximum SUM
    func routeMAX() -> (String) {
        var backgroundQueue = NSOperationQueue()
        backgroundQueue.maxConcurrentOperationCount = 10 // Cap the thread spawns
        backgroundQueue.addOperationWithBlock { () -> Void in
            self.routeMAX(0, col: 0, resultSoFar: 0, pathSoFar: "")
        }
        backgroundQueue.waitUntilAllOperationsAreFinished()
        NSOperationQueue.mainQueue().waitUntilAllOperationsAreFinished()
        return "SUM: \(self.max) \nPath: \(self.path)"
    }
    
    private func routeMAX(row:Int, col:Int, resultSoFar:Int, pathSoFar:String) {
        let result = resultSoFar + self.matrix.data[row][col]
        let path = pathSoFar + (pathSoFar.isEmpty ? "" : ", ") + "\(self.matrix.data[row][col])"
        if row < self.matrix.rows-1 {
            NSOperationQueue.currentQueue().addOperationWithBlock({ () -> Void in
                self.routeMAX(row+1, col: col, resultSoFar: result, pathSoFar:path)
            })
        }
        if col < self.matrix.cols-1 {
            NSOperationQueue.currentQueue().addOperationWithBlock({ () -> Void in
                self.routeMAX(row, col: col+1, resultSoFar: result, pathSoFar:path)
            })
        }
        if (col == self.matrix.cols-1) && (row == self.matrix.rows-1) {
            // We compare and replace the new local MAX safely
            var syncQueue = NSOperationQueue()
            syncQueue.maxConcurrentOperationCount = 1
            syncQueue.addOperationWithBlock({ () -> Void in
                if result > self.max {
                    self.max = result
                    self.path = path
                }
            })
            syncQueue.waitUntilAllOperationsAreFinished()
        }
    }
}

- Anonymous September 04, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Here's both recursion and DP

public class MaxPath {
	public int maxPathRecurse(int[][] path, int x, int y) {
		if (x < 0 || y < 0 || y >= path.length || path[y].length >= x)
			return 0;
		
		return Math.max(path[y][x + 1], path[y + 1][x]) + path[y][x];
	}
	
	public int maxPathDP(int[][] maxPath) {
		int max = Integer.MIN_VALUE;
		
		for (int y = 0 ; y < maxPath.length ; y++) {
			for (int x = 0 ; x < maxPath[y].length ; x++) {
				
				int top = y - 1 > 0 ? maxPath[y - 1][x] : 0;
				int left = x - 1 > 0 ? maxPath[y][x - 1] : 0;
				
				maxPath[y][x] = Math.max(top, left);
				max = Math.max(maxPath[y][x], max);
			}
		}
		
		return max;
	}
}

- frankierock September 05, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include <iostream>
#include <cstdio>
#include <algorithm>

using namespace std;

void BuildMatrix(int *** pmaze,unsigned row_num,unsigned column_num)
{
*pmaze = new int*[row_num];
for(unsigned i=0;i<row_num;++i){
(*pmaze)[i] = new int[column_num];
}
}

void ReleaseMatrix(int ***pmaze,unsigned row_num)
{
if(!pmaze) return;

for(unsigned i=0;i<row_num;++i){
delete [](*pmaze)[i];
}

delete [](*pmaze);
}

void CoreSolve(int ***ppDistanceMatrix,unsigned matrix_size)
{
for(int i=0;i<matrix_size;++i){
for(int j=i;j<matrix_size;++j){
if(i-1>=0&&j-1>=0){
(*ppDistanceMatrix)[i][j] += max((*ppDistanceMatrix)[i-1][j],(*ppDistanceMatrix)[i][j-1]);
}else if(i-1>=0){
(*ppDistanceMatrix)[i][j] += (*ppDistanceMatrix)[i-1][j];
}else if(j-1>=0){
(*ppDistanceMatrix)[i][j] += (*ppDistanceMatrix)[i][j-1];
}
}

for(int k=i+1;k<matrix_size;++k){
if(k-1>=0&&i-1>=0){
(*ppDistanceMatrix)[k][i] += max((*ppDistanceMatrix)[k-1][i],(*ppDistanceMatrix)[k][i-1]);
}else if(k-1>=0){
(*ppDistanceMatrix)[k][i] += (*ppDistanceMatrix)[k-1][i];
}else if(i-1>=0){
(*ppDistanceMatrix)[k][i] += (*ppDistanceMatrix)[k][i-1];
}
}
}
}

void Solve()
{
unsigned matrix_size = 0;
int **ppmatrix = NULL;
cin>>matrix_size;
BuildMatrix(&ppmatrix,matrix_size,matrix_size);
for(unsigned i=0;i<matrix_size;++i){
for(unsigned j=0;j<matrix_size;++j){
cin>>ppmatrix[i][j];
}
}

int **ppDistanceMatrix = NULL;
BuildMatrix(&ppDistanceMatrix,matrix_size,matrix_size);
for(unsigned i=0;i<matrix_size;++i){
for(unsigned j=0;j<matrix_size;++j){
ppDistanceMatrix[i][j]=ppmatrix[i][j];
}
}

CoreSolve(&ppDistanceMatrix,matrix_size);
cout<<ppDistanceMatrix[matrix_size-1][matrix_size-1];

ReleaseMatrix(&ppmatrix,matrix_size);
ReleaseMatrix(&ppDistanceMatrix,matrix_size);
}

int main()
{
freopen("data.in","r",stdin);
freopen("data.out","w",stdout);

unsigned case_num = 0;
cin>>case_num;

for(unsigned i=1;i<=case_num;++i){
cout<<"Case #"<<i<<": ";
Solve();
cout<<endl;
}

return 0;
}

- zhouyouisme September 07, 2014 | 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