## Amazon Interview Question for Software Engineer / Developers

Country: India
Interview Type: Phone Interview

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

``````private static int maxContigousWithoutDP(int A[], int n) {
int sumSoFar = 0, sumEndingHere = 0;
for (int i = 0; i < n; i++) {
sumEndingHere = sumEndingHere + A[i];
if (sumEndingHere < 0) {
sumEndingHere = 0;
continue;
}
if (sumSoFar < sumEndingHere)
sumSoFar = sumEndingHere;
}
return sumSoFar;
}``````

Comment hidden because of low score. Click to expand.
3
of 5 vote

Maintain a cumulative sum (say in a hash), and for current sum S check if S-N exists.

Possible Pseudo code...

``````Pair LargestSubArray(int [] A, int sum) {

HashMap <int, int> H = new HasMap<int, int>();
// Cumulative sum is the key.
// The value is the leftmost index.

H.Insert(0, 0);
int Sum = 0;

int max_left = 0;
int max_right = 0;
int max_len = 0;

for(int j = 0; j < A.Length; j++) {
Sum += A[j];
if (H.containsKey(Sum-N)) {
int possible_left = H[Sum-N];
int possible_right = j;
int possible_len = possible_right - possible_left;

if (possible_len>= max_len) {
max_left = possible_left;
max_right = possible_right;
max_len = possible_len;
}
}

if (!H.ContainsKey(Sum)) {
H[Sum] = j+1;
}
}
return new Pair(max_left, max_right);
}``````

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

@Nasser: Huh?

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

I think this works.

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

``start from left most end add  while going from right to left whenever you find sum equal to "N" just count how many steps you have moved from start position save it in "max" dont' stop here go to right end if you ever again found the sum equal to "N" give new value to "max",now again move one step further from start position ,now check the length of array from this point if it is smallerr than "max " then the "max" you have found is reallly max other repeat the process.``

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

good idea to keep track of the possible left most position!

O(N) time.

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

Is it necessary to store each different sum in the hashtable?, wouldn't be enough to store only those ones that sum up N?

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

O(n^2) time. O(n^2) space

``````def maximum_subarray(array, n):
l = len(array)
c = [[0 for i in range(l)] for j in range(l)]
max_length = 0
for i in range(l):
c[i][i] = array[i]
if c[i][i] == n:
max_length = 1

for size in range(2, l + 1):
for i in range(0, l - size + 1):
j = size - 1 + i
c[i][j] = c[i][j - 1] + array[j]
if c[i][j] == n and size > max_length:
max_length = size

return max_length``````

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

How about this?

public class largestSubArray
{
private static int[] arr = {7, -7, 3, 4, 1, -1, 0, 0, 0, 0};
private static int N = 7;

public static boolean findN(int[]dp, int sum, int start, int end)
{
if ( start > end )
return false;
if ( dp[start] == end )
return false;
if ( sum == N )
{
System.out.print("The largest contiguous sub-array is starting from index " + start + ", ");
System.out.println("ending at index " + end);
return true;
}
dp[start] = end;
return findN(dp, sum-arr[start], start+1, end) || findN(dp, sum-arr[end], start, end-1);
}

public static void main(String[] args)
{
int[] dp = {-1, -1, -1, -1, -1, -1, -1, -1, -1, -1};
int start = 0;
int end = arr.length-1;
int sum = 0;
for ( int i = start; i <= end; i++ )
sum += arr[i];
boolean result = findN(dp, sum, start, end);
if ( result == false )
System.out.println("Sorry, N is not reachable by the elements");
}
}

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

This is a maximum subarray problem which can be solved using Kadane's solution:

``````def max_subarray(A):
max_ending_here = max_so_far = 0
for x in A:
max_ending_here = max(x, max_ending_here + x)
max_so_far = max(max_so_far, max_ending_here)
return max_so_far``````

Reference: Wikipedia

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

Huh? LOL. -100.

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

My bad! misread the question

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

Here is the code for Kadane's algorithm

``````int Kadane(int* A,int n,int& startIndex,int& endIndex)
{
startIndex = 0;
endIndex = 0;
int maxSubTotal=1<<31; // -INFINITY
int currSubTotal=0;
int j=0;
for(int i=0; i<n ;i++)
{
currSubTotal=currSubTotal+A[i];
if(currSubTotal>maxSubTotal)
{
startIndex=j;
endIndex=i;
maxSubTotal=currSubTotal;
}
if(currSubTotal<0)
{
currSubTotal=0;
j=i+1;
}
}
return maxSubTotal;
}``````

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

