Facebook Interview Question for Software Engineers


Interview Type: Phone Interview




Comment hidden because of low score. Click to expand.
12
of 16 vote

public boolean findSum (int [] A ,int T){
		int sum = 0 ;
		int j = 0;
		for (int i = 0 ; i < A.length ; ++i) {
			while (j < A.length &&  sum < T) {
				sum += A[j] ;
				j++;
			}			
			if (sum == T) {
				return true ;
			}
			sum -= A[i] ;
		}
						
		return false ;

}

- Scott February 27, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

public static boolean calc(int[] num, int target) {
int sum;
for (int i = 0; i < num.length; i++) {
sum = num[i];
for (int j = i + 1; j < num.length; j++) {
sum = sum + num[j];
if (sum == target) {
return true;
} else if (sum < target) {
continue;
} else {
break;
}
}
}

return false;
}

- coder March 06, 2015 | Flag
Comment hidden because of low score. Click to expand.
-2
of 2 votes

This is wrong. What about this sequence (6, 3, 4, 10), 20. Going through the loop will pop 6 immediately. while the correct answer should be: (6,4, 10)

- Howard October 17, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@Howard: We're only looking for continuous sequences.
@Chris: Are you sure that

++i

makes sense since you're substracting A[1] from sum after adding A[0] to it on first iteration if A[0] > N ? (check data from first example)

- Phil Pirozhkov November 10, 2015 | Flag
Comment hidden because of low score. Click to expand.
1
of 5 vote

Use Sliding Window to slides along the sequence, watching the sum of numbers inside the window:
If sum less than T: expand the window to the right;
If sum = T: report true, finish;
If sum > T: shrink the window from left.

EDIT:
This algorithm works for positive numbers.
It takes O(N) time, O(1) space, where N is the size of array.

Pseudo code (which is almost code!):

checkSum(){
	wL = 0, wR = 0, sum = A[0]; // fixed by phantomlord, thanks!

	while(wR<N){
		if (sum < T){
			wR++;			//expand to the right
			sum += A[wR];	//update sum
		};

		if (sum==T) return true;
	
		if (sum > T){
			sum -= A[wL];	//update sum
			wL++;			//shrink from left
		};
	};

	return false;
}

EDIT2:
For input of both NEGATIVE and positive numbers: we can store cumulative sum at each position in a hash table and check for the sum of T along the way.

If we see Sum at current position i, and saw Sum-T at some previous position j, then all numbers between j and i will sum up to T.

Remember to check the case Sum-T = Sum. To avoid that case, need to check the hash table before inserting current Sum into it.

Still O(N) time, but O(N) space needed.

Credit to eugene.varovoi!

Pseudo code:

checkSum(){
	Sum = 0;
	HashSet = {};
	
	for i = 0..N-1
		Sum += A[i];
		//if see a value of  (Sum-T) previously, report true, else insert current Sum in:
		if HashSet contains (Sum-T) then return true;
		else HashSet.insert(Sum);			
	};
	
	return false;
}

- ninhnnsoc February 27, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

the array isn't sorted, won't work

- nemo February 27, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

The numbers were stated to be positive, this WILL work

- Anonymous February 27, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

I think this should work even with an unsorted array.

function find_sum(arr, target)                                                                                     
{                                                                                                         
    var sum = 0;                                                                                          
    for (var idx_right =0, idx_left = 0; idx_right < arr.length; ++idx_right)                                                            
    {                                                                                                     
        sum += arr[idx_right];                                                                                    
        while (sum > target)                                                                                   
        {                                                                                                 
            sum -= arr[idx_left];                                                                                
            ++idx_left;                                                                                          
        }                                                                                                 
        if (sum == target)                                                                                     
            return true;                                                                                  
    }                                                                                                     
    return false;                                                                                         
}

- Anonymous February 27, 2015 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

This should work even without a sorted array.

function find_sum(arr, T)
{
    var sum = 0;
    for (var i =0, j = 0; i < arr.length; ++i)
    {
        sum += arr[i];
        while (sum > T)
        {
            sum -= arr[j];
            ++j;
        }
        if (sum == T)
            return true;
    }
    return false;
}

