Amazon Interview Question for Software Engineer / Developers

Team: Data Storage
Country: India
Interview Type: Phone Interview

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

yo kadanes algorithm will surely work here :)
int Maxsubarray(int a[],int n)
{
int sum,maxsum=INT_MIN;
int i,j;
j=0;
start=j;
for(i=0;i<n;i++)
{
sum=sum+a[i];
if(sum>maxsum)
{
maxsum=sum;
end=i;
}
if(sum<0)
{
j=i;
start=j;
sum=0;
}
}
return maxsum;
}

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

both will fail when array has all negative numbers.

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

Assumption here is that if all numbers are negative I return 0 . If all the numbers are negative then the solution is -maximum number , which is not difficult to find

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

This solution will work even if array has all negative numbers.

int maxSubArraySum(int a[], int size)
{
int max_so_far = a[0];
int max_ending_here = 0;
int i;
for(i = 1; i < size; i++) /* start from 2nd element onwards */
{
max_ending_here = max_ending_here + a[i];
if(max_ending_here < 0)
max_ending_here = 0;
if(max_so_far < max_ending_here)
max_so_far = max_ending_here;
}
return max_so_far;
}

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

The previous one won't work for all -ve number aray, but i guess the following code would do it.

int maxSubArraySum(int a[], int size)
{
int max_so_far = a[0];
int max_ending_here = 0;
int i;
for(i = 1; i < size; i++) /* start from 2nd element onwards */
{
max_ending_here = max_ending_here + a[i];

if(max_so_far < max_ending_here)
max_so_far = max_ending_here;
}

if(max_ending_here < 0)
max_ending_here = 0;

return max_so_far;
}

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.