LOL! -100.

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

int max(int a,int b)
{
return (a>b?a:b);
}
main()
{
int a[]={1,2,3,4,};
int sum=5,temp,maxlen=0,k=0;
temp=sum;
int n=sizeof(a)/sizeof(int);
int b[100],start=0,end=0;
for(int i=0;i<100;i++)
b[i]=-1;
b[a[0]]=0;
for(int i=1;i<n;i++)
{
a[i]+=a[i-1];
b[a[i]]=i;
}
for(int i=0;i<n;i++)
{
sum+=a[i];
if(b[sum]>=0)
{
maxlen=max(maxlen,(b[sum]-(i)));
/* if(k>maxlen)
{
start=i+1;
end=b[sum];
} */
}
sum=temp;
}
printf("the longest length is %d",maxlen);
getch();
}

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

#include<stdio.h>
int main()
{
int arr[]={-1,1,3,4,-7,7};
int given_num=7;
int i=0,max_start=0,max_end=0,current_start=0,current_sum=0,count=0,max_count=0;
for(i=0;i<6;)
{
current_sum=current_sum+arr[i];
if(current_sum==given_num)
{
//max_start=current_start;
//max_end=i;
count=i-current_start +1;
if(count>max_count)
{
max_start=current_start;
max_end=i;
max_count=count;
}
i++;
}
else if(current_sum<=0)
{
current_start=i+1;
current_sum=0;
i++;
}
else if(current_sum > given_num)
{
i=++current_start;
current_sum=0;
}
else
i++;
}
for(i=max_start;i<=max_end;i++)
printf("%d\n",arr[i]);
return 0;
}

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

``````public class arraypuzzle{
public static void main(String args[]){
int N = 6;
//int a[] = {7, 2, 2, 8, 1,1,2,2,4, 22, 5, 6, 11};
int a[] = {1,2,3,-5,1,5,0,1,1,1,1,1};
int largestFrom = -1;
int largestSize = -1;
int temp =0;

for(int i=0; i<a.length; i++){
int j=1;
temp = a[i];
while(j<a.length && (i+j)<a.length){
System.out.println("temp:" + temp + " a[i+j]:" + a[i+j]);
temp = temp+a[i+j];
j++;
if(temp==N){
if(largestSize<(j-1)){
largestFrom=i;
largestSize = j-1;
System.out.println("largestFrom:" + largestFrom);
System.out.println("largestSize:" + largestSize);
}

}
}
System.out.println("total:" + temp);

if(temp==N){
if(largestSize<(j-1)){
largestFrom=i;
largestSize = j-1;
System.out.println("largestFrom:" + largestFrom);
System.out.println("largestSize:" + largestSize);
}

}
}
System.out.println("largestFrom:" + largestFrom);
System.out.println("largestSize:" + largestSize);
System.out.println("");
for(int i=largestFrom; i<=(largestFrom+largestSize);i++){
System.out.print(a[i] + " ");
}
}``````

}

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

``````'''
FUNCTION
Given a array, find the largest contiguous sub-array having its sum equal to N.
'''
def find_largest_contiguous_array(inputArray, N):
print '[Details]'
print 'Given a array, find the largest contiguous sub-array having its sum equal to N.'
print ''
print '[Running]'

# read the list
print 'The input array is: ',
print inputArray
print 'The target number N is: ',
print N
arrayLen = len(inputArray)
sumupDict = {}
hit = [-1, -1, -1] # length of the subarray, posBegin, posEnd

for currentPos in range (0, arrayLen-1):
for previousPos in sumupDict.keys():
if previousPos in sumupDict:
oldSum = sumupDict[previousPos][0]
sumupDict[previousPos] = [oldSum+inputArray[currentPos], currentPos]
newSubarrayLen = currentPos - previousPos + 1
if (sumupDict[previousPos][0] == N) & (newSubarrayLen > hit[0]): # a new hit
hit = [newSubarrayLen, previousPos, currentPos+1]
sumupDict[currentPos] = [inputArray[currentPos], currentPos]; # [sum, posEnd]

print '[Result]'
print 'The largest subset is: ',
print inputArray[hit[1]:hit[2]]

if __name__ == '__main__':
kk = [1,2,3,4,5,6,7 ,-7,0,7,0,0,0,0,7,9]
N = 14
find_largest_contiguous_array(kk, N)``````

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

