Google Interview Question
Country: India
Interview Type: Phone Interview
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.
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.
use two iterators:pstart and pend,indicate the subarray.
initial : pstart=pend=0;
if(sum<goal) pend++
else if(sum>goal) pstart++
else return
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.
@Above,
I think this question is all about positive integers and did not mention about negative integer scenario.
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.
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.
@Above , we don't need to actually remove the element from array. Just keep track of index on both sides, front and back.
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?
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.
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.
@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
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++;
}
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;
}
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));
}
}
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;
}
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();
#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);
}
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.
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.
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;
}
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;
}
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);
}
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++;
}
}
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++;
}
}
}
}
// 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;
}
/* 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;
}
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;
}
@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;
}
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;
}
#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;
}
#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;
}
#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;
}
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);
}
}
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.
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)
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();
}
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++];
}
}
It can be done O(n).
- Anonymous May 02, 2012My 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.