## Amazon Interview Question for SDE-2s

• 1
of 1 vote

Country: India
Interview Type: Phone Interview

Comment hidden because of low score. Click to expand.
2
of 4 vote

This can be solved in single pass through the array .. It is called Kandane's Algorithm

``````public class Kadane {

public static void main(String[] args) {
int[] intArr={3, -1, -1, -1, -1, -1, 2, 0, 0, 0 };
//int[] intArr = {-1, 3, -5, 4, 6, -1, 2, -7, 13, -3};
//int[] intArr={-6,-2,-3,-4,-1,-5,-5};
findMaxSubArray(intArr);
}

public static void findMaxSubArray(int[] inputArray){

int maxStartIndex=0;
int maxEndIndex=0;
int maxSum = Integer.MIN_VALUE;

int cumulativeSum= 0;
int maxStartIndexUntilNow=0;

for (int currentIndex = 0; currentIndex < inputArray.length; currentIndex++) {

int eachArrayItem = inputArray[currentIndex];

cumulativeSum+=eachArrayItem;

if(cumulativeSum>maxSum){
maxSum = cumulativeSum;
maxStartIndex=maxStartIndexUntilNow;
maxEndIndex = currentIndex;
}
else if (cumulativeSum<0){
maxStartIndexUntilNow=currentIndex+1;
cumulativeSum=0;
}
}

System.out.println("Max sum         : "+maxSum);
System.out.println("Max start index : "+maxStartIndex);
System.out.println("Max end index   : "+maxEndIndex);
}

}``````

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

The above program doesn't work for the input { -9, 3, 3, 4, 3, -7, -5, 1, -2, 5, 4, 2, -5, 4 };

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

We do not need 'nlogn', we only need O(n). As mentioned above, it is a Kadane Algorithm.

``````int length ;
int a[]={-12, 14, 0, -4, 61, -39};
length = a.length;

int absoluteMax=0, localMax=0, startIndex=0, lastIndex=0, tempStartIndex=0;

for (int index = 0; index < length;index++) {
localMax= localMax + a[index];
if(localMax < 0){ localMax=0; tempStartIndex = index + 1;}
if(absoluteMax < localMax) {
absoluteMax = localMax;
lastIndex = index;
startIndex = tempStartIndex;
}
}``````

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

Hi Raaz,

Can u please clarify this
P = {4,6,-3,1,5,9,-2} is the array
S ={1,5,9} has sum of 15
but Q = {4,6,-3,1,5,9} has sum of 22.
so is S is correct or Q...?

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

Hello Bhupal,
My mistake..correct output should be Q = {4,6,-3,1,5,9}.

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

Why isn't this array the max?
{4,6,1,5,9}

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

It's not max because you're skipping elements in the output array. Remember, the sub array "Must have the same sequence"

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

First thought is brute force, that thats just a start.
Second thought would be to think of the array as the bottom tier of a quasi-binary tree, building up towards the final sum as the 'root' of the tree.
You could then walk the tree from the root, looking at each individual tier, looking for the maximal node combination

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

Specially, think MinMax or AlphaBeta search routines for this one.

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

``````//linear time O(n), traverse from left to right

//initialize variables
int i = 0;
int maxSum = 0; // sum of current maximum array
int LastSum = 0; // sum of current extending array
int maxBegin = 0; //start position of current maximum array
int LastBegin = 0; //start position of current extending array
int maxLength = 1; // length of current maximum array
int LastLength = 1; // length of current extending array

for(i=0; i<arr.length(); i++)
{
//if LastSum and the current integer are both non-negative or LastSum >= |arr[i]|, merge them
if(LastSum >= 0 && (arr[i] >= 0 || LastSum >= -arr[i]))
{
LastSum += arr[i];
LastLength ++;
}

//if arr[i] < 0, and |arr[i]| > LastSum , restart the calculation
else if arr[i] < -LastSum //note that LastSum  is maintained non-negative
{
LastLength = 0;
LastSum = 0;
if(i< arr.length)
LastBegin = i+1;
}

///compare LastSum and maxSum, if LastSum  is greater, update the array which has maximum sum.
if( LastSum >= maxSum )
{
maxSum = LastSum;
maxBegin = LastBegin;
maxLength = LastLength;
}

}``````

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

This is called Maximum Sub Array problem (refer MIT Introduction to Algorithms by Cormen)