Here is my solution. If having more than one sub-array match, this solution will get the one from start index largest. If you want to get all of them, then use the HashMap<Integer,Integer> to start start, end entry and iterate to display all results.

``````public static void main( String ... args) {
int arr[]= { -2, -3, 4, -1, -2, 1, 5, -3, 2, -2, -3, 6, -1, -2, 1, 5, -3, 2};
largestSubArrayMatchSum(arr, 2);
}

public static void largestSubArrayMatchSum( int[] arr, int num) {

int sum = 0;
int i = 0;
int max = 0;
int start= 0;
int j = 0;
while( j < arr.length) {
sum += arr[i];
if( sum >= num) {
if( sum == num) {
int prev = max;
max = Math.max(max, i );
if( max > prev) {
start = j;
}
};
}
++i;
if( i == arr.length) {
++j;
i = 0;
}
}

if( max != 0) {
//Found.
System.out.println("sub-array based-0 index [from - to]:[" + start + " - " + max + "]");
}
}``````

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

Here is my solution. Notice that there might be more than one sub arrays on the solution. This solution just take the last one found largest sub-array that satisfy the question (i.e. the one with start index largest). If you want to keep all of them, use HashMap<Integer,Integer> to keep the start/end index pairs of the matched.

``````public static void main( String ... args) {
int arr[]= { -2, -3, 4, -1, -2, 1, 5, -3, 2, -2, -3, 6, -1, -2, 1, 5, -3, 2};
largestSubArrayMatchSum(arr, 2);
}

public static void largestSubArrayMatchSum( int[] arr, int num) {

int sum = 0;
int i = 0;
int max = 0;
int start= 0;
int j = 0;
while( j < arr.length) {
sum += arr[i];
if( sum >= num) {
if( sum == num) {
int prev = max;
max = Math.max(max, i );
if( max > prev) {
start = j;
}
};
}
++i;
if( i == arr.length) {
++j;
i = 0;
}
}

if( max != 0) {
//Found.
System.out.println("sub-array based-0 index [from - to]:[" + start + " - " + max + "]");
}
}``````

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

/*Find largest sub-contigous array.*/
void FindLargSubContgArray() {

int a[] = { -1, 3, -5, 4, 6, -1, 2, -7, 13, -3};

int max_end_here = 0;
int max_so_far = 0;
int start_sub_array = 0;
int end_sub_array = 0;
bool found = false;

int len = (sizeof(a)/sizeof(a[0]));

for(int i=0; i < len; i++) {

if(a[i] >= 0) found = true;

max_end_here = ( a[i] + max_end_here > 0 ? (a[i] + max_end_here): 0);

if(max_end_here == 0) start_sub_array = i;
if(max_end_here > max_so_far) end_sub_array = i;

max_so_far = (max_end_here > max_so_far ? max_end_here:max_so_far);
}
if(found) {
cout << "Start position of largest sub-array is: " << start_sub_array+1 << endl;
cout << "End position of largest sub-array is: " << end_sub_array << endl;
}
else
cout << "No sub-contigous array could be found." << endl;
}

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

/*Find largest sub-contigous array.*/
void FindLargSubContgArray() {
int a[] = { -1, 3, -5, 4, 6, -1, 2, -7, 13, -3};

int max_end_here = 0;
int max_so_far = 0;
int start_sub_array = 0;
int end_sub_array = 0;
bool found = false;

int len = (sizeof(a)/sizeof(a[0]));

for(int i=0; i < len; i++) {

if(a[i] >= 0) found = true;

max_end_here = ( a[i] + max_end_here > 0 ? (a[i] + max_end_here): 0);

if(max_end_here == 0) start_sub_array = i;
if(max_end_here > max_so_far) end_sub_array = i;

max_so_far = (max_end_here > max_so_far ? max_end_here:max_so_far);
}
if(found) {
cout << "Start position of largest sub-array is: " << start_sub_array+1 << endl;
cout << "End position of largest sub-array is: " << end_sub_array << endl;
}
else
cout << "No sub-contigous array could be found." << endl;
}

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

Anyone with faster than O(n2) algorithm on this one? Check this one

7, 3, 4, 4, 3, 1, 8, 1, 1, 1, 3, 1 , 2, -1, -2, 3
N=21

I doubt if this can be done Order(N). Consider the 2nd 3. It is involved in 3 sequences that add up to 21. I think there is no option, but to calculate all n (n+1)/2 sums.

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

