Facebook Interview Question
Country: United States
Interview Type: Phone Interview
def verify_sum(sum_given) :
data_array = [1,3,5,18]
len_data = len(data_array)
for i in range(len_data) :
j = 1
while j<=len_data :
sum_array = sum(data_array[i:j])
print sum_array
if sum_array == sum_given :
return data_array[i:j]
j+=1
return -1
if __name__ == '__main__' :
print verify_sum(18)
def largestContinuousSum(arr,n):
i=0
j=1
curSum=arr[0]
while j<len(arr) or i<j:
if curSum<n and j==len(arr):
return False
if curSum<n and j<len(arr):
curSum=curSum+arr[j]
j=j+1
if curSum==n:
return True
if i==j:
curSum=arr[i]
if curSum>n:
curSum=curSum-arr[i]
i=i+1
return False
print largestContinuousSum([1,3,5,18,20,19,33],39)
print largestContinuousSum([1,3,5,18,20,19,33],72)
print largestContinuousSum([1,3,5,18,20,19,33],79)
print largestContinuousSum([1,3,5,18,20,19,33],6)
print largestContinuousSum([1,3,5,18],8)
print largestContinuousSum([1,3,5,18],10)
print largestContinuousSum([1,3,5,18],40)
def largestContinuousSum(arr,n):
i=0
j=1
curSum=arr[0]
while j<len(arr) or i<j:
if curSum<n and j==len(arr):
return False
if curSum<n and j<len(arr):
curSum=curSum+arr[j]
j=j+1
if curSum==n:
return True
if i==j:
curSum=arr[i]
if curSum>n:
curSum=curSum-arr[i]
i=i+1
return False
print largestContinuousSum([1,3,5,18,20,19,33],39)
print largestContinuousSum([1,3,5,18,20,19,33],72)
print largestContinuousSum([1,3,5,18,20,19,33],79)
print largestContinuousSum([1,3,5,18,20,19,33],6)
print largestContinuousSum([1,3,5,18],8)
print largestContinuousSum([1,3,5,18],10)
print largestContinuousSum([1,3,5,18],40)
def largestContinuousSum(arr,n):
i=0
j=1
curSum=arr[0]
while j<len(arr) or i<j:
if curSum<n and j==len(arr):
return False
if curSum<n and j<len(arr):
curSum=curSum+arr[j]
j=j+1
if curSum==n:
return True
if i==j:
curSum=arr[i]
if curSum>n:
curSum=curSum-arr[i]
i=i+1
return False
print largestContinuousSum([1,3,5,18,20,19,33],39)
print largestContinuousSum([1,3,5,18,20,19,33],72)
print largestContinuousSum([1,3,5,18,20,19,33],79)
print largestContinuousSum([1,3,5,18,20,19,33],6)
print largestContinuousSum([1,3,5,18],8)
print largestContinuousSum([1,3,5,18],10)
print largestContinuousSum([1,3,5,18],40)
bool isContiguesSubArrayX(const vector<uint> &A, const int X)
{
uint size = A.size();
if(size == 0)
{
if(X == 0) return true;
return false;
}
if(X < 0) return false;
uint bPos = 0, ePos = 0, Sum = A[0];
while(bPos < size && ePos < size)
{
if(Sum == X) return true;
if(Sum < X)
{
if(++ePos >= size) return false;
Sum += A[ePos];
continue;
}
else
{
Sum -= A[bPos++];
if(bPos == ePos)
{
if(A[bPos] == X) return true;
bPos++; ePos++;
Sum = A[bPos];
continue;
}
else if(bPos == ePos+1)
{
ePos++;
Sum = A[bPos];
}
if(Sum == X) return true;
assert(bPos<=ePos);
}
}
return false;
}
Time: O(N)
Space: O(1)
public boolean isContainsSum(int[] arr, int target) {
int start = 0;
int end = 0;
int currentSum = arr[0];
while (currentSum != target) {
if (currentSum < target) {
if(end == arr.length - 1) {
break;
}
end++;
currentSum += arr[end];
} else if (currentSum > target) {
if(start == arr.length - 1) {
break;
}
currentSum -= arr[start];
start++;
if(start > end) {
end = start;
currentSum = arr[start];
}
}
}
return currentSum == target;
}
This could be a php version with sort and array_splice
function checkContigSumFromArray($aToCheck, $iSumToFind){
asort($aToCheck);
while (count($aToCheck) > 0){
$sum = 0;
for ($i = 0; $i < count($aToCheck); $i++){
$sum += $aToCheck[$i];
if ($sum == $iSumToFind){
return true;
}else if ($sum > $iSumToFind){
$i = count($aToCheck);
array_splice($aToCheck, 0, 1);
}else if ($i+1 == count($aToCheck) && $sum < $iSumToFind){
return false;
}
}
}
return false;
}
It could be a php version
function checkContigSumFromArray($aToCheck, $iSumToFind){
asort($aToCheck);
while (count($aToCheck) > 0){
$sum = 0;
for ($i = 0; $i < count($aToCheck); $i++){
$sum += $aToCheck[$i];
if ($sum == $iSumToFind){
return true;
}else if ($sum > $iSumToFind){
$i = count($aToCheck);
array_splice($aToCheck, 0, 1);
}else if ($i+1 == count($aToCheck) && $sum < $iSumToFind){
return false;
}
}
}
return false;
}
PHP Alternative with asort and array_splice
function checkContigSumFromArray($aToCheck, $iSumToFind){
asort($aToCheck);
while (count($aToCheck) > 0){
$sum = 0;
for ($i = 0; $i < count($aToCheck); $i++){
$sum += $aToCheck[$i];
if ($sum == $iSumToFind){
return true;
}else if ($sum > $iSumToFind){
$i = count($aToCheck);
array_splice($aToCheck, 0, 1);
}else if ($i+1 == count($aToCheck) && $sum < $iSumToFind){
return false;
}
}
}
return false;
}
#include<stdio.h>
int main(int argc, char *argv[]){
int count = 0;
int left = 0;
int right = 1;
int sum = 0;
int tmp = 0;
scanf("%d", &count);
scanf("%d", &sum);
int arr[count];
for (int i=0; i<count;i++){
scanf("%d",arr+i);
}
tmp = arr[0];
while(right < count){
printf("tmp = %d", tmp);
if (tmp == sum){
printf("left = %d right = %d ", left, right-1);
return 0;
}
if (tmp > sum) {
tmp = tmp - arr[left];
left++;
}
if (tmp < sum){
tmp = tmp + arr[right];
right++;
}
}
}
#include<stdio.h>
int main(int argc, char *argv[]){
int count = 0;
int left = 0;
int right = 1;
int sum = 0;
int tmp = 0;
scanf("%d", &count);
scanf("%d", &sum);
int arr[count];
for (int i=0; i<count;i++){
scanf("%d",arr+i);
}
tmp = arr[0];
while(right < count){
printf("tmp = %d", tmp);
if (tmp == sum){
printf("left = %d right = %d ", left, right-1);
return 0;
}
if (tmp > sum) {
tmp = tmp - arr[left];
left++;
}
if (tmp < sum){
tmp = tmp + arr[right];
right++;
}
}
}
#include<stdio.h>
int main(int argc, char *argv[]){
int count = 0;
int left = 0;
int right = 1;
int sum = 0;
int tmp = 0;
scanf("%d", &count);
scanf("%d", &sum);
int arr[count];
for (int i=0; i<count;i++){
scanf("%d",arr+i);
}
tmp = arr[0];
while(right < count){
printf("tmp = %d", tmp);
if (tmp == sum){
printf("left = %d right = %d ", left, right-1);
return 0;
}
if (tmp > sum) {
tmp = tmp - arr[left];
left++;
}
if (tmp < sum){
tmp = tmp + arr[right];
right++;
}
}
}
def sublist_reduced_sum(num_list, target):
outer_idx = 0
end = len(num_list)
while outer_idx < end:
total = 0
for i in range(outer_idx, end):
total += num_list[i]
if total > target:
break
elif total == target and i != outer_idx:
return True
outer_idx += 1
return False
test_list = [9,3,7,4,8]
target = 8
print(sublist_reduced_sum(test_list, target))
C Version
/*
* Given an array of positive integers and a target total of X, find if there exists a contiguous subarray with sum = X
*
* [1, 3, 5, 18]
* X = 8 Output: True
* X = 9 Output: True
* X = 10 Output: False
* X = 40 Output :False
*/
#include <stdio.h>
#define SIZE 4
#define VERDICT(_X_) printf("X = %3d Output = %s\n", _X_, (findSubArray(_X_) ? "True" : "False"))
static int A[SIZE] = {1,3,5,18};
int
findSubArray(int X)
{
int sum;
int i = 0; // Array iterator
int j = 0; // SubArray iterator
for (i = 0; i < SIZE; i++) {
j = i;
sum = 0;
while ((X > sum) && (j < SIZE)) {
sum = sum + A[j++];
if (sum == X) {
return 1; // Found contiguous sub-array sum = X
}
}
}
return 0; // contiguous sub-array not found.
}
int
main()
{
VERDICT(1);
VERDICT(4);
VERDICT(8);
VERDICT(19);
VERDICT(21);
VERDICT(22);
VERDICT(23);
VERDICT(26);
VERDICT(27);
return 0;
}
output for test data
X = 1 Output = True
X = 4 Output = True
X = 8 Output = True
X = 19 Output = False
X = 21 Output = False
X = 22 Output = False
X = 23 Output = True
X = 26 Output = True
X = 27 Output = True
public static boolean contiguousSum(int[] arr, int targetSum)
{
int max = 0;
for (int i=0; i<arr.length; i++) {
max = arr[i];
if (arr[i] >= targetSum)
continue;
for (int j=i + 1; j<arr.length; j++) {
max += arr[j];
if (max == targetSum)
return true;
else if (max > targetSum || arr[j] >= targetSum)
break;
}
}
return false;
}
int find_sum(int* arr, int num, int sum, int *begin, int *end)
{
*begin = *end = -1;
if ( sum <= 0) return 0;
int tmp = 0;
int start = 0;
int finish = 0;
for (int i = 0; i < num; i++) {
tmp += arr[i];
while ( tmp > sum && start < i ) {
tmp -= arr[start];
start++;
}
if ( tmp == sum ) {
*begin = start;
*end = i;
return 1;
}
}
return 0;
}
void print_results(int *arr, int num, int sum)
{
printf("Find sum: %d\n", sum);
int begin = -1, end = -1;
if (find_sum(arr, 10, sum, &begin, &end)) {
printf("Sum %d found between indices %d and %d\n", sum, begin, end);
show("window:", arr, begin, end);
} else {
printf("sum %d NOT found\n", sum);
}
}
function sumWindow(array, target) {
var startIndex = 0;
var endIndex = 1;
var total = array[startIndex] + array[endIndex];
while(endIndex < array.length && startIndex < array.length -1) {
if(total === target) {
break;
}
if(total < target || (endIndex - startIndex === 1)) {
endIndex++;
total += array[endIndex];
} else {
total -= array[startIndex];
startIndex++;
}
}
return (total === target);
}
console.log(sumWindow([1, 3, 5, 18], 40));
Swift:
func existsContiguousSubArray(array: [Int], sum: Int) -> Bool {
guard array.count > 0 else { return false }
var start = 0
var end = 0
var result = 0
while start <= end && end < array.count {
result = result + array[end]
if result == sum {
return true
} else if result > sum {
result -= array[start]
start = start + 1
}
end = end + 1
}
return false
}
Here is a working example in c++:
#include <iostream>
#include <vector>
using namespace std;
bool find_if_sequence_sub_exist(vector<int> a, int sum)
{
int i=0, startIdx=0, total=0;
while(i < a.size() && startIdx <= i)
{
if(total > sum)
{
total -= a[startIdx];
startIdx++;
}
else if(total ==sum)
return true;
else
{
total += a[i];
i++;
}
}
return false;
}
int main(int argc, const char * argv[]) {
vector<int> arr = {1, 3, 5, 18};
int x = 8;
cout<<"Result: "<<find_if_sequence_sub_exist(arr, x)<<endl;
return 0;
}
Take care of boundary cases, for example for arrays of 0 length:
public boolean existsContigous(int[] array, int x){
int size = array.length;
if(size == 0)
if(x == 0)
return true;
else
return false;
int left = 0;
int right = 0;
int sum = 0;
while(right < size){
if(sum == x)
return true;
if(sum < x){
sum += array[right];
right++;
}else{
sum -= array[left];
left++;
}
}
return false;
}
This is an Objective-C solution
-(void)getSubArray:(NSMutableArray *)array withSum:(int)sum{
int tempSum = [array[0] intValue];
int i;
int start = 0;
for(i = 1; i < [array count]; i++){
while(tempSum > sum && start < i + 1){
tempSum -= [array[start] intValue];
start++;
}
if(tempSum == sum){
NSLog(@"FOUND SUM FROM INDEX %i TO %i", start, i - 1);
return;
}
if(i < [array count]){
tempSum += [array[i] intValue];
}
}
NSLog(@"NOT FOUND");
}
The critical phrase here is 'positive integers' because even if we just extended the the value set from natural numbers to whole numbers with the addition of zero, the summation would become unbounded, or up to 'N' where 'N' is the full size of the array.
But, with natural numbers, the subarray size is bounded by the sum, which is maximally reached with all ones. That limits running time at O(nk) and O(k) space complexity, where k is the target sum and n is the array size.
One could go further with early exit on the subarray sum, but there's little point as that has no effect on the worst case running time.
#include <stdio.h>
int findSubArray(unsigned *d, unsigned d_size, unsigned X)
{
for (int n = 0; n < d_size; n++) {
int sum = 0;
for (int i = 0; i < X; i++) {
if (n+i >= d_size)
break;
sum += d[n+i];
if (sum == X)
return 1;
}
}
return 0;
}
int main(int argc, char **argv)
{
unsigned in[] = { 1, 3, 5, 18, };
printf("Sum exists for %u? %s\n", 9,
findSubArray(in, 4, 9) ? "True" : "False");
printf("Sum exists for %u? %s\n", 10,
findSubArray(in, 4, 10) ? "True" : "False");
printf("Sum exists for %u? %s\n", 40,
findSubArray(in, 4, 40) ? "True" : "False");
}
import java.util.*;
public class ContiguousSubarray {
static int[] containsSubarray(int[] a, int s) {
int lt = 0, rt = 0, sum = 0;
while (sum < s && rt < a.length) {
sum += a[rt];
while (sum > s) sum -= a[lt++];
if (sum == s) return new int[] {lt, rt};
rt++;
}
return null;
}
static void test(int[] a, int s) {
System.out.println("Input array is: " + Arrays.toString(a));
int[] result = containsSubarray(a, s);
if (result == null)
System.out.println("Subarray not found with sum " + s);
else
System.out.println("Subarray " + Arrays.toString(result) + " sums up to " + s);
System.out.println("______________________________");
}
public static void main(String[] args) {
int[] a = {1, 3, 5, 18};
test(a, 1);
test(a, 8);
test(a, 9);
test(a, 10);
test(a, 23);
test(a, 40);
}
}
def subarrayForSumExists(nums, x):
if nums is None or len(nums) == 0 or x < 0:
return False
nlen = len(nums)
start = 0
end = 0
sum = 0
while end < nlen:
while end < nlen and sum < x:
sum = sum + nums[end]
if sum == x :
return True
end += 1
# sum > x at this point or end == nlen
while start < end and sum > x:
sum -= nums[start]
if sum == x:
return True
start += 1
return False
O(N) time O(1) space solution in C#
static bool checkForSum(uint[] arr, uint sum)
{
if (arr == null || !arr.Any())
return false;
uint accum = 0;
int begin = 0;
int end = 0;
while(end < arr.Length)
{
accum += arr[end++];
if (accum > sum)
while (begin < end && accum > sum)
accum -= arr[begin++];
else if (accum == sum)
return true;
}
return false;
}
it is brute force,there should be better way to do the same.
public class SubArrayWithsum {
public static void main(String[] args) {
// TODO Auto-generated method stub
int[]arr={1,3,5,18};
boolean is_found=false;
int sumdesired=8;
int currentsum=0;
for(int j=0;j<arr.length;j++)
{
currentsum=0;
for(int k=j;k<arr.length;k++)
{
currentsum+=arr[k];
if(currentsum==sumdesired)
{
is_found=true;
System.out.println("yes there exists contigous array with that sum");
break;
}
}
if(is_found)
break;
}
}
}
Since the numbers are a positive we should be able to do this with a window function. We move the right side as long as we don't make the sum too large, otherwise we move the left one. Complexity O(N) time, O(1) space.
- Johnie June 29, 2016