This runs in O(n) time and O(1) space.

- Some guy February 27, 2015 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

The problem statement only allowed for positive numbers, so this approach is correct. If negative numbers were also allowed, here's a different approach that works for all numbers.

Build a cumulative array where the i-th element contains the sum of the first i numbers. Then, scan through the cumulative array, and for each value v, check whether v-T has been previously seen in the cumulative array (to do this efficiently, use a hash table and add the elements of the cumulative array to it as you go).

- eugene.yarovoi February 27, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@phantomlord: fixed first bug! Thanks!

Second bug: each time the window only moves at most 1 position, thus sum is checking at every position.

- ninhnnsoc February 28, 2015 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

@ninhnnsoc, OK, I realised the second comment was invalid after writing and deleted it.
There is one more bug. Feed the input [1, 3, 5, 23, 2], 7.
The sum is 2 at the last index because everything up to that point does not add up to 7. Because the sum is 2, it increments wR which goes over the bounds of the array and when accessing it to accumulate the next sum, the position is N, hence invalid. You'll probably need to return false if wR is == N after incrementing to prevent that.

- phantomlord February 28, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@phantomlord: why don't you give real code and fix the bug for me :)
Thanks!

- ninhnnsoc March 01, 2015 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

while (wR < nums.length) {
			if (sum == target)
				return true;
			else if (sum > target) {
				sum -= nums[wL++];
			} else if (wR<nums.length-1){
				sum += nums[++wR];
			} else {
				wR++;
			}

}

should check if wR out of index when increase it and add it to sum

- zhihongbupt March 03, 2015 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

@ninhnnsoc, here you go :-) Test cases included. Don't get me wrong, your solution is very neat, does the job in one loop. Hence a lot of scrutiny.

public class ContinuousSequenceSum {
    public static boolean sumsTo(int[] a, int T) {
        int wL = 0, wR = 0, sum = a[0];

        while (wR < a.length) {
            if (sum < T) {
                if (wR < a.length-1) ++wR;
                else                 return false;
                sum += a[wR];
            }

            if (sum==T) return true;

            if (sum > T) {
                sum -= a[wL];
                ++wL;
            }
        }
        return false;
    }

    public static void main(String[] args) {
        int[] a1 = {23, 5, 4, 7, 2, 11};
        int   t1 = 20;
        System.out.println(sumsTo(a1, t1)); // true

        int[] a2 = {1, 3, 5, 23, 2};
        int   t2 = 8;
        System.out.println(sumsTo(a2, t2)); // true

        int[] a3 = {1, 3, 5, 23, 2};
        int   t3 = 7;
        System.out.println(sumsTo(a3, t3)); // false

        int[] b1 = {23, 5, 12, 4, 7, 9};
        int   u1 = 20;
        System.out.println(sumsTo(b1, u1)); // true

        int[] b2 = {1, 2, 23, 24, 20, 4, 7, 9};
        int   u2 = 20;
        System.out.println(sumsTo(b2, u2)); // true

        int[] b3 = {25, 23, 24, 20, 4, 7, 9};
        int   u3 = 20;
        System.out.println(sumsTo(b3, u3)); // true

        int[] b4 = {1, 2, 3, 4, 20, 21, 5, 9, 6};
        int   u4 = 20;
        System.out.println(sumsTo(b4, u4)); // true
    }
}

- phantomlord March 05, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@phantomlord: excellent! It works.
Can initiate A[n] = A[n+1] = 0, it also works.

- ninhnnsoc March 06, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

You may be at at max possible valid wR, and then you just increment wR and read at it without checking for validity... so you may end up reading past the end of the array... Try it with array {1,1,1,100} and target sum 5.

- venera.varbanova April 05, 2015 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

Hi, Just wonder if this can handle [1,1,1,1,1,1,1] 20 case.
Correct me if I am wrong. This algorithm will go into infinite loop for this input since there is no boundary check for array.

- hankm2004 July 10, 2015 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

I think for worst case this would be O(N^2), not O(N). This is because if you have
[1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,99], 100, the first time you have to check n numbers, then the second you check n-1 numbers and essentially won't find a result until you hit the last two, which ends up being O(N^2)

