Google Interview Question


Country: India
Interview Type: Phone Interview




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

It can be done O(n).
My logic is as follows:- Keep adding elements to a running sum till it is either equal to given number or is greater than the given number. As soon as we add a number and the running number is greater than the given number we subtract the elements from the beginning of the array till it is again less than the given number. After the current sum is less than the given number we add the next element and check and continue the same process.

- Anonymous May 02, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

just that the process of subtracting numbers from beginning of array might be taking overhead, (might be depending on the array size), and thus this might run into o(n2). I am not sure.

- prakhargoyal May 02, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Hi der it will run in O(n). Take some time and check with few examples. It is a DP. If it does not convince you i will paste my code too.

- Anonymous May 03, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Great this logic would work.

- GuruK May 03, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

use two iterators:pstart and pend,indicate the subarray.
initial : pstart=pend=0;
if(sum<goal) pend++
else if(sum>goal) pstart++
else return

- kurskk141 May 03, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@Anonymous: could you please clarify on the DP part?. [Dynamic Programming] ?

- Pavan May 03, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Good logic.

- Pavan Dittakavi May 03, 2012 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

This won't work.

[-1 -1 1] look for sum 0.
running sum is -1, -2, -1 and you won't find it.

If you are using comparisons and +/-, then you cannot do better than Omega(n log n). We can reduce element distinctness to this problem.

- Anonymous May 03, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@Above,
I think this question is all about positive integers and did not mention about negative integer scenario.

- Pavan Dittakavi May 03, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Not only need to subtract the head element but also need to subtract the newly added element that cause it larger than the given number.

- Daisy May 03, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Not only need to subtract the head element but also need to subtract the newly added element that cause it larger than the given number.

- Daisy May 03, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

how is this O(n)? each subtracting from head process is also n. It is still n^2.

- Anonymous May 17, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@Above , we don't need to actually remove the element from array. Just keep track of index on both sides, front and back.

- cancer16789 May 19, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

how is it O(n)
consider case with
1,1,1,1,1,1,1,1,1,10 and find x = 11
can someone prove it will be O(n) now?

- maddy June 12, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

I'm thinking the similar way. Just when the sum is larger than the given number, I check if the last added number itself is larger than given number. If it is, put the sum=0, and track the array[i+1] as the new front of the sub_array; if not, subtract the current front from the sub_array, and check if the sum of rest sub_array is still larger than the given number.

- sophia June 14, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@maddy I think that will be O(2*n) and not O(square(n)).

- Water July 10, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

explaining the O(n) time complexity:
the suggested alg. assumes 2 pointers: head, tail. head pointer can move at most n steps as well as the tail pointer. overall 2n moves.

- bilal July 23, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@Daisy we dont need to subtract newly added number as
if S(i, j)<x and we added j+1 th element to make it,
S(i, j+1)>x, we just need to check by removing ith element,
ie check S(i+1, j+1),
we dont need to check S(i+1,j) as always S(i+1,j)<X as S(i,j)<X and ith element is positive!

P.S. S(i,j) is sum of ith to jth elements and X is the given number

- sLeviN August 09, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

i=0;j=0;sum=0;
for(;i<length;)
{
sum +=Array[j];

if (sum > value)
{
sum -= Array[i];
i++;
}
if (sum == value)
{
return(subarary(i,j));
}
if(sum<value)
j++;
}

- I'mpossible September 22, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

above code is tested for:
1,1,1,1,1,1,1,1,1,10 and find x = 11
3,7,4,5,6,9 and find 16

- I'mpossible September 22, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

C# implementation of one-pass algo:

static int[] Search(int[] arr, int k)
{
    if (k < 0) return null;
    int i = 0, j = 0, sum = 0;
    while (j < arr.Length)
    {
        while (j < arr.Length && sum < k) sum += arr[j++];
        while (i < arr.Length && sum > k) sum -= arr[i++];
        if (sum == k) return arr.Skip(i).Take(j - i).ToArray();
    }
    return null;
}

- Flux November 11, 2013 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

Here is my answer:

basicalgos.blogspot.com/2012/05/46-find-sub-array-of-given-sum.html

- Andy May 03, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

I hope this works. Also takes care of negative ints.

