## Amazon Interview Question for Software Engineer / Developers

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

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

What should be the length of subarray??

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

Obviously it has to be contiguous. Otherwise just sum up all the positive numbers.

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

``````def maxSubarray(arr:Array[Int]): Array[Int]= {

var maxEndedArr = new Array[Int](arr.length)
var maxArr = new Array[Int](arr.length)

maxEndedArr(0) = max(0, arr(0))
maxArr(0) = max(0, arr(0))

var index = 1;

while( index < arr.length ){

val value = arr(index)

maxEndedArr(index) = max(0, maxEndedArr(index-1) + value)
maxArr(index) = max( maxArr(index-1), maxEndedArr(index) )

index += 1
}

val maxSumValue = maxArr( maxArr.length-1)

var i = maxEndedArr.length-1
var from = -1
var to = -1

while( i >=0 && from < 0 ){

if( maxEndedArr(i) == maxSumValue ){
to = i
}

if( maxEndedArr(i) == 0 && to > 0 ){
from = i+1
}

i -= 1
}

val maxSubarray = new Array[Int](to - from + 1)

var copyIndex = 0

while( from+copyIndex < to + 1 ){
maxSubarray(copyIndex) = arr(from+copyIndex)
copyIndex += 1
}

return maxSubarray
}``````

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

Optimized version:

``````/**
* Use one pass by original array.
* Time: O(N)
* Space: O(N)
*/
def maxSubarray(arr:Array[Int]): Array[Int]= {

if( arr == null ){
throw new IllegalArgumentException("NULL array passed")
}

if( arr.length == 0 ){
return new Array[Int](0)
}

var maxEnded = max(0, arr(0))
var maxAll = max(0, arr(0))

var firstNonZeroIndex = -1
var maxFromIndex = -1
var maxToIndex = -1

for( i <- 1 to arr.length-1){

var newMaxEnded = max(0, maxEnded + arr(i) )
var newMaxAll = max( maxAll, newMaxEnded )

if( maxEnded == 0 && newMaxEnded > 0 ){
firstNonZeroIndex = i
}

if( newMaxEnded > maxAll ){
maxFromIndex = firstNonZeroIndex
maxToIndex = i
}

maxEnded = newMaxEnded
maxAll = newMaxAll

}

// up to N elements
val maxSubarray = new Array[Int](maxToIndex - maxFromIndex + 1)

for( i <- 0 to maxSubarray.length-1 ){
maxSubarray(i) = arr(maxFromIndex + i)
}

return maxSubarray
}``````

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

good

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

what if -1 -2 -3 -4 -5 -6 -7 -8 -9 -10

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

@zhou: the answer is 0 if all are negative
and the answer is sum of all numbers if all the numbers are positive

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

After sorting leave first element and return the pointer of rest of the array. Does it meet your requirement? Or I misunderstood it?

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

This would be the naive solution to give first, but obviously too slow for the intention of this question.

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

Just keep track of current maximum sum, if the current element alone is bigger than the sum, then update the sum with current element.

See the code below in action: ideone.com/bPblj

``````int GetMaxSum(const vector<int>& array, int* max_lb, int* max_ub) {
int maxsum = std::numeric_limits<int>::min();
int sum = 0;

int lb = 0;
*max_lb = *max_ub = lb;

int len = array.size();
for (int i = 0; i < len; ++i) {
sum += array[i];
if (sum < array[i]) {
sum = array[i];
lb = i;
}
if (maxsum < sum) {
maxsum = sum;
*max_lb = lb;
*max_ub = i;
}
}
return maxsum;
}``````

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

#include<stdio.h>

int main()
{
int arr[13]={-11,-2,6,4,5,10,7,-9,11,15,16,-5,-8};
int previous_sum=0;
int current_sum=0;
int i=0;
for(i=0;i<13;i++)
{
if(arr[i]<0)
{
if(previous_sum<=current_sum)
previous_sum=current_sum;
current_sum=0;
}
else
{

current_sum=current_sum+arr[i];

}

}
if(previous_sum>=current_sum)
{

current_sum=previous_sum;
}
printf("Value is %d\n",current_sum);
}

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.