Facebook Interview Question
Software EngineersInterview Type: Phone Interview
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;
}
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)
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;
}
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;
}
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.
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).
@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, 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.
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
@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
}
}
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.
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.
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)
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
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;
}
}
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.
For negatives numbers, O(N) time solution exists!
See EDIT2 of my post and comment of eugene.varovoi
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.
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;
}
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;
}
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
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
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
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;
}
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;
}
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;
}
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;
}
}
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;
}
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;
}
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
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
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
{{ #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";
} }}
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;
}
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;
}
}
}
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
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 --
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");
}
}
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;
}
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++;
}
}
}
#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);
}
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);
}
}
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) {
}
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
}
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;
}
}
- Scott February 27, 2015