- zkaiwen October 12, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

def findSub(self,A,target):
        length = len(A)
        i = 0
        while(i<length-1):
            output = target-A[i]
            if output<0:
                i+=1
            elif output==0:

                return True
                break

            else:
                for j in range(i+1,length):
                    output =output-A[j]
                    if output <0:
                        i+=1
                        break
                    elif output==0:
                        return True
                        break
                    else:
                        output = output
        return False

- liwzhi February 27, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

{
for(int i = 0; i<arr.length(); i++){
if(flag)
startIndex = i;

sum = sum + arr[i];
if(sum < T){
flag = false;
continue;
}
while(sum > T && startIndex <= i){
sum = sum - arr[startIndex];
startIndex++;
}
if(startIndex == i)
flag = true;

if(sum == T)
return true;
}
return false;
}

- Amit February 27, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static bool IsSubsetSum(int T, int[] S)
{
	for(int i = 0; i < S.Length; i++)
	{
		int total = 0;
		for(int j = i; j < S.Length; j++)
		{
			total += S[j];
			if(total == T)
			{
				return true;
			}
		}
		
		return false;
	}
}

- Nelson Perez February 27, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Don't understand why everybody else assumes that the numbers are only positives.
You need to look at the entire array in order to determine if the SUM exist.

- Nelson Perez February 27, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Oh finally saw it. Darn "only positive numbers".

- Nelson Perez February 27, 2015 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

For negatives numbers, O(N) time solution exists!
See EDIT2 of my post and comment of eugene.varovoi

- ninhnnsoc February 28, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Thanks for the input.
Yep I just realized when I did it in the white board but I'll post it as a new entry.

- Nelson Perez March 02, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Actually I saw that you use a HashSet I do not quite understood how it works.

I tried with a couple of samples and indeed does work but I'm still sort not sure how it does work.

- Nelson Perez March 02, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

bool doesContSeqExists(int &vTargSum, vector<int> &vInput)
{
int vSum = 0;
int totalIterations = 0;
totalIterations = vInput.size();
int skipIterations=0;

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

skipIterations = 0;
vSum = 0;
for(auto e:vInput)
{
if(skipIterations<i)
{
skipIterations++;
continue;
}

if(e == vTargSum)
{
return true;
}
else
{
vSum += e;
if(vSum>vTargSum)
{
vSum = 0;
continue;
}
else if(vSum == vTargSum)
{
return true;
}
}
}
}


return false;

}

- kapilsatija February 27, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Will your solution work dor this sequence and sum . 18 1 5 14 28 40. And target sum 20

- Anonymous February 27, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

bool hasContSeq(std::vector<int>& vec, int num)
{
	int sum = 0;

	for (int i = vec.size() - 1; i >= 0; --i)
	{
		if (sum == num)
		{
			return true;
		}
		else if (sum > num)
		{
			sum = vec[i];
		}
		else
		{
			sum += vec[i];
			if (sum > num)
			{
				sum = vec[i];
			}
		}
	}
	return false;
}

- Pasha February 27, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public boolean isSequence(int[] a, int val){
int start=0;
int sum=0;
int len = a.length;
for(int i=0;i++;i<len){
sum+=a[i];
if(sum == val){
return true;
}
else if(sum < val){
continue;
}else{
while (sum > val && start < len){
sum-=a[start];
start++;
}
if(sum == val){
return true;
}
}
}
return false;
}

- satty February 27, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Python, O(n) time and O(1) extra space:

def hasSum(A,T):
	if len(A) == 1:
		return A[0] == T
	elif len(A) == 0:
		return False
	left = 0
	right = 1 # exclusive
	total = A[0]
	while True:
		if total < T:
			right += 1
			if right == len(A):
				break
			total += A[right]
		elif total > T:
			left += 1
			total -= A[left]
		else:
			return True
	return False

- Anonymous February 27, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Python code