public class sumOfContiguosArray {
	public static int sumToX(int[] a, int target){
		int cursum=0,temp=0;
		for(int i=0;i<a.length;i++){
			temp=Math.max(0, temp+a[i]);
			cursum=Math.max(cursum, temp);
			if(cursum==target)
				return i;
			else if(cursum>target){
				cursum=a[i];temp=a[i];
			}
		}
		return -1;
	}
	public static void main(String[] args) {
		System.out.println(sumToX(new int[]{1,2,3,-1,1,2}, 5));
	}
}

- Shobhit May 08, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Please check it again.
Your code won't work for 2, 1, 8, 2, 2, 4
And target is 12

- Psycho August 06, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

what if the required sum is negative i.e. -1??
{-1,-1,1}

- arma1303 April 07, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

int[] subArray(int[] inputArray, int  sum){
		for(int counter = 0; counter<inputArray.length; counter++){
		    int tempSum = 0;
		    for(int finalIndex=counter; finalIndex<inputArray.length;finalIndex++){
		    	tempSum+=inputArray[finalIndex];
			    if(tempSum==sum){
			      return Arrays.copyOfRange(inputArray, counter, finalIndex+1);  
			    }
		    }
		}
		return null;
	}

- abhinav May 02, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

are the elements expected to be in sorted order???

- codinglearner May 02, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Can be done in linear time. given below is the python where variable SUM contains the total, feel free to change and try. In the end it prints the sum and continous subarray indexes. The idea is to keep adding and checking the total..more like a moving window...if current total exceeds the sum, shrink the window by moving the start of the window and deduct the value from the total. Until the window end goes beyond the array end.

import sys;

# Given an array having positive integers, find a continous subarray which adds to a given number.
def main():
        arr = [2,4,1,3,7,5,6];
        SUM = 15;

        i=0;
        wstart=0;
        wend=0;
        total = 0;

        while True:
                if total == SUM: break;

                if wend == len(arr): break;
                if total > SUM:
                        total -= arr[wstart];
                        wstart +=1;
                        continue;
                           
                total += arr[wend];
                wend +=1;

        
        print "Expected Total = ",SUM;
        print arr;
        if total!=SUM:
                print "None Found";
        else:
                print wstart,wend;
main();

- Tintin May 02, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include<stdio.h>
void findsubarray(int *a,int n,int sum)
{int start=0,end=0;
int tempsum=0;
 
if(sum<a[0])
{
printf("not possible");
return;
}
for(int i=0;i<n;i++)
{
        if(tempsum==sum)
        break;
        if(tempsum<sum && a[i]<sum)
        {
                tempsum+=a[i];
                end=i;
        }
        if(tempsum>sum)
        {
                tempsum-=a[start];
                start++;
        }
}
if(tempsum==sum)
{
for(int i=start;i<=end;i++)
printf("%d\t",a[i]);
}
else
printf("not possible");
 
}
 
int main()
{
int a[]={1,3,5,6,8,9};
int n=6;
int sum=14;
findsubarray(a,n,sum);
}

- codinglearner May 02, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Won't work without the assumptions that you have made.

1. Array contains only positive numbers.
2. The required sum cannot be negative.

For e.g. try finding sum = -4 in your example array.

you will get start = 2 and end = 0 as a result.

- NewCoderInTown May 02, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

My algorithm to solve this will be.

1. Sort the array O(n*lgn)
2. Update the array to have cumulative sum till that index O(n).
- index n, Sum i =0 to n
- if any of these sums match the required sum, break.
3. Now have two indexes at start and end (0 and str.Length-1).
- tempSum = value[end] - value[start]
4. Increment start if tempSum is less than sum, else decrement end.
5. Do the above till sum found or end > start.

- NewCoderInTown May 02, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

What was I thinking?

Please disregard my algorithm.

- NewCoderInTown May 02, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

What was I thinking?

Please disregard my algorithm.

- NewCoderInTown May 02, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@ newCoserInTown My algo works has O(n) and the question itself specifies the that the nos in the array are positive...that wasnt an assumption .However thnx for reminding me of the testcase i missed i.e sum being negative.

- codinglearner May 03, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include <stdio.h>