Its a classic DP problem

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

onestopinterviewprep.blogspot.com/2014/03/namespace-arrayproblem-write-function.html

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

onestopinterviewprep.blogspot.com/2014/03/namespace-arrayproblem-write-function.html

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

can be done in O(n) time complexity
1. take 2 variable i, j,s (all r initially zero)
2. increment j and sum s+=a[j] till you get s>=given sum (and maintatin the count also) .
3. if(equal as above) then store the value of i , j , count in other variable .
4. else if(greater) then increment the i , and decrement the s with a[i] till u get s<=given sum.
4.a if(equal) then no probs , just cmpre the curr count with the prev stored count to chek max val and assign acc to it .
4.b else if(less) then increment j , s+=a[j] and check s with the givn sum .

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

@Barney even this came to my mind. But i think here the question is about largest subarray having given sum.

e.g. 1 2 3 5 -5
and say required sum = 6 then answer should be whole array not just 1 2 3.

But with what you shared i think we would be getting only 1 2 3 as answer which would be correct per se. But won't be largest.

Thoughts?

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

yes , u r ryt . I didn't think about this . Above algo only works for non negative numbers . I think any modification wont do any gud in dis

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

main()
{
int a[24],i,j,n;
clrscr();
printf("\n\n\n\n");
printf("Enter the no");
scanf("%d",&n);
printf("\nenter the list");
for(i=0;i<23;i++)
scanf("%d",&a[i]);
fun(a,n);
getch();
return 0;
}
fun(int *a,int n)
{
int i,j,sum=0,count[24]={0},c=0,d=0,k,pos,l;
for(i=0;i<23;i++)
{
k=i;
for(j=i+1;j<23;j++)
{
if(k==d)
sum=sum+a[i]+a[j];
else
sum=sum+a[j];
if(sum>n)
{
sum=0;
d++;
break;
}
else if(sum==n)
{
d++;
if(i==0)
count[i]=1;
else
count[i]=2+c;
sum=0;
break;
}
else if(sum<n)
{
c++;
d++;
}
}
d=i+1;
c=0;
}
l=count[0];
for(i=1;i<23;i++)
{
if(l<count[i])
{
l=count[i];
pos=i;
}
}
for(j=pos;j<pos+l;j++)
printf(" %d",a[j]);
}

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

Taking arrays when array contains +ve numbers too. time complexity O(N)

``````class LargestSumContiguousSubarray{

public static void maxSubArraySum(int[] a)
{
int currentSum=0;
int maxSum=0;
int endIndex=0;
int beginIndex=0;

for(int i=0;i<a.length;i++)
{
currentSum+=a[i];
if(currentSum<0)
currentSum=0;
if(currentSum>maxSum)
{
maxSum=currentSum;
endIndex=i;
}

}
int temp=maxSum;
for(int j=endIndex;j>=0;j--)
{
temp-=a[j];
if(temp==0)
{
beginIndex=j;
break;
}
}
System.out.println("endIndex: "+endIndex);
System.out.println("beginIndex: "+beginIndex);
}

public static void main(String[] args)
{
int[] a= {-2, -3, 4, -1, -2, 1, 5, -3};
maxSubArraySum(a);
}``````

}

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

Why is this O(n)?

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

My approach was different. I take a window from left to right and narrow the window from the left by one if the current sum is too large. (though I use subtraction rather than addition to compute this) This should be O(n) because, once we get to the end of the list we are done moving right and simply waiting for the tail pointer to get to the end (provided we are bigger than the sum when the index gets to the end)

``````#!/usr/bin/ruby
a = [1,1,1,2,2,1,1,1,1,1,2]

def longestSum(a,s)
start = 0
sum = s
length = 0
max = 0
i = 0
while (i >= start) &&  (start < a.length) do
puts "loop start considering #{a[start..i]}"
sum -= a[i]
length += 1
if (sum > 0)
puts "sum = #{sum} continuing"
else
puts "sum = #{sum} backing out length = #{length}"
max = length if (sum == 0) && (length > max)
sum += a[start]
puts "adding back #{a[start]} to sum now equal to #{sum}"
start += 1
length -= 1
puts "new max:#{max}"
end
i+=1 if (i < (a.length - 1))
end
return max
end

puts longestSum(a,5)``````

Add a Comment
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.

Learn More

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

Learn More

### Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

### Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More