def sumT(A, T):
    front = 0
    rear  = 0

    while front < len(A):

        T = T - A[front]

        # case 1
        if T == 0:
            return True

        # case 2
        elif T < 0:
            
            # add rear index until positive
            while T < 0:
                T = T + A[rear]
                if T == 0:
                    return True
                rear += 1
                
            # Now that T is just positive again, step front pointer forward
            front += 1
                
        # case 3
        else: # T > 0
            front += 1

    return False

- Jim February 28, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Python Code
O(n), in place.

def sumT(A, T):
    front = 0
    rear  = 0

    while front < len(A):

        T = T - A[front]

        # case 1
        if T == 0:
            return True

        # case 2
        elif T < 0:
            
            # add rear index until positive
            while T < 0:
                T = T + A[rear]
                if T == 0:
                    return True
                rear += 1
                
            # Now that T is just positive again, step front pointer forward
            front += 1
                
        # case 3
        else: # T > 0
            front += 1

    return False

- Jimmy February 28, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

O(N) solution

public static boolean contSeq(int [] A, int T) {
		int start = -1, end = -1, tempSum = 0;
		int len = A.length;
		for (int i=0; i<len; i++) {
			tempSum += A[i];
			start = start==-1?i:start;
			end = i;
			
			if (tempSum==T) {
				System.out.println("Starting index: " + start + " Ending index: " + end);
				return true;
			}
			else if (tempSum>T){
				while (tempSum>T && start<=end) {
					tempSum -= A[start++];
					if (tempSum==T) {
						System.out.println("Starting index: " + start + " Ending index: " + end);
						return true;
					}
				}
			}
		}
		return false;
	}

- Sakshi February 28, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public boolean contSeq(int [] A, int T) {
		int start = -1, end = -1, tempSum = 0;
		int len = A.length;
		for (int i=0; i<len; i++) {
			tempSum += A[i];
			start = start==-1?i:start;
			end = i;
			
			if (tempSum==T) {
				System.out.println("Starting index: " + start + " Ending index: " + end);
				return true;
			}
			else if (tempSum>T){
				while (tempSum>T && start<=end) {
					tempSum -= A[start++];
					if (tempSum==T) {
						System.out.println("Starting index: " + start + " Ending index: " + end);
						return true;
					}
				}
			}
		}
		return false;
	}

- Sakshi February 28, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

private static boolean hasContSeq(int[] a, int T) {
		int sum = 0;
		int k = 0;
		for (int j = 0; j < a.length; j++) {
			if(a[j] > T){
				k++;
				sum=0;
				continue;
			}
			sum += a[j];
			while(sum > T){
				sum -= a[k];
				k++;
			}
			if(sum == T) return true;
		}
		return false;
	}

- Anonymous February 28, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

private static boolean hasContSeq(int[] a, int T) {
		int sum = 0;
		int k = 0;
		for (int j = 0; j < a.length; j++) {
			if(a[j] > T){
				k++;
				sum=0;
				continue;
			}
			sum += a[j];
			while(sum > T){
				sum -= a[k];
				k++;
			}
			if(sum == T) return true;
		}
		return false;
	}

- whiplash February 28, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public boolean findSequenceSum (int [] a ,int T){
		for(int i=0; i<a.length; i++) {
			int sum = 0;
			int j=i;
			while (sum<T && j < a.length) {
				sum += a[j];
				j++;
			}
			if(sum==T)
				return true;
		}
		
		return false;
	}

public boolean findSequenceSum2(int[] a, int T){
		int sum = 0;
		int start = 0;
		for(int i=0; i<a.length; i++) {
			sum += a[i];
			if(sum>T) {
				while(sum >= T && start <= i) {
					sum -= a[start];
					start++;
					if(sum==T)
						return true;
				}
			} else {
				if(sum==T)
					return true;
			}
		}
		
		return false;
	}

- Julie March 01, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public class Test{
	public boolean isSumSeq(int[] arr, int sum){
		Queue<Integer> seqQ= new PriorityQueue<Integer>();
		int currSum = 0;
		for(int i : arr){
			currSum += i;
			if(currSum == sum)
				return true;
			if(currSum > sum){
				while(currSum > sum){
					int last = seqQ.pop();
					currSum -= last;
				}
			}
			if(currSum == sum)
				return true;
		}
		return false;
	}
}