int main()
{
int a[6] = {2,3,1,6,4,9};
int p=0 , i=0, j, x=0;
int input=13;

while (i != 6)
{
x = a[i] + x;

while (x > input)
{
x = x - a[p];
p = p+1;
}
if(x == input)
{
for(j=p; j<=i; j++)
{
printf("\n%d",a[j]);
}
break;
}
i++;

}
return 0;
}

- Spammer May 03, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

It' my solution:

#include <iostream>

using namespace std;

int main() {
    int final_sum;
    cin >> final_sum;
    int array[10] = {11, 1, 3, 9, 10, 2, 5, 7, 4, 8};
    int i = 0, j = 0, sum = array[0];
    while (j < 10) {
        while (sum < final_sum) {
            ++j;
            if (j >= 10) break;
            sum += array[j];
        }
        if (j >= 10) break;
        if (sum == final_sum) {
            for (int k = i; k <= j; ++k)
                cout << array[k] << " ";
            cout << endl;
            sum -= array[i];
            ++i;
        } else {
            sum -= array[i];
            ++i;
            sum -= array[j];
            --j;
        }
    }
    return 0;
}

- milo May 03, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

It' my solution:

#include <iostream>

using namespace std;

int main() {
    int final_sum;
    cin >> final_sum;
    int array[10] = {11, 1, 3, 9, 10, 2, 5, 7, 4, 8};
    int i = 0, j = 0, sum = array[0];
    while (j < 10) {
        while (sum < final_sum) {
            ++j;
            if (j >= 10) break;
            sum += array[j];
        }
        if (j >= 10) break;
        if (sum == final_sum) {
            for (int k = i; k <= j; ++k)
                cout << array[k] << " ";
            cout << endl;
            sum -= array[i];
            ++i;
        } else {
            sum -= array[i];
            ++i;
            sum -= array[j];
            --j;
        }
    }
    return 0;
}

- milo May 03, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static int[] getArrayRange(int[] array, int goal)
    {
	int start = 0;
	int end = 0;
	int sum = 0;
	
	while(start <= end)
	{
	    if (sum == goal)
	    {
		break;
	    }
	    if (sum < goal)
	    {
		sum += array[end];
		end++;
	    }
	    else
	    {
		sum -= array[start];
		start++;
	    }
	}

	return Arrays.copyOfRange(array, start, end);
    }

- Anonymous May 03, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

this will not work:
arr = 7 , 1,2,0

1.) goal = 0
2.) goal = 2

etc...

- GKalchev May 04, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Maintaining running sum is fine, but moving window solution proposed by other might not work.

Use hashtable.

If Array is a[0], a[1], ... a[n] and given number is S.

Running sum S[i] = a[0] + a[1] + ... + a[i].
S[-1] = 0.

Insert S[i] into hash table.

When inserting S[j], check if S[j] - S is already there.

Something like this:

void hasSubarraySum(int [] inpArray, int S) {
    HashMap<int, int> prefixSums = new HashMap<int, int>();
    prefixSums[0] = -1;
    int prefixSum = 0;
    int curIndex = 0;
    foreach (int num in inpArray){
        prefixSum += num;
        if (prefixSums.contains(prefixSum - S)){
            // Found subarray
        } else {
            prefixSums[prefixSum] = curIndex;
        }
        curIndex++;
    }
}

- Anonymous May 03, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

This is efficient algorithm. In terms of time complexity

- Spammer May 05, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

public class subset {

public static void main(String str[]){
int a[] = {2,3,4,7,1,1,11};

int sumRequired = 9;

int initialIndex=0;
int i=0;
int add=0;
while (i<a.length){

for(;add!=sumRequired && i<a.length;){
if(add > sumRequired){
add-=a[initialIndex];
initialIndex++;
}else {
add+=a[i];i++;
}
}

if(add==sumRequired){
System.out.println("initial Index ="+initialIndex + "Final index ="+ (i-1));
add-=a[initialIndex];
initialIndex++;
}
}


}

}

- Anonymous May 03, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I even don't understand this question.

Given an array having positive integers, find a continuos subarray which adds to a given number.

what means "which adds to a given number"?

- Tony Stark May 04, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

// O(n) time O(1) space
//move a window as soon as it is equal stop.
// If it is greater move left pointer ++
// if it is lower move right pointer ++ 

