## Amazon Interview Question for Software Engineer / Developers

Country: United States
Interview Type: Phone Interview

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

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)

Comment hidden because of low score. Click to expand.
0

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;
}``````

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

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.Vector;

public class SumFinder {

List<Integer> getNeighbors(int maxDepth, int currentIndex) {
if(currentIndex != 0) {
}
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(" ")) {
}
return numbers;
}

public static void main(String[] args) {
SumFinder sumFinder = new SumFinder();
Vector<Vector<Integer>> numbers = new Vector<Vector<Integer>>();
System.out.println(sumFinder.maxSum(numbers, 1, 0, numbers.get(0).get(0)));
}
}``````

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

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]))``````

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

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]))``````

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

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]))``````

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

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]))``````

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

``````#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));
}``````

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

Can any one help me understand what exactly is the question?

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

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]))``````

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

is there any algo bettr than O(n^2)????

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

is there any algo bettr than O(n^2)????

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

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("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++){
}
sum += set.last();
set.clear();
}

System.out.println("SUM "+sum);
}

public static void main(String[] args) {
new MaxSumFromLine();
}

}

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

1. sort each line in descending order (max in index 0)
2. sum up the first number of each line to get max sum

Comment hidden because of low score. Click to expand.
0

No... The numbers should be adjacent

Comment hidden because of low score. Click to expand.
0

No... The numbers should be adjacent

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

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[]>();

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;
}``````

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

This can be solved in nxn. This is analogous to finding shortest path in a graph. Each node of the graph is connected to the adjacent nodes in the next row and the largest value is the shortest path here

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

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;
}``````

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

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];
}

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

public class InputFile {

public static void main(String [] args){

try {
String line = null;
StringBuffer buffer = new StringBuffer();
int count = 0;
int total = 0;
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;
}

}

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

---max total from top to bottom. in the above case, the sum is 5 + 3 + 7 = 15
if I correctly read this sentence - will be second vertical line.

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

i=0;
array[]=line.split(" ");

maxNumIndex=findLargestAmoung(array[i],array[i+1],array[i-1]) //should checks if all these elements really exist or i should not give arrayBounds

sum+=array[maxNumIndex]

i=maxNumIndex;
}

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

Start from last row and memoize.
Maxsum(n) = max { ni+ Maxsum(n-1) } i=0 to M
Worstcase (MxN) because we hit each element only once.

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.

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