- tomahawk March 02, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

oh my friends , is it not the version of SUM OF SUBSET problem. whatever solutions you have submitted welldone!
but all the solutions will fail for the larger size of the problem.

- nakul_o+ve March 02, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Linear time taking care of negatives as well. I created a function that might as well return the subset as it knows the range but uses "yield return" so it return on the first part of the loop.

I used yield return if there is no need to find the actual values so it does not iterate through the results just tells if a result will exists on the first yield return.

public HasSubsetThatSums(int[] A, int T)
{

	return (FindSubsetThatSums(A, T) != null);
}

public static IEnumerable<int> FindSubsetThatSums(int[] A, int T)
{
	int head = 0;
	int tail = 0;
	int sum = 0;

	while(tail < A.Length)
	{
		if (sum > T)
		{
			sum -= A[head++];
		}
		else if ( sum < T)
		{
			sum += A[tail++];
		}
		else // if(sum == T) 
		{
			for( int i = head; i < tail; i++)
			{
				yield return A[i];
			}
		}
	}

	return null;
}

- Nelson Perez March 02, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

How does it work for negative numbers?

- ninhnnsoc March 07, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

public boolean isSum(int[] a, int t){
	    
	    for(int i=0; i<=a.length; i++){
	        int j=i;
	        int sum = 0;
	        while(j<a.length){
	        if(a[j]>t) sum = 0;
	        sum += a[j];
	        if(sum>t) j++;
	        if(sum == t) return true;
	        
	        j++;
	        System.out.println("Herej " + j);
	        //System.out.println("Herea " + a.length);
	        }
	        
	        System.out.println("Here " + i);
	    }
	    return false;

}

- Preethi March 03, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

def is_sumed(A, num):
    s = 0
    start_index = 0
    i = 0
    while i < len(A):
        if s == 0:
            start_index = i
        s = s + A[i]
        if s == num:
            return True, start_index
        if s > num:
            s = 0
            i = start_index + 1
        else:
            i = i + 1
    return False

- Natali March 04, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static boolean isPossible(int a[], int index, int sum, int reqSum)
	{
		if(sum > reqSum)
			return false;
		if(index < 0)
			return false;
		if(sum == reqSum)
			return true;
		return isPossible(a, index -1, sum + a[index], reqSum) || isPossible(a, index-1, 0, reqSum);
	}

- anon March 04, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

def continuousArray(seq,num):
    prevCount=0
    nextCount=0
    tSum=0
    if len(seq)>0:
        tSum=seq[prevCount]
    while (prevCount<len(seq) ) and (nextCount<len(seq)):
        if tSum <num:
            nextCount= nextCount+1
            if nextCount < len(seq):
                tSum=tSum+seq[nextCount]
        if tSum >num:
            tSum=tSum-seq[prevCount]
            prevCount=prevCount+1
        if num==tSum:
            return True
    return False

- Rohan March 05, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

def continuousArray(seq,num):
    prevCount=0
    nextCount=0
    tSum=0
    if len(seq)>0:
        tSum=seq[prevCount]
    while (prevCount<len(seq) ) and (nextCount<len(seq)):
        if tSum <num:
            nextCount= nextCount+1
            if nextCount < len(seq):
                tSum=tSum+seq[nextCount]
        if tSum >num:
            tSum=tSum-seq[prevCount]
            prevCount=prevCount+1
        if num==tSum:
            return True
    return False

- Rohan March 05, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

def continuousArray(seq,num):
    prevCount=0
    nextCount=0
    tSum=0
    if len(seq)>0:
        tSum=seq[prevCount]
    while (prevCount<len(seq) ) and (nextCount<len(seq)):
        if tSum <num:
            nextCount= nextCount+1
            if nextCount < len(seq):
                tSum=tSum+seq[nextCount]
        if tSum >num:
            tSum=tSum-seq[prevCount]
            prevCount=prevCount+1
        if num==tSum:
            return True
    return False

- Rohan March 05, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