public int[] findSubArray(int[] arr, int value) {
 int[] result = null;

 if (arr != null && value >= 0) {
  int i = 0;
  int j = 0;
  int sum = 0;
  boolean hasResult = false;
  boolean jChanged = true;
  boolean iChanged = false;

  while (j < arr.length) {
   if (jChanged) {
    sum += arr[j];
    jChanged = false;
   }

   if (iChanged) {
    sum -= arr[i];
    iChanged = false;
   }

   if (sum == value) {
    hasResult = true;
    break;
   } else if ( sum < value) {
    j++;
    jChanged = true;;
   } else {
    if(i == j) {
     j++;
     jChanged = true;
    }
    i++;
    iChanged = true;
   }
  }
 
  if (hasResult)
   result = Arrays.copyOfRange(arr, i, j + 1);
 }
 return result;
}

- GKalchev May 04, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

/* just to practice the running sum alg*/
boolean find_seq_sum(int a[], int length, int target_sum, int *start, int *end) {
  int i,j;
  int sum=a[0];

  *start=*end=-1;
  for(i=0, j=0; i<length && j<length && i<=j;) {
     if(sum==target_sum) { *start=i; *end=j; return true;}
     else if(sum>target_sum) {sum -= a[i++];}
     else if(++j<length) sum += a[j];
  }
  return false;
}

- jzhu May 17, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I get internal error 500 when I submit my code!

- hmonfared May 23, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public int[] continuousArraySummingTo(int ar[], int num) {
		if (ar == null)
			return null;
		int start,end;
		start=0;end=1;
		
		int runningSum = ar[start];
		
		while((end+1)<=ar.length){
			while(runningSum < num && (end+1)<=ar.length){
				  
				  runningSum+=ar[end];
				  end++;
			}
			if(runningSum == num)
			{
			  int len = 0;
			  int startIndexOfResult = start;
			  int [] result = new int[end-start+1];
			  
			  while(len<(end-start+1)){
				  System.out.println("StartIndexOfResult:"+startIndexOfResult+"  End:"+end+"  len:"+len);
				  result[len] = ar[startIndexOfResult];
				  len++;
				  startIndexOfResult++;
				  
			  }
			  return result;
			  
			}
			else{
				while(runningSum > num && start<=end){
					runningSum-=ar[start];
					start++;
				}
			}		
		}//end of outermost while
		return null;
	}

- Learner May 27, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

@arr = (33,22,1,32,122);
my $FAIL = 1;
my $PASS = 0;

$num = $ARGV[0];

print "Argv = $num..\n";
if (!$num)
{
   usage();
   exit($FAIL);
}

my $index = 0;
my $ini;
foreach (@arr)
{
   $ini += $_;
}

