## Facebook Interview Question for Senior Software Development Engineers

• 0

Country: United States
Interview Type: Phone Interview

Comment hidden because of low score. Click to expand.
4
of 6 vote

Use two pointers, O(n) time complexity, O(1) space:

``````////assume target is positive
public boolean hasContSum(List<Integer> list, int target)
{
int tail = 0;
int sum = 0;
for(int i=0;i<list.size();i++)
{
sum+=list.get(i);
while(sum>target){
sum-=list.get(tail++);
}
if(sum == target) return true;
}
return false;
}``````

Comment hidden because of low score. Click to expand.
0

your solution doesn't work with: list=[] and target=0.
It will return false, but it should be true.

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

``````bool HasSumSubarray(vector<int> const &a, int n)
{
int sum = 0;
int start = 0;
for (int i = 0; i < a.size(); ++i) {
sum += a[i];
while (sum > n &&
start <= i)
{
sum -= a[start++];
}
if (sum == n) {
return true;
}
}
return false;
}``````

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

Can the list contain negative numbers?

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

``````func solve(array: [Int], input: Int) -> Bool {
var left = input

for element in array {
left -= element

if left == 0 {
return true
} else if (left < 0) {
left = input - element
continue
}
}

return false
}``````

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

private static boolean sumCon(int[] list,int target){
int sum=0,position=0;

for(int i=0;i<list.length;i++){
sum+=list[i];

if(sum==target){
return true;
}

while(sum>target){
sum-=list[position];
position++;
}
}
return false;
}

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

``````private static boolean sumCon(int[] list,int target){
int sum=0,position=0;

for(int i=0;i<list.length;i++){
sum+=list[i];

if(sum==target){
return true;
}

while(sum>target){
sum-=list[position];
position++;
}
}
return false;
}``````

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

``````private static boolean sumCon(int[] list,int target){
int sum=0,position=0;

for(int i=0;i<list.length;i++){
sum+=list[i];

if(sum==target){
return true;
}

while(sum>target){
sum-=list[position];
position++;
}
}
return false;
}``````

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

Test:
list: [8,10,2,3,1,4,4] target = -10

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

Gives all possible solutions with complexity of O(n2)

``````public class ContElemSum {

public static void main(String[] args) {

Integer[] array = {6, 5, 3, 2, 1, 7};

Integer targetValue = 10;

for (int i = 0; i < array.length; i++) {
Integer sum = array[i];
List<Integer> result = new ArrayList<Integer>();
for (int j = i + 1; sum < targetValue && j < array.length; j++) {
sum += array[j];
}
if (sum == targetValue) {
result.forEach(x -> System.out.print(x + " "));
System.out.println();
}
}
}
}``````

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

``````def main():
input_list = [6, 5, 3, 2, 1, 7]
number = int(input("accept number"))
len_list = len(input_list) - 1

total = 0
l = []
j = 0
for i in range(len_list):
j = i + 1
total = sum(input_list[i: j + 1])
if total == number:
print("{0}===>{1}".format(total, input_list[i: j + 1]))
if total < number:
k = j + 1
total += sum(input_list[k:k + 1])
if total == number:
print("{0}===>{1}".format(total, input_list[i: k + 1]))

if __name__ == '__main__':
main()``````

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

O(n^2) brute force solution:

``````int adjacent(int list[], int length, int number)
{
for(int i = 0; i < length; i++){
int helper = 0;
for(int j = 0; j < length; j++){
helper = helper + list[i+j];
if( helper == number) {
return 1;
}
}
}
return 0;
}

int main(void)
{
int list[] = {6, 3, 5, 3, 2, 22, 3, 4, 100, 6, 7, 10, 11};

int length = sizeof(list)/sizeof(*list);

return 0;
}``````

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

All solutions assume positive numbers. Here a solution with o(n^2) time, o(n) space, not assuming this. Working with negative numbers

``````def sum_find(x, s):
if x[0] == s:
return x[0]
cumsum = [x[0]]*len(x)
for end in range(1,len(cumsum)):
cumsum[end] = cumsum[end-1] + x[end]
if cumsum[end] == s:
return x[:end+1]
for start in range(end):
if cumsum[end] - cumsum[start] == s:
return x[start+1:end+1]
return -1