{{ #include <iostream>
#include <vector>

using namespace std;

bool sumExists(vector<int>& a, int target) {
int n = a.size();
if (n == 0) return false;
if (a[0] == target) return true;
int s = 0;
int sum = a[0];
int i = 1;
while(i < n) {
if (sum + a[i] < target){
sum += a[i];
i++;
} else if (sum + a[i] > target) {
sum -= a[s];
s++;
} else {
return true;
}
}
return false;
}

int main() {
vector<int> a = {23,5,4,7,2,11};
cout << "sum exists : " << sumExists(a,20) << "\n";
cout << "sum exists : " << sumExists(a,28) << "\n";
cout << "sum exists : " << sumExists(a,11) << "\n";
cout << "sum exists : " << sumExists(a,190) << "\n";
cout << "sum exists : " << sumExists(a,23) << "\n";
a = {1,2};
cout << "sum exists : " << sumExists(a,3) << "\n";
} }}

- anonymous March 12, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static boolean consecutiveSum() {
	    	int [] a = { 23,5,4,7,2,11};
		    int T = 11;
		    Queue<Integer>queue=new LinkedList<Integer>();
	        int sum = a[0];
	        queue.add(a[0]);
            
	        for(int i = 0;i<a.length+1;){
	        	if(sum < T){
	        		sum+=a[i];
	        		queue.add(a[i]);
	        		i++;
	        	}
	        	if(sum==T)
	        	{
	        		System.out.println(queue.toString());
	        		return true;
	        		
	        	}
	        	if(sum >T){
	        		sum-=queue.poll();
	        	}
	        	
	        }
	        
	      return false;  
}

- RA March 21, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Another Java version using a loop:

private static boolean sumLoop(int[] arr, int target) {
	for (int sum = 0, i = 0, j = 0;;) {
		if (sum == target) {
			return true;
		}

		if (sum < target && i < arr.length) {
			sum += arr[i++];
		} else if (sum > target && j < arr.length) {
			sum -= arr[j++];
		} else {
			return false;
		}
	}
}

- dph March 28, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Here is my solution in PHP:

function sums($sequence, $sum)
{
    $sequence_length = count ($sequence);
    foreach ($sequence as $key => $value) {
        $count = 0;
        for ($i = $key; $i < $sequence_length; ++$i) {
            $count += $sequence[$i];
            if ($count == $sum)
                return true;
            elseif ($count > $sum)
                break;
        }
    }
    return false;
}

To call and test the above function:

$input = array (
    array (array (23, 5, 4, 7, 2, 11), 20),
    array (array (1, 3, 5, 23, 2), 8),
    array (array (1, 3, 5, 23, 2), 7)
);

foreach ($input as &$row)
    echo implode(',', $row[0]) . " ... {$row[1]} = " . (sums ($row[0], $row[1]) ? 'true' : 'false') . "\n";

This outputs:

23,5,4,7,2,11 ... 20 = true
1,3,5,23,2 ... 8 = true
1,3,5,23,2 ... 7 = false

- JosephB April 04, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Folks ... my solution works irrespective of whether you have positive or negative number.