``````public class MaxSubArray {

private static class SubArray {
int start;
int end;
int sum;

SubArray(int start, int end, int sum) {
this.start = start;
this.end = end;
this.sum = sum;
}
}

private SubArray findMaxCrossingSubArray(int[] data, int start, int mid,
int end) {
int sum = 0;
int leftSum = Integer.MIN_VALUE;
int maxLeft = mid;
for (int index = mid; index >= start; index--) {
sum += data[index];
if (leftSum < sum) {
leftSum = sum;
maxLeft = index;
}
}

int rightSum = Integer.MIN_VALUE;
int maxRight = mid + 1;
sum = 0;
for (int index = mid + 1; index <= end; index++) {
sum += data[index];
if (rightSum < sum) {
rightSum = sum;
maxRight = index;
}
}

return new SubArray(maxLeft, maxRight, leftSum + rightSum);
}

public SubArray findMaxSubArray(int[] data, int start, int end) {

if (start == end)
return new SubArray(start, end, data[start]);

int mid = (start + end) / 2;
SubArray ls = findMaxSubArray(data, start, mid);
SubArray rs = findMaxSubArray(data, mid + 1, end);
SubArray mcs = findMaxCrossingSubArray(data, start, mid, end);

if (ls.sum >= rs.sum && ls.sum >= mcs.sum)
return ls;
else if (rs.sum >= ls.sum && rs.sum >= mcs.sum)
return rs;
else return mcs;
}

public static void main(String[] args) {

int[] data = { -9, 3, 3, 4, 3, -7, -5, 1, -2, 5, 4, 2, -5, 4 };
MaxSubArray msa = new MaxSubArray();
SubArray sa = msa.findMaxSubArray(data, 0, data.length - 1);
System.out.println("Start: " + sa.start + ", End: " + sa.end + ", Sum: "
+ sa.sum);
}
}``````

The code runs in O(n log n)

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

dp

``````public static  void findMaxSeq(int [] seq){
int [] dp = new int [seq.length] ;
dp  = seq  ;
int max = Integer.MIN_VALUE ;
int end = -1 ;
int start = -1 ;
for (int i = 1 ; i < seq.length ; ++i){
if (seq[i] + dp[i-1]  <= 0 ){
dp [i] = seq[i] ;
}else{
dp [i] = seq[i] + dp[i-1] ;
}

if (dp[i] > max){
max = dp [i];
end = i;
}
}

end = dp  > max ? 0 : end;

for (int i = 0 ; i < dp.length ; ++i){
if (dp[i] >= 0){
start = i ;
break;
}
}

System.out.println("from " + start + " to "  + end);``````

}

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

``````o(n) solution,  in two passes we should be able to find the max sub array without disturbing the sequence

public static void maxSubArray(int[] arr)
{

int cummaltive = 0;
int max = 0;
int maxIndex = 0;

//one pass - find the max index that produces max sub array
for(int i = 0; i< arr.length; i ++)
{
cummaltive = cummaltive+arr[i];

if(cummaltive > max)
{
max = cummaltive;
maxIndex = i;
}
}

//second pass loop till max pointer

for(int i = 0; i<=maxIndex; i ++)
{
System.out.println(arr[i]);
}

}``````

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

your solution only takes into account arrays that start from the 0th element to n (where n is some index in the array).

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

``````void max(int a[],int n)
{
int i=0,sum=0,max=0,end=0;
for(i=0;i<n;i++)
{
sum = sum+a[i];
if(sum>max)
{
max=sum;
end=i;
}
if(sum<0)
sum=0;
}
printf("Maximum Sum is %d\n",max);
while(max>0)
{
printf("%d\t",a[end]);
max = max-a[end];
end--;
}
printf("\n");
}``````

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

C++ function:

``````{
int * maxSequence(int * arr, int length)
{
int max = 0, start = 0, end = 0, actual_start = 0, sum = 0;
for(int i = 0; i < length; i++)
{
sum += arr[i];
if(sum < 0)
{
sum = 0;
start = i + 1;
}
else if(sum > max)
{
max = sum;
end = i;
actual_start = start;
}
}

int extension = end - actual_start + 1;
int * result = new int[extension];
for(int i = 0; i < (extension); i++)
result[i] = arr[i + actual_start];

return result;
}``````

}

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

int a[] = { -9, 3, 3, 4, 3, 20, -50, -5, 4};
int sum=0;
int max=0;
int pos=0;
for(int i=0;i<a.length;i++)
{
sum+=a[i];
if(sum>=max)
{
max=sum;
pos=i;
}
}
System.out.println(max+ " "+pos);

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.