Facebook Interview Question
Senior Software Development EngineersCountry: United States
Interview Type: Phone Interview
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>();
result.add(array[i]);
for (int j = i + 1; sum < targetValue && j < array.length; j++) {
sum += array[j];
result.add(array[j]);
}
if (sum == targetValue) {
result.forEach(x -> System.out.print(x + " "));
System.out.println();
}
}
}
}
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()
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);
printf("\n%d\n", adjacent(list,length, 31));
return 0;
}
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)
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++;
}
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++;
}
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++) {
result.add(nums[j]);
}
return result;
} else if (sum > n) {
sum = nums[i];
start = i;
}
}
return null;
}
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++) {
result.add(nums[j]);
}
} else if (sum > n) {
sum = nums[i];
start = i;
}
}
return result;
}
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++) {
result.add(nums[j]);
}
} else if (sum > n) {
sum = nums[i];
start = i;
}
}
return result;
}
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++) {
result.add(nums[j]);
}
} else if (sum > n) {
sum = nums[i];
start = i;
}
}
return result;
}
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;
}
#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
$$
#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
#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$
#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);
}
---
#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);
}
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>();
values.add(i);
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;
}
}
Use two pointers, O(n) time complexity, O(1) space:
- jiahuang December 12, 2017