Amazon Interview Question Software Engineer / Developers
Country: India
Interview Type: Phone Interview
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);
}
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.
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
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");
}
}
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
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;
}
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();
}
#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;
}
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] + " ");
}
}
}
'''
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)
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 + "]");
}
}
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 + "]");
}
}
/*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;
}
/*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;
}
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.
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 .
@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?
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]);
}
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);
}
}
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)
- Vir Pratap Uttam May 05, 2015private 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; }