Amazon Interview Question Software Engineer / Developers
Country: United States
Interview Type: Phone Interview
Good one. You can do it with a memoization as well. Here is the Java code:
public int getMaxSum(int[][] input, int[][] dp, int i, int j) {
int N = intput.length;
int result = 0;
if (i >= 0 && i < N && j >= 0 && j < N) {
if (dp[i][j] != 0)
result = dp[i][j];
else {
result = Math.max(result, getMaxSum(input,dp, i + 1, j - 1) );
result = Math.max(result, getMaxSum(input,dp, i + 1, j) );
result = Math.max(result, getMaxSum(input,dp, i + 1, j + 1) );
result += input[i][j];
dp[i][j] = result;
}
}
return result;
}
I'm guessing you mean the maximum sum is 21. It's 3 + 8 + 3 + 7.
Here's the code.
import java.util.List;
import java.util.LinkedList;
import java.util.Vector;
public class SumFinder {
List<Integer> getNeighbors(int maxDepth, int currentIndex) {
List<Integer> neighbors = new LinkedList<Integer>();
neighbors.add(currentIndex);
neighbors.add(currentIndex + 1);
if(currentIndex != 0) {
neighbors.add(currentIndex - 1);
}
return neighbors;
}
int maxSum(Vector<Vector<Integer>> numbers, int curDepth, int previousIndex, int curSum) {
if(curDepth == numbers.size()) {
return curSum;
}
List<Integer> neighbors = getNeighbors(numbers.size(), previousIndex);
int maxSum = 0;
Vector<Integer> numbersThisDepth = numbers.get(curDepth);
int nextDepth = curDepth + 1;
for(Integer neighbor : neighbors) {
maxSum = Math.max(maxSum, maxSum(numbers, nextDepth, neighbor, curSum + numbersThisDepth.get(neighbor)));
}
return maxSum;
}
Vector<Integer> stringToInteger(String numbersAsString) {
Vector<Integer> numbers = new Vector<Integer>();
for(String number : numbersAsString.split(" ")) {
numbers.add(Integer.parseInt(number));
}
return numbers;
}
public static void main(String[] args) {
SumFinder sumFinder = new SumFinder();
Vector<Vector<Integer>> numbers = new Vector<Vector<Integer>>();
numbers.add(sumFinder.stringToInteger("3"));
numbers.add(sumFinder.stringToInteger("8 5"));
numbers.add(sumFinder.stringToInteger("2 3 1"));
numbers.add(sumFinder.stringToInteger("0 7 4 2"));
System.out.println(sumFinder.maxSum(numbers, 1, 0, numbers.get(0).get(0)));
}
}
Other than the numbers used, this is identical to a Project Euler problem (two actually, 18 and 67). Here's the code in Python:
inputString = """3
8 5
2 3 1
0 7 4 2"""
# Split input string into 2d array
splitToRows = inputString.split('\n')
numberTree = []
for i in range(0, len(splitToRows)):
numberTree.append(splitToRows[i].split(' '))
# Do stuff to it
for j in range(0, len(numberTree)-1):
tempRow = [0] * (j+2)
for h in range(0, j+1):
tempRow[h] = max(int(tempRow[h]), int(numberTree[j][h]) + int(numberTree[j+1][h]))
tempRow[h+1] = max(int(tempRow[h+1]), int(numberTree[j][h]) + int(numberTree[j+1][h+1]))
numberTree[j+1] = tempRow
print(max(numberTree[len(numberTree)-1]))
Other than the numbers used, this is identical to a Project Euler problem (two actually, 18 and 67). Here's the code in Python:
inputString = """3
8 5
2 3 1
0 7 4 2"""
# Split input string into 2d array
splitToRows = inputString.split('\n')
numberTree = []
for i in range(0, len(splitToRows)):
numberTree.append(splitToRows[i].split(' '))
# Do stuff to it
for j in range(0, len(numberTree)-1):
tempRow = [0] * (j+2)
for h in range(0, j+1):
tempRow[h] = max(int(tempRow[h]), int(numberTree[j][h]) + int(numberTree[j+1][h]))
tempRow[h+1] = max(int(tempRow[h+1]), int(numberTree[j][h]) + int(numberTree[j+1][h+1]))
numberTree[j+1] = tempRow
print(max(numberTree[len(numberTree)-1]))
Other than the numbers used, this is identical to a Project Euler problem (two actually, 18 and 67). Here's the code in Python:
inputString = """3
8 5
2 3 1
0 7 4 2"""
# Split input string into 2d array
splitToRows = inputString.split('\n')
numberTree = []
for i in range(0, len(splitToRows)):
numberTree.append(splitToRows[i].split(' '))
# Do stuff to it
for j in range(0, len(numberTree)-1):
tempRow = [0] * (j+2)
for h in range(0, j+1):
tempRow[h] = max(int(tempRow[h]), int(numberTree[j][h]) + int(numberTree[j+1][h]))
tempRow[h+1] = max(int(tempRow[h+1]), int(numberTree[j][h]) + int(numberTree[j+1][h+1]))
numberTree[j+1] = tempRow
print(max(numberTree[len(numberTree)-1]))
Other than the numbers used, this is identical to a Project Euler problem (two actually, 18 and 67). Here's the code in Python:
inputString = """3
8 5
2 3 1
0 7 4 2"""
# Split input string into 2d array
splitToRows = inputString.split('\n')
numberTree = []
for i in range(0, len(splitToRows)):
numberTree.append(splitToRows[i].split(' '))
# Do stuff to it
for j in range(0, len(numberTree)-1):
tempRow = [0] * (j+2)
for h in range(0, j+1):
tempRow[h] = max(int(tempRow[h]), int(numberTree[j][h]) + int(numberTree[j+1][h]))
tempRow[h+1] = max(int(tempRow[h+1]), int(numberTree[j][h]) + int(numberTree[j+1][h+1]))
numberTree[j+1] = tempRow
print(max(numberTree[len(numberTree)-1]))
#include <stdio.h>
inline int max( int a, int b, int c)
{
return (a>b)?( (a>c)? a:c ) : ((b>c)? b : c);
}
int find_max_sum(int A[4][4], int B[4][4], int n)
{
if( n<= 0 )
{
return 0;
}
else if(n == 1 )
{
return A[0][0];
}
else
{
int i=0, j=0;
for(i=0; i<n; i++ )
B[n-1][i] = A[n-1][i];
for(i=n-2; i>=0; i-- )
for( j=0; j<=i; j++ )
{
if( j == 0 )
B[i][j] = A[i][j] + max(0, B[i+1][j], B[i+1][j+1] );
else
B[i][j] = A[i][j] + max(B[i+1][j-1], B[i+1][j], B[i+1][j+1] );
}
return B[0][0];
}
}
int main()
{
int A[4][4] = {{3,-1,-1,-1},{8,5,-1,-1},{2,3,1,-1},{0,7,4,2}};
int B[4][4] = {0};//{;//{-1,-1,-1,-1},{-1,-1,-1,-1},{-1,-1,-1,-1},{-1,-1,-1,-1}};
printf("\n max sum is %d\n", find_max_sum(A,B,4));
}
Other than the numbers used, this is identical to a Project Euler problem (two actually, 18 and 67). Here's the code in Python:
inputString = """3
8 5
2 3 1
0 7 4 2"""
# Split input string into 2d array
splitToRows = inputString.split('\n')
numberTree = []
for i in range(0, len(splitToRows)):
numberTree.append(splitToRows[i].split(' '))
# Do stuff to it
for j in range(0, len(numberTree)-1):
tempRow = [0] * (j+2)
for h in range(0, j+1):
tempRow[h] = max(int(tempRow[h]), int(numberTree[j][h]) + int(numberTree[j+1][h]))
tempRow[h+1] = max(int(tempRow[h+1]), int(numberTree[j][h]) + int(numberTree[j+1][h+1]))
numberTree[j+1] = tempRow
print(max(numberTree[len(numberTree)-1]))
import java.util.ArrayList;
import java.util.List;
import java.util.TreeSet;
public class MaxSumFromLine {
public MaxSumFromLine() {
List<String> value = new ArrayList<String>();
value.add("3");
value.add("8 5");
value.add("2 3 1");
value.add("0 7 4 2");
value.add("0 7 4 2 9 19");
value.add("0 7 4 2 0 0 0 0 0 4 5 6 12");
calculateMAX(value);
}
private void calculateMAX(List<String> list) {
int sum = 0;
String str;
TreeSet<Integer> set = new TreeSet<Integer>();
for(int i=0;i<list.size();i++){
str = list.get(i);
String[] split = str.split("[\\s+]");
for(int j=0;j<split.length;j++){
set.add(Integer.parseInt(split[j]));
}
sum += set.last();
set.clear();
}
System.out.println("SUM "+sum);
}
public static void main(String[] args) {
new MaxSumFromLine();
}
}
1. sort each line in descending order (max in index 0)
2. sum up the first number of each line to get max sum
Code in C#
public int FindMax()
{
var a1 = new int[1] {3 };
var a2 = new int[2] {8,6 };
var a3 = new int[3] {2,3,1 };
var a4 = new int[4] {11,7,4,8};
var input = new List<int[]>();
input.Add(a1);
input.Add(a2);
input.Add(a3);
input.Add(a4);
var maxCount = 0;
var currentArrayIndex = 0;
for (int i = 0; i < input.Count; i++)
{
var currentInput = input[i];
maxCount += FindMaxCountFromThisLine(ref currentArrayIndex, currentInput);
}
return maxCount;
}
private int FindMaxCountFromThisLine(ref int currentArrayIndex, int[] currentInput)
{
var maxCount = 0;
var index = currentArrayIndex;
for (int i = index - 1; i <= index + 1; i++)
{
if (i < 0)
{
continue;
}
if (i >= currentInput.Count())
{
break;
}
if (currentInput[i] > maxCount)
{
maxCount = currentInput[i];
currentArrayIndex = i;
}
}
return maxCount;
}
Dynamic programming?
say input is arr[][] where arr[i] has i+1 elements
#define MAX( x , y) (((x)>(y))?(x):(y))
#define MAX3(x , y , z) MAX( MAX(x,y) , z )
#define VALID( x , l ) ( ( ((x)>=0) && ((x)<(l)) ) ? (x) : (( (x)>=0 )?((l)-1):0) )
int maxPathVal(int ** arr, int n) {
int res = 0;
for (int lvl=1; lvl<n; lvl++) {
for (int pos=0; pos<=lvl; pos++) {
arr[lvl][pos] += MAX3( arr[VALID(lvl-1,n)][VALID(pos-1,lvl)] ,
arr[VALID(lvl-1,n)][VALID(pos,lvl)] ,
arr[VALID(lvl-1,n)][VALID(pos+1,lvl)] );
if (lvl==n-1 && max<arr[lvl][pos]) max=arr[lvl][pos];
}
return res;
}
public static int findAdjacentMx(){
int [][] array={{3},
{8,5},
{2,3,1},
{0,7,4,2}};
int [] state=new int [array.length];
state[0]=array[0][0];
int irow=1;
while (irow<array.length){
for (int i=0;i<=irow;++i){
if (state[irow-1]+array[irow][i]>state[irow]){
state[irow]=state[irow-1]+array[irow][i];
}
}
irow++;
}
return state[state.length-1];
}
public class InputFile {
public static void main(String [] args){
try {
BufferedReader reader = new BufferedReader(new FileReader("c:/Input.txt"));
String line = null;
StringBuffer buffer = new StringBuffer();
int count = 0;
int total = 0;
while((line=reader.readLine())!= null){
count++;
total+=getMaximumOfLine(line,count);
}
System.out.println("Total is"+total);
} catch (FileNotFoundException e) {
e.printStackTrace();
} catch (IOException e){
e.printStackTrace();
}
}
private static int getMaximumOfLine(String line, int count) {
StringTokenizer str = new StringTokenizer(line," ");
int maximum=0;
while(str.hasMoreElements()){
Integer abc = Integer.parseInt(str.nextToken());
if(maximum < abc)
maximum= abc;
}
System.out.println("max in line "+count+" is"+maximum);
return maximum;
}
}
Simple DP should do the trick. Start from the last row and work up to the 1st row
int max_sum(int **arr, int row) { /*allocate a 2D array */ for(i=size(arr)-2_; i>=0; i--) { for(j=0; j<i ; j++) { if(j==0) { max[i][j] = max((arr[i][j]+arr[i+1][j]),(arr[i][j]+arr[i+1][j+1])) } else { max[i][j] = max((arr[i][j]+arr[i+1][j]),(arr[i][j]+arr[i+1][j+1]),(arr[i][j]+arr[i+1][j-1])) } } } return(max[0][0]); }Time complexity O(n^2)
- Prakash May 25, 2012