public static void main(String [] args) {

        int a[] = new int[] {1,-3,5,23,28,2,3,7};
        int b= 8,i=0;

        int Sum=0 ;

        while(Sum !=b  && (i!=a.length) ){

            if (a[i] < b) {
                Sum=Sum+a[i];
            }
            else {
                Sum=0;
            }
            i++;
        }
        if (Sum==b) {
            System.out.println(" we have found a match");
        }
        else {
            System.out.println(" we have not  found a match");
        }
-- INSERT --

- rsingh2 April 05, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

below is my solution which works for both positive and negative number .rather adding to achieve the SUM ,my approach is to subtract and achieve 0, I have outer while loop on the list of array which will be incremented when we see negative number,value greater that SUM expected or the SUM computed greater than SUM expected.

class consArray {



public static void main(String []args) {

  int [] a1 = {1,3,5,7,2};
  int T =8;
  int sum=T;
  int i=0,j=0;
  boolean cons=false;
    while(i!=a1.length){
    for ( j=i;j< a1.length;j++) {
     
       if(sum==0){
        cons=true;
       break;
       }
       else {
              if((a1[j]> T) || (sum<0)||(a1[j]<0)){
                break;
              }
             else {
                    sum-=a1[j];
             }
       }
  }
   if(sum==0){
    cons=true;
   break;
   }
   sum=T;
   i++;
 }
   if(cons)
    System.out.println("We have consecutive sequence");
   else
    System.out.println("we dont have consecutive sequence");

}
}

- rahul.singh4899 April 26, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

test

- dsfsdfsdf June 08, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Here is C++ version of solution with running time O(N), where N is the length of input array

#include <iostream>

using namespace std;

bool find_sum_seq(int* input, int target, int len)
{
  int sum = 0, start = 0;
  for (int i = 0; i <len; i++)
  {
    sum+= input[i];
    if (sum == target)
      break;
    else if (sum > target)
    {
      while(start < len && start <= i && sum > target)
      {
        sum -= input[start++];
      }
      if (sum == target)
        break;
    }
  }
  return sum == target;
}

- hankm2004 July 10, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

boolean hasContSum(int[] in, int t) {
	int lastStart, sum  = 0;
	for (int i = 0; i < in.length; ) {
		sum += in[i];
		if (sum == t) {
			return true;
		} else if (sum > t) {
			i = ++lastStart;
		} else {
			i++;
		}
	}
	
	return false;
}

- Daniel August 10, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

A simple sliding window will do the trick

static int[] vals = {23, 5, 4, 7, 2, 11};
	static int target =  18;
	static void findConsecutiveSum()
	{
		int i = 0; int j =1;
		int l = vals.length;
		int targ = vals[0];
		while(i < l && j < l)
		{
			if(targ == target){
				System.out.println("from index "+i+"  to "+(j-1));
				return;
			}
			
			if(targ < target)
			{
				targ = targ+vals[j];
				j++;
			}
			
			if(targ > target)
			{
				targ = targ - vals[i];
				i++;
			}
		}
	}

- CodeKnight November 10, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include<iostream>

using namespace std;

		 void ContinuousSequence(int *sequence, int length, int sum)
		 {
			 bool flag = false;

			 if (!sequence || length < 0)
				 return;

			 int curSum = sequence[0], start = 0, end, i;

			 for (i = 1; i <= length; i++)
			 {
				 while (curSum  > sum && start < i - 1)
				 {
					 curSum -= sequence[start];
					 start++;
				 }
				 if (curSum == sum)
				 {
					 flag = true;
					 end = i - 1;
				 }
				 if (i< length)
					 curSum += sequence[i];
			 }

			 if (flag)
			 {
				 cout << "\nThere is a Continuous Sequence to targeted Sum" << endl;

				 for (int i = start; i <= end; i++)
					 cout << sequence[i] << endl;				 
			 }

			 else
				 cout << "\nThere is no Continuous Sequence to targeted Sum" << endl;

			cout << endl;
		 }


		 int main()
		 {
			int sequence[] = { 23, 5, 4, 7, 2, 11 };
			int length = sizeof(sequence) / sizeof(sequence[0]);
			ContinuousSequence(sequence, length, 20);

}

- Basu March 16, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

# Here is my python solution
def is_continous_sum(A,T):
s = 0
n = len(A)
curr_sum = 0
for e in range(n):
curr_sum += A[e]
while curr_sum > T:
curr_sum -= A[s]
s+=1
if curr_sum == T:
return 1
return 0

- Gili.Baumer June 17, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

keep calculating currentSum until :
1. Either currentSum = desired sum
2. or if currentSum > desired sum , reset currentSum= value of current element(i.e we are starting out check sub-sequence from here)
3. or if currentSum < desired sum , keep adding next element

public class FindSumContinousArray {

	public static void findContinuousSubArray(int[] arr , int sum){

		int iCuurent=0;
		int jCurrent=0;
		int curSum=0;
		
		while(iCuurent <= arr.length-1 && jCurrent <= arr.length-1){
			
			curSum = curSum + arr[jCurrent]; // find new sum including current element
			if(curSum == sum){
				System.out.println("Sum found from elemen : " + iCuurent +" " +jCurrent);
				return;
			}else if(curSum > sum){
				iCuurent = jCurrent; // start from current element new sum
				curSum = arr[jCurrent];
				jCurrent++;
			}else{ // continue to include next element
				jCurrent++;
			}
		}		
	}
	
	public static void main(String[] args) {
		
		int[] arr = {1,3,5,2,4};
		findContinuousSubArray(arr,6);
	}
}

- Mayank Jain August 16, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

In 10 line of python, here you go.

def summed(seq, target):
    current_sum = 0
    for i in range(len(seq)):
        current_sum  = current_sum + seq[i]
        if current_sum == target:
            return True
        if current_sum > target:
            current_sum = 0
    return False
print summed([23, 6, 4, 8, 2, 2,], 22)

- donaghc December 15, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Since partial sums S[] make a sorted array we can use binary search to find whether there is a value that matches target, e.g. equals to S[k] + T, where k is the start index. We need to precompute partials sums.

This algorithms has O(n log n) time complexity worst case and O(n) space complexity.

boolean search(int[] A, int T) {
    int n = A.length();
    
    // S[i] = sum_{k < i} A[k]
    //
    // Hence,
    // sum_{i <= k < j} A[k] == S[j] - S[i]
    //
    // E.g.: 
    // S[0] = 0
    // S[1] = A[0]
    // ...
    // S[n] = A[0] + A[1] + ... + A[n-1]
    int[] S = computePartialSums();

    for (int i = 0; i < n; i += 1) {
        boolean found = binarySearch(S, i + 1, n + 1, T + S[i]);

        if (found) {
            // sum_{i <= k < j} A[k] == T
            return true;
        }
    }

    return false;
}

// fromIndex inclusive
// toIndex exclusive
boolean binarySearch(int[] a, int fromIndex, int toIndex, int searchValue) {
}

- Arkady Seletsky January 27, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

A recursive approach:

fun hasContinuousSequence(array: IntArray, sum: Int, startedSoustracting: Boolean = false): Boolean {
    if (array.isEmpty()) {
        return sum == 0
    }
    if (sum == 0) {
        return true
    }

    val first = if (sum - array.first() >= 0) {
        hasContinuousSequence(array.drop(1).toIntArray(), sum - array.first(), true)
    } else {
        false
    }
    val second = if (!startedSoustracting) {
        hasContinuousSequence(array.drop(1).toIntArray(), sum, startedSoustracting)
    } else {
        false
    }

    return first || second
}

- romain May 01, 2020 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

private static boolean hasContinuousSequence(int[] arr, int t) {
        if(arr == null) {
            return false;
        }

        int sum = 0;

        for(int i = arr.length - 1; i >= 0; i--) {
            if(sum == t) {
                return true;
            } else if(sum > t) {
                sum = arr[i];
            } else {
                sum += arr[i];
            }
        }


        return false;
    }

- PK February 27, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote
bool doesContSeqExists(int &vTargSum, vector<int> &vInput) {{{ int vSum = 0; int totalIterations = 0; totalIterations = vInput.size(); int skipIterations=0; for(int i=0;i<totalIterations;i++) {{{ skipIterations = 0; vSum = 0; for(auto e:vInput) {{{ if(skipIterations<i) {{{ skipIterations++; continue; }}} if(e == vTargSum) {{{ return true; }}} else {{{ vSum += e; if(vSum>vTargSum) {{{ vSum = 0; continue; }}} else if(vSum == vTargSum) {{{ return true; }}} }}} }}} }}} return false; }}} - kapilsatija February 27, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
-2
of 2 vote

private static boolean hasContinuousSequence(int[] arr, int t) {
        if(arr == null) {
            return false;
        }

        int sum = 0;

        for(int i = arr.length - 1; i >= 0; i--) {
            if(sum == t) {
                return true;
            } else if(sum > t) {
                sum = arr[i];
            } else {
                sum += arr[i];
            }
        }
        return false;
    }

- PK February 27, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

I don't see how this works.

- Gee February 27, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

You got the right idea but if (sum > i ) sum = arr[i]; section I don't think that is the right approach is better to subtract the first added value and so on.

- Nelson Perez March 02, 2015 | Flag


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