Amazon Interview Question
Country: United States
// 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)
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;
}
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))
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);
}
}
if no require the trace, dp can handle it.
if require the tracce, i can only get the dfs method .
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.
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;
}
}
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()
}
}
}
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;
}
}
#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;
}
Solution in O(RC)
- shukad333 August 31, 2014