my $found;
if ($num >$ini) { print "Invalid input.. \n"; exit($FAIL); }
for my $index(0..scalar(@arr))
{
   my $sum = $arr[$index];
   print "Sum = $sum..\n";
   my @window = $arr[$index];
   my $lindex = $index;
   print "plus  $arr[$index+1] ..\n";
   while ($sum < $num)
   {
      print "less.\n";

      if ($lindex == scalar(@arr)) { last;}
      $sum += $arr[$lindex+1];
      print "$sum..\n";
      push(@window,$arr[$lindex+1]);
      print @window,"\n";
      $lindex++;
      next;
   }

- Anand Sridharan May 31, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Half pasted code earlier. Ignore the same. Full code in perl below.

@arr = (33,22,1,32,122);
my $FAIL = 1;
my $PASS = 0;

$num = $ARGV[0];

print "Argv = $num..\n";
if (!$num)
{
   usage();
   exit($FAIL);
}

my $index = 0;
my $ini;
foreach (@arr)
{
   $ini += $_;
}

my $found;
if ($num >$ini) { print "Invalid input.. \n"; exit($FAIL); }
for my $index(0..scalar(@arr))
{
   my $sum = $arr[$index];
   print "Sum = $sum..\n";
   my @window = $arr[$index];
   my $lindex = $index;
   print "plus  $arr[$index+1] ..\n";
   while ($sum < $num)
   {
      print "less.\n";

      if ($lindex == scalar(@arr)) { last;}
      $sum += $arr[$lindex+1];
      print "$sum..\n";
      push(@window,$arr[$lindex+1]);
      print @window,"\n";
      $lindex++;
      next;
   } 

   if ($sum == $num) { $found = 1;print "Found1..\n";print join(",",@window); last;}

   while ($sum > $num)
   {
      print "More..\n";
      my $val = shift (@window);
      print @window,"\n";
      $sum = $sum - $val;
         
   }

   if ($sum == $num) { $found = 1;print "Found..\n"; print join(",",@window);last;}

}

unless ($found) { print "Not found..\n"; exit($FAIL);}

###############################################
sub usage
{
   $str = <<EOF
Usage:
subarraysum.pl <input>
EOF
   ;
   print $str;
}

- Anand Sridharan May 31, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include <stdio.h>

int main (int argc, const char * argv[]) {
	int a[] = {1,2,3,5,7,2,3,1,8};
	int sum = 12;
	int len=sizeof(a)/sizeof(int);
	int currentSum = 0;
	int startingIndex = 0;
	int i,j,k;
	for (i = 0; i < len; i++) {
		if(currentSum == 0){
			startingIndex = i;
		}
		currentSum += a[i];
		if(currentSum == sum){
			for(j=startingIndex;j<=i;j++){
				printf("%i ",a[j]);
			}
			printf("\n");
			currentSum=0;
			i--;
			continue;
		}else if (currentSum > sum) {
			k = startingIndex;
			while (currentSum > sum) {
				currentSum -= a[k];
				k++;
			}
			startingIndex = k;
			if(currentSum == sum){
				for(j=startingIndex;j<=i;j++){
					printf("%i ",a[j]);
				}
				printf("\n");
				currentSum=0;
				i--;
				continue;
			}
		}
		
	}
    return 0;
}

- Anonymous May 31, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include <stdio.h>

int main (int argc, const char * argv[]) {
	int a[] = {1,2,3,5,7,2,3,1,8};
	int sum = 12;
	int len=sizeof(a)/sizeof(int);
	int currentSum = 0;
	int startingIndex = 0;
	int i,j,k;
	for (i = 0; i < len; i++) {
		if(currentSum == 0){
			startingIndex = i;
		}
		currentSum += a[i];
		if (currentSum > sum) {
			k = startingIndex;
			while (currentSum > sum) {
				currentSum -= a[k];
				k++;
			}
			startingIndex = k;
		}
		if(currentSum == sum){
			for(j=startingIndex;j<=i;j++){
				printf("%i ",a[j]);
			}
			printf("\n");
			currentSum=0;
			i--;
			continue;
		}
	}
    return 0;
}

- Anonymous May 31, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include <stdio.h>

int main (int argc, const char * argv[]) {
	int a[] = {13,2,3,5,7,2,3,7,8,4};
	int sum = 12;
	int len=sizeof(a)/sizeof(int);
	int currentSum = 0;
	int startingIndex = 0;
	int i,j,k;
	for (i = 0; i < len; i++) {
		if(currentSum == 0){
			startingIndex = i;
		}
		currentSum += a[i];
		if (currentSum > sum) {
			k = startingIndex;
			while (currentSum > sum) {
				currentSum -= a[k];
				k++;
			}
			startingIndex = k;
		}
		if(currentSum == sum){
			for(j=startingIndex;j<=i;j++){
				printf("%i ",a[j]);
			}
			printf("\n");
			currentSum=0;
			i = startingIndex;
			continue;
		}
	}
    return 0;
}

- Anonymous May 31, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static void findSum(int x) {
		int sum = 0;
		int top = 0;

		for (int i = 0; i < array.length; i++) {
			sum = sum + array[i];
			sub.add(array[i]);
			if (sum > x) {
				while (sum > x) {
					sum = sum - ((int) sub.get(top));
					sub.remove(top);
				}
			} if(sum ==x){

				return;
			}
		}

}

- srilesnar June 12, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Is it asking for the longest or just any one of the subarray?
For example:
Given A[] = {2,4,1,3,7,5,6} and sum =15,
should the program return 4 ,1,3,7 or should it return 3,7,5? or both?

Thanks!

- songwanguvm07 June 13, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

package interview.tree;

public class Q13507662
{
    public static void find(int[] a, int k)
    {
        int start = 0;
        int sum = 0;
        for (int i = 0; i < a.length; i++)
        {
            sum +=a[i];
            if (sum > k)
            {
                while(sum > k && start <= i)
                {
                    sum -= a[start++];    
                }
            }
            
            if(sum == k)
            {
                System.out.println(String.format("a[%s, %s] sums up to %s", start, i, k));
                return;
            }
        }
    }

    public static void main(String[] args)
    {
        int[] a = new int[]{1, 2, 3, 4, 5, 6};
        
        find(a, 5);
    }
}

- Anonymous June 17, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Linear algorithm:

maintain a running sum from the first element until the running sum is either equal to the goal (return) or passes... if it passes keep subtracting from it the earliest element to be included until it is either equal (return) or too small... repeat until it either returned due to the 2 return conditions or both i and j ran out at which case return null.

- rduck July 26, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Solution in Python. Worse case still O(n^2 / 2), but average case is O(n^2 / 4)

def findsubseqsum(arr, thesum):
	arr.insert(0, 0)
	allsums = [[0 for x in range(len(arr) + 1)] for y in range(len(arr) + 1)]
	
	for s in range(1, len(arr)):
		allsums[s][s] = arr[s]
		if allsums[s][s] == thesum:
			print "start = %d, finish = %d" % (s, s)
				
		for f in range(s + 1, len(arr)):
			allsums[s][f] = allsums[s][f-1] + arr[f]
			
			if allsums[s][f] == thesum:
				print "start = %d, finish = %d" % (s, f)
				
			if allsums[s][f] > thesum:
				break
	
print findsubseqsum([1, 2, 3, 4, 5, 6, 7, 8, 9], 15)

- ep August 02, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Actually don't really need the allsums array. Just use a sum variable to keep track of the running sum for each i.

- ep August 02, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

public void findSubArray(int[] array, int result){
    	int start = 0;
    	int sum = 0;
    	if(array.length == 0){
    		System.out.println("Array is invalid format");
    		return;
    	}else if(array.length == 1){
    		if(array[0] == result){
    			System.out.println("Match found: "+array[0]);
    			return;
    		}
    	}else{
    		sum = array[0];
    		for(int i=1; i < array.length; i++){
    			sum += array[i];
    			if(sum == result){
    				System.out.println("found match "+printMatch(array,start,i));
    				return;
    			}else if(sum > result){
    				while( sum > result && start < i){
    					sum = sum - array[start++];
    					if( sum == result){
    						System.out.println("decrease found match "+printMatch(array,start,i));
    						return;
    					}
    				}
    			}
    		}

    	}
    	System.out.println("No match found");
    }

    public String printMatch(int[] array, int start, int end){
    	StringBuffer buff = new StringBuffer(String.valueOf(array[start++]));
    	while(start<=end){
    		buff.append(", "+array[start++]);
    	}
    	return buff.toString();
    }

- Anonymous August 14, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

int low = 0, high = 0, sum = in[0];
while(high < in.length && sum != val){

if(sum > val && low < high ) {

sum-= in[low];
low +=1;
}

if((sum < val ) || ( low == high && sum > val)) {
high +=1;
sum+= in[high];
}

}
System.out.println("Low: " + low + "High: " + high);

- Anonymous August 18, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

S = 0;
E = 0;
RS = ARR[S];
while(E<ARR.length) {
	if(RS == RESULT) {
		break;
	} else if(RS>RESULT) {
		RS = RS - ARR[S];
		S++;
	} else {
		E++;
		RS = RS + ARR[E];
	}
}
if(E!=ARR.length){
	print elements of ARR[] from S to E.
} else {
	No such subarray exist.
}

- SRB August 19, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static void find(int[] a, int sum) {
		
			int i = 0, run_sum = 0;
			for (int j = 0; j < a.length; j++) {
				run_sum += a[j];
				if (run_sum == sum)
					print(a, i, j);
				else if (run_sum > sum)
					run_sum -= a[i++];
			}
	}

- Anonymous October 29, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

1 4 5 8 7 6, then sum is 15

That means, if I want sum which can only get in the middle part, then this way cannot work!

- It cannot work under some circumstances December 28, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

int ps(0), j(0);
for (int i=0; i < n; i++)
{
        ps += a[i];
        while (ps > k) ps-= a[j++];
        if (ps == k) return true;
}
return false;

- Anonymous August 07, 2013 | Flag Reply


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