x = [2,-3,5,1,-4,6,7,5,7,3,2,2,5,7,8,4,-2,-7,-2,5,3,-2,7,3,10,9,43]
sum_find(x, 11)``````

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

``````public void ContiguousElementsEqualToSum(int [] input, int sum)
{
int currentSum = 0;
int currentIndex = 0;
int lastIndex = 0;
while (currentIndex < input.Length)
{
if(currentSum < sum || currentIndex == 0)
{
currentSum += input[currentIndex];
}
while (currentSum >= sum)
{
// Keep removing the first one.

if (currentSum == sum)
{
for (int i = lastIndex; i <= currentIndex; i++)
{
Console.Write("{0} ", input[i]);
}
Console.WriteLine();
}
currentSum -= input[lastIndex];
lastIndex++;
}

currentIndex++;
}``````

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

``````public void ContiguousElementsEqualToSum(int [] input, int sum)
{
int currentSum = 0;
int currentIndex = 0;
int lastIndex = 0;
while (currentIndex < input.Length)
{
if(currentSum < sum || currentIndex == 0)
{
currentSum += input[currentIndex];
}
while (currentSum >= sum)
{
// Keep removing the first one.

if (currentSum == sum)
{
for (int i = lastIndex; i <= currentIndex; i++)
{
Console.Write("{0} ", input[i]);
}
Console.WriteLine();
}
currentSum -= input[lastIndex];
lastIndex++;
}

currentIndex++;
}``````

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

For given set above, if n is 10 shouldn't we return {5, 3, 2} instead of {2, 1, 7}?

``````public List find(int[] nums, int n) {
int sum = 0;
int start = 0;
int end = 0;
for (int i = 0; i < nums.length; i++) {
sum += nums[i];
if (sum == n) {
end = i;
List<Integer> result = new ArrayList<>();
for (int j = start; j <= end; j++) {
}
return result;
} else if (sum > n) {
sum = nums[i];
start = i;
}
}
return null;
}``````

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

Shouldn't it return {5, 3, 2} if n is 10? This could be done as O(n)

``````public List getContiguousSum(int[] nums, int n) {
List<Integer> result = new ArrayList<>();
int sum = 0;
int start = 0;
int end = 0;
for (int i = 0; i < nums.length; i++) {
sum += nums[i];
if (sum == n) {
end = i;
for (int j = start; j <= end; j++) {
}
} else if (sum > n) {
sum = nums[i];
start = i;
}
}
return result;
}``````

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

Shouldn't it return {5, 3, 2} if n is 10? This could be done as O(n)

``````public List getContiguousSum(int[] nums, int n) {
List<Integer> result = new ArrayList<>();
int sum = 0;
int start = 0;
int end = 0;
for (int i = 0; i < nums.length; i++) {
sum += nums[i];
if (sum == n) {
end = i;
for (int j = start; j <= end; j++) {
}
} else if (sum > n) {
sum = nums[i];
start = i;
}
}
return result;``````

}

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

Shouldn't it return {5, 3, 2} if n is 10? This could be done as O(n)

``````public List getContiguousSum(int[] nums, int n) {
List<Integer> result = new ArrayList<>();
int sum = 0;
int start = 0;
int end = 0;
for (int i = 0; i < nums.length; i++) {
sum += nums[i];
if (sum == n) {
end = i;
for (int j = start; j <= end; j++) {
}
} else if (sum > n) {
sum = nums[i];
start = i;
}
}
return result;
}``````

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

O(n) solution

``````#include <stdio.h>
#include <stdlib.h>
#include <math.h>

int findMaxSubArraySum(int arr[], int n, int sum)
{
int curr_sum = arr[0], max_sum = 0, start = 0;

for(int i = 1; i < n; i++){

// If curr_sum becomes greater than sum subtract starting elements of array
while( curr_sum > sum && start < i) {
curr_sum -= arr[start];
start++;
}

max_sum = fmax(max_sum, curr_sum);

curr_sum += arr[i];
}

if (curr_sum <= sum)
max_sum = fmax(max_sum, curr_sum);

if(max_sum == sum)
return 1;
else
return 0;

}

int main(int argc, char **argv)
{
int list[] = {6, 3, 5, 3, 2, 22, 3, 4, 100, 6, 7, 10, 11};

int n = sizeof(list)/sizeof(*list);

int sum = atoi(argv[1]);

printf("\n%d\n",findMaxSubArraySum(list, n, sum));

return 0;
}``````

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

``````#include <stdio.h>
#include <stdlib.h>

void print_sub_array(int *arr, int start_index, int end_index)
{
while(start_index <= end_index) {
printf("%d ", arr[start_index++]);
}
printf("\n");

return;
}

void find_contiguous_elements_sum(int *arr, int num_elements, int sum)
{
int start_index = 0, end_index = 0;
int running_sum = 0;
int i = 0;

for(i = 0; i < num_elements; i++) {
running_sum += arr[i];

if (running_sum > sum) {
/* discard elements from the start_index till running_sum < sum */
while(running_sum > sum) {
running_sum -= arr[start_index];
start_index++;
}
}

if (running_sum == sum) {
print_sub_array(arr, start_index, (end_index = i));
/* Continue finding next series */
running_sum -= arr[start_index];
start_index++;
}

}

return;
}

int main(int argc, char *argv[])
{
int arr[6] = {6,5,3,2,1,7};
find_contiguous_elements_sum(&arr[0], 6, 8);
find_contiguous_elements_sum(&arr[0], 6, 10);
exit(0);
}

*** OUTPUT ***

\$\$  ./a.out
5 3
1 7
5 3 2
2 1 7
\$\$``````

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

``````#include <stdio.h>
#include <stdlib.h>

void print_sub_array(int *arr, int start_index, int end_index)
{
while(start_index <= end_index) {
printf("%d ", arr[start_index++]);
}
printf("\n");

return;
}
void find_contiguous_elements_sum(int *arr, int num_elements, int sum)
{
int start_index = 0, end_index = 0;
int running_sum = 0;
int i = 0;

for(i = 0; i < num_elements; i++) {
running_sum += arr[i];

if (running_sum > sum) {
/* discard elements from the start_index till running_sum < sum */
while(running_sum > sum) {
running_sum -= arr[start_index];
start_index++;
}
}

if (running_sum == sum) {
print_sub_array(arr, start_index, (end_index = i));
/* Continue finding next series */
running_sum -= arr[start_index];
start_index++;
}

}

return;
}

int main(int argc, char *argv[])
{
int arr[6] = {6,5,3,2,1,7};
find_contiguous_elements_sum(&arr[0], 6, 8);
find_contiguous_elements_sum(&arr[0], 6, 10);
exit(0);
}

*** OUTPUT ***
cup-questions\$ ./a.out
5 3
1 7
5 3 2
2 1 7``````

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

``````#include <stdio.h>
#include <stdlib.h>

void print_sub_array(int *arr, int start_index, int end_index)
{
while(start_index <= end_index) {
printf("%d ", arr[start_index++]);
}
printf("\n");

return;
}
void find_contiguous_elements_sum(int *arr, int num_elements, int sum)
{
int start_index = 0, end_index = 0;
int running_sum = 0;
int i = 0;

for(i = 0; i < num_elements; i++) {
running_sum += arr[i];

if (running_sum > sum) {
/* discard elements from the start_index till running_sum < sum */
while(running_sum > sum) {
running_sum -= arr[start_index];
start_index++;
}
}

if (running_sum == sum) {
print_sub_array(arr, start_index, (end_index = i));
/* Continue finding next series */
running_sum -= arr[start_index];
start_index++;
}

}

return;
}

int main(int argc, char *argv[])
{
int arr[6] = {6,5,3,2,1,7};
find_contiguous_elements_sum(&arr[0], 6, 8);
find_contiguous_elements_sum(&arr[0], 6, 10);
exit(0);
}
cup-questions\$ ./a.out
5 3
1 7
5 3 2
2 1 7
cup-questions\$``````

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

``````#include <stdio.h>
#include <stdlib.h>

void print_sub_array(int *arr, int start_index, int end_index)
{
while(start_index <= end_index) {
printf("%d ", arr[start_index++]);
}
printf("\n");

return;
}
void find_contiguous_elements_sum(int *arr, int num_elements, int sum)
{
int start_index = 0, end_index = 0;
int running_sum = 0;
int i = 0;

for(i = 0; i < num_elements; i++) {
running_sum += arr[i];

if (running_sum > sum) {
/* discard elements from the start_index till running_sum < sum */
while(running_sum > sum) {
running_sum -= arr[start_index];
start_index++;
}
}

if (running_sum == sum) {
print_sub_array(arr, start_index, (end_index = i));
/* Continue finding next series */
running_sum -= arr[start_index];
start_index++;
}

}

return;
}

int main(int argc, char *argv[])
{
int arr[6] = {6,5,3,2,1,7};
find_contiguous_elements_sum(&arr[0], 6, 8);
find_contiguous_elements_sum(&arr[0], 6, 10);
exit(0);
}

---``````

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

``````#include <stdio.h>
#include <stdlib.h>

void print_sub_array(int *arr, int start_index, int end_index)
{
while(start_index <= end_index) {
printf("%d ", arr[start_index++]);
}
printf("\n");

return;
}
void find_contiguous_elements_sum(int *arr, int num_elements, int sum)
{
int start_index = 0, end_index = 0;
int running_sum = 0;
int i = 0;

for(i = 0; i < num_elements; i++) {
running_sum += arr[i];

if (running_sum > sum) {
/* discard elements from the start_index till running_sum < sum */
while(running_sum > sum) {
running_sum -= arr[start_index];
start_index++;
}
}

if (running_sum == sum) {
print_sub_array(arr, start_index, (end_index = i));
/* Continue finding next series */
running_sum -= arr[start_index];
start_index++;
}

}

return;
}

int main(int argc, char *argv[])
{
int arr[6] = {6,5,3,2,1,7};
find_contiguous_elements_sum(&arr[0], 6, 8);
find_contiguous_elements_sum(&arr[0], 6, 10);
exit(0);
}``````

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

``````import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

public class ExistsSubarraySum {
public static void main(String[] args){
int[] testcase1 = {6,5,3,2,1,7};

boolean actual = existsSubarraySum(testcase1, 8);
System.out.println("test1 : target 8 " + actual);

actual = existsSubarraySum(testcase1, 10);
System.out.println("test1 : target 10 " + actual);

int[] testcase2 = {-6,2,3,-2,4,1,-5,6};
actual = existsSubarraySum(testcase2, 7);
System.out.println("test2 : target 7 " + actual);
}

public static boolean existsSubarraySum(int[] a, int target){
// if all elements are non negative, use specialized solution, O(n) time
boolean allElementsAreNonNegative = true;
for (int e : a){
if (e < 0) {
allElementsAreNonNegative = false;
break;
}
}
if (allElementsAreNonNegative) {
return existsSubarraySumNonNegativeElements(a,target);
} else {
// else -- has negative elements
return existsSubarraySumGeneric(a,target);
}
}

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

/**
* 1) Compute prefix sums S
* 2) for each i check if S(i) + target present
*/
public static boolean existsSubarraySumGeneric(int[] a, int target){
int n = a.length;
int[] prefixSum = new int[n];

Map<Integer, Set<Integer>> sumVsPrefixIndex = new HashMap<Integer, Set<Integer>>();
for (int i = 0; i < n; i++){
prefixSum[i] = ((i > 0) ? prefixSum[i-1] : 0) + a[i];

Set<Integer> values =  (sumVsPrefixIndex.containsKey(prefixSum[i])) ?
sumVsPrefixIndex.get(prefixSum[i]) : new HashSet<Integer>();

sumVsPrefixIndex.put(prefixSum[i], values);
}

for (int i = 0; i < n; i++){
if (sumVsPrefixIndex.containsKey(prefixSum[i] + target)){
return true;
}

Set<Integer> values = sumVsPrefixIndex.get(prefixSum[i]);
values.remove(i);
if (values.size() == 0){
sumVsPrefixIndex.remove(prefixSum[i]);
}
}

return false;
}
}``````

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.

### 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.