Facebook Interview Question
Country: United States
Interview Type: Phone Interview
Can be done by using a dynamic programming approach. Create a matrix say A such that
A[i][j] = sum of the numbers from index i to j in the original array. and also i <= j
To build this matrix use
A[i][j] = A[i][j-1] + Input[j]
Input is the input array.
Print the i and j indices for which the value of A[i][j] = 0
This is not the best dynamic programming method.
A simple way is,
use an array sum[i] to present the sum from data[0] to data[i]. A special 0 at beginning to simplify the logic later.
Then, just find the same values in sum[].
For example,
[-1, -3, 4, 5, -2, -7]
[0, -1, -4, 0, 5, 3, -4]
There is a pair 0, that mean the range from 0 to 2.
Another pair -4, that means the range form 2 to 5.
A hash can be used to find the same value pair.
Space: O(N)
Time: O(N)
@Jie
How would you find the duplicates in O(N) time and O(N) space. The duplicate elements might repeat more than twice, in which case, we need to store the indices of all the prev occurences of the element. For example, if the cummulative array were
[0, -1, -4, 0, 5, 3,0, -4]
There is a pair 0, that means the range from 0 to 2.
There is a pair 0, that means the range from 0 to 5.
There is a pair 0, that means the range from 3 to 5.
So, for this, probably we need to create a bucket kind of structure with each bucket refering to the elements of the cumm. array and each bucket containg a list of indices of occurence of the bucket element in the cumm. array. This would lead to worst case time complexity of O(n^2) {when all elements of cumm. array are same; we need to print all n_Choose_2 pairs} and O(max_value_of_sum_in_cumm_array*n) space.
Can you suggest an improvement over this approach.
But it's not Ω(N), because you have to go through the sum array after running the original array.
Friends,
Jie's solution can be modified to provide O(N) time complexity.
1. Each Hash table element can store Pair of 'sum' and 'list of indexes' to array of elements. Each list will have array indexes with equal sum.
3. Maintain another 'master list' of 'list of indexes with more than one item' separately. This list will be used to print sub sequences.
This is a simple recursive solution. You can optimize it by storing the solution to the sub-problems (dynamic programming).
#include<stdio.h>
void print_zero(int a[], int n, int indx, int sum, int r[], int r_indx)
{
int i,j;
for(i=indx; i<n; i++)
{
r[r_indx]=a[i];
if(sum+a[i]==0)
{
for(j=0; j<r_indx; j++)
printf("%d ",r[j]);
printf("%d\n",a[i]);
}
print_zero(a, n, i+1, sum+a[i], r, r_indx+1);
}
}
int main()
{
int a[]={1,-1,2,-2};
int n = sizeof(a)/sizeof(a[0]);
int r[n];
print_zero(a,n,0,0,r,0);
return 0;
}
It could be done with O(n)
1) run cumulate sum on the original array
2) append [0] in font of this cum_sum_array
3) check if two item in this cum_sum_array are same (for requirement sum==0, this could be done in O(n))
Totally time spend is O(2n) = O(n)
I'm using python:
import numpy as np
def get_sum(array):
cumsum_array = [0] + np.cumsum(array).tolist()
key_dict = {}
for index, cum_sum in enumerate(cumsum_array):
if cum_sum not in key_dict:
key_dict[cum_sum] = index
continue
print array[key_dict[cum_sum]: index]
if __name__ == '__main__':
array = [-1, -3, 4, 5, -2, -4, 6]
get_sum(array)
output:
[-1, -3, 4]
[-3, 4, 5, -2, -4]
[-2, -4, 6]
One problem is that same cum_sum may appear more than twice, using a key_dict is not enough
you should update the key_dict[cum_sum] when cum_sum may appear more than twice,like array = [-1, -3, 4, 5, -2, -4, 6,-5]
the code should be
def get_sum(array):
cumsum_array = [0] + np.cumsum(array).tolist()
key_dict = {}
for index, cum_sum in enumerate(cumsum_array):
if cum_sum not in key_dict:
key_dict[cum_sum] = index
continue
print array[key_dict[cum_sum]: index]
key_dict[cum_sum] = index
Your solution won't show all options for [-1,-3,4,-1,1,-1,5]. @fword solution neither.
The following adjustment will do:
def get_sum(array):
cumsum_array = [0] + np.cumsum(array).tolist()
key_dict = {}
for index, cum_sum in enumerate(cumsum_array):
if cum_sum not in key_dict:
key_dict[cum_sum] = [index]
continue
for i,v in enumerate(key_dict[cum_sum]):
print array[v: index]
key_dict[cum_sum].append(index)
void printTriplet(const int a[], int n)
{
int result[n][n] = {0};
for( int x = 0; x <= n ; x ++ )
{
for( int y = 0; y < n; y ++ )
result[x][y] = MAXINT;
}
for( int i = 0; i < n; i ++ )
{
for( int x = 0; x <= i ; x ++ )
{
for( int y = i; y < n; y ++ )
{
if( result[x][y] == MAXINT )
result[x][y] = 0;
result[x][y] += a[i];
}
}
}
for( int x = 0; x <= n ; x ++ )
{
for( int y = 0; y < n; y ++ )
if( result[x][y] == 0 )
print( a, x, y );
}
}
void print( int a[], int x, int y )
{
printf("Triplet: ");
for( int i = x; i <= y; i++ )
{
printf("%d ", a[i] );
}
printf("\n");
}
If the problem is looking for subarrays, then it can be solved by divide and conquer;
Split the problem into three subproblems:
1. All subarrays in array A[0...n/2 - 1] that sum to 0
2. All subarrays containing element a[n/2] that sum to 0
3. All subarrays in array A[n/2 + 1..n] that sum to 0
The time complexity is O(n (logn)^2)
T(n) = 2T(n/2) + nlogn
Space complexity is O(n)
Otherwise it is subset sum problem.
void print_subarray(int* data, int start, int end) {
for (int i = start; i <= end; i++) {
cout << data[i];
if (i < end) { cout << ", "; }
}
cout << endl;
return;
}
void find_subarray_partial(int* data, int* buffer, int* indexes, int start, int end) {
if (start > end) { return; }
if (start == end) {
if (data[start] == 0) {
print_subarray(data, start, start);
}
return;
}
int middle = start + (end - start) / 2;
find_subarray_partial(data, start, middle - 1);
find_subarray_partial(data, middle + 1, end);
// Sub problem in which data[middle] must be part of the subarray
// 1. Calculate the sum around data[middle]
buffer[middle] = data[middle];
int sum = data[middle];
for (int i = middle - 1; i >= start; i--) {
sum += data[i];
buffer[i] = sum;
}
sum = data[middle];
for (int i = middle + 1; i <= end; i++) {
sum += data[i];
buffer[i] = sum;
}
// 2. Sort the sums on left and right side of data[middle] separately, and record indexes before sort. Insertion sort used here for simplicity but real implementation should be replaced by a sorting algorithm with complexity O(nlogn)
for (int i = start; i <= end; i++) {
indexes[i] = i;
}
for (int i = start; i < middle; i++) {
for (int j = start; j < i; j++) {
if (buffer[i] < buffer[j]) {
swap(buffer[i], buffer[j]);
swap(indexes[i], index[j]);
}
}
}
for (int i = middle + 1; i <= end; i++) {
for (int j = middle + 1; j < i; j++) {
if (buffer[i] < buffer[j]) {
swap(buffer[i], buffer[j]);
swap(indexes[i], index[j]);
}
}
}
// 3. Get pairs from left and right side of middle whose sums add up to -data[middle]
int left = start;
int right = end;
int target = -data[middle];
while (left < middle && right > middle) {
int sum = buffer[left] + buffer[right];
if (sum == target) {
// Found a pair, output the sequence
print_subarray(data, indexes[left], indexes[right]);
left++;
right++;
} else if (sum < target) {
left++;
} else {
right--;
}
}
}
void find_subarray(int* data, int* indexes, int size) {
int* buffer = new int[size];
int* indexes = new int[size];
find_subarray_partial(data, buffer, 0, size - 1);
delete [] buffer;
delete [] indexes;
}
How is order N log N and if the given array contains all Zeros u must print N*(N-1)/2 intervals ?
You're right, the worst case complexity is O(N^2), and i made some mistakes in step 3. after finding a target.
I think this question can be solved by one pass traversal.
Use an additional array sum which sum[i] represents sum from data[0] to data[i].
If we find two elements in array sum that they have the same value, for example, sum[i] = sum[j]
then we can sure that the sum of continuous sequence data[i+1] to data[j] is zero.
Note that there maybe an exception. If any sum[i]`s value is zero, that means the sum of sequence from data[0] to data[i] is zero
For example
input is -1, -3, 4, 5, 4
sum is -1, -4, 0, 5,9
sum[2] is zero that means data[0] + data[1] + data[2] = 0
input is 1,3,5,7,9,-2,2
sum is 1 4 9 16 25 23 25
sum[4] = sum[6], that means data[5] + data[6] = 0
Time complexity is O(n)
Space complexity is O(n)
//Author : A.NAsimunni
//Cse student
#include<stdio.h>
main()
{
int n;
printf("\n\tEnter size of an array : ");
scanf("%d",&n);
int a[n];int i;
for(i=0;i<n;i++)
{
scanf("%d",&a[i]);
}
int j=0,s=0,m;
int t[n];int k=0;
for(i=0;i<n;i++)
{
s=0;
k=0;t[k]=a[i];s=s+a[i];k=k+1;
for(j=i+1;j<n;j++)
{
t[k]=a[j];k=k+1;
s=s+a[j];
if(s==0)
{printf("\n\t\tYour array : ");
for(m=0;m<k;m++){printf(" %d ",t[m]);}
}
else
{;}
}
}
printf("\n\n");
}
//Author : A.NAsimunni
//Cse student
#include<stdio.h>
main()
{
int n;
printf("\n\tEnter size of an array : ");
scanf("%d",&n);
int a[n];int i;
for(i=0;i<n;i++)
{
scanf("%d",&a[i]);
}
int j=0,s=0,m;
int t[n];int k=0;
for(i=0;i<n;i++)
{
s=0;
k=0;t[k]=a[i];s=s+a[i];k=k+1;
for(j=i+1;j<n;j++)
{
t[k]=a[j];k=k+1;
s=s+a[j];
if(s==0)
{printf("\n\t\tYour array : ");
for(m=0;m<k;m++){printf(" %d ",t[m]);}
}
else
{;}
}
}
printf("\n\t\tThank you\n");
}
Another approach by using maps. Assume we keep track of cumulative sum of array. If there is a subsequence starting from index n1 to n2 summing to zero, then the cumulative sum is equal at n1 and n2. Just need to remember the locations.
map<int, vector<int>> locs;
int cs = 0;
locs[0]=0;
for (int i = 0; i < N; i++)
{
cs += arr[i];
locs[cs].push_back(i);
}
/// now go over map to identify subsequence
for (auto it = locs.begin(); it != locs.end(); ++it)
{
List_sequences(it->second);
}
list_sequences
simply prints sub sequences based on starting indices. For instances, the cumulative sum meets value "2" at indices 4, 8, 120, the there are three sub sequences: 4-8, 8-120, 4-120.
Time : O(N + M)
Space: O(N)
M = Total number of subsequences
#include<iostream>
#include<algorithm>
using namespace std;
int main()
{
int n,i,a[10001];
cin>>n;
for(i=0;i<n;i++)cin>>a[i];
sort(a,a+n);
for(i=0;i<n;i++)
{
if(a[i]<=0)
{
int l=i+1,r=n-1,k=-a[i];
while(l<n && r<n && l<r)
{
if(a[l]+a[r]>k)
{
r--;
}
else if(a[l]+a[r]<k)
{
l++;
}
else
{
cout<<a[i]<<" "<<a[l]<<" "<<a[r]<<endl;
l++;
r--;
}
}
}
}
cin>>n;
}
#include<iostream>
#include<algorithm>
using namespace std;
int main()
{
int n,i,a[10001];
cin>>n;
for(i=0;i<n;i++)cin>>a[i];
sort(a,a+n);
for(i=0;i<n;i++)
{
if(a[i]<=0)
{
int l=i+1,r=n-1,k=-a[i];
while(l<n && r<n && l<r)
{
if(a[l]+a[r]>k)
{
r--;
}
else if(a[l]+a[r]<k)
{
l++;
}
else
{
cout<<a[i]<<" "<<a[l]<<" "<<a[r]<<endl;
l++;
r--;
}
}
}
}
cin>>n;
}
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
struct range{int x,y;};
struct xyz{int su,in;}s[100001];
bool c(const xyz &l,const xyz &r){if(l.su==r.su)return(l.in<r.in);return(l.su<r.su);}
vector<range> ra;
int main()
{
int n,a[100001],i,j;
cin>>n;
for(i=1;i<=n;i++)cin>>a[i];
for(i=1;i<=n;i++){s[i].su=s[i-1].su+a[i];s[i].in=i;}
//for(i=1;i<=n;i++)cout<<s[i].su<<" ";
sort(s+1,s+n+1,c);
//for(i=1;i<=n;i++)cout<<s[i].su<<" ";
cout<<endl;
for(i=1;i<=n;i++)
{
if(s[i].su==0)
{
ra.push_back((range){1,s[i].in});
}
j=i+1;
while(s[j].su==s[i].su && j<=n)
{
ra.push_back((range){s[i].in+1,s[j].in});
j++;
}
}
for(i=0;i<ra.size();i++)
{
for(j=ra[i].x;j<=ra[i].y;j++)
{
cout<<a[j]<<" ";
}
cout<<endl;
}
cin>>n;
}
Python Code:
startend = {}
def getZeroSubsFromIndex(array, startIndex):
sum = 0
for i in range(startIndex, len(array)):
sum += array[i]
if sum == 0:
if startIndex not in startend:
startend[startIndex] = [i]
else:
startend[startIndex].append(i)
def getAllZeroSubs(array):
for i in range(len(array)):
getZeroSubsFromIndex(array, i)
print startend
int countSubArray(int A[], int n)
{
map<int, int> accumCountMap;
accumCountMap[0] = 1;
int sum = 0;
for (int i = 0; i < n; i++)
{
sum += A[i];
if (accumCountMap.find(sum) == accumCountMap.end())
accumCountMap[sum] = 1;
else
accumCountMap[sum]++;
}
int cnt = 0;
for (auto iter = accumCountMap.begin(); iter != accumCountMap.end(); iter++)
{
int val = iter->second;
if (val > 1)
cnt += val * (val - 1) / 2;
}
return cnt;
}
public static List<List<Integer>> zeroSumSubsequence(final List<Integer> list) {
if (list.isEmpty()) {
return Collections.emptyList();
}
List<List<Integer>> result = new ArrayList<>();
final List<Integer> sum = new ArrayList<>(list);
sum.add(0, 0);
for (int i=1; i<sum.size(); ++i) {
sum.set(i, sum.get(i) + sum.get(i-1));
}
for (int i=0; i<sum.size() - 1; ++i) {
for (int j=i+1; j<sum.size(); ++j) {
if (sum.get(j) - sum.get(i) == 0) {
result.add(list.subList(i, j));
}
}
}
return result;
}
This can be done in one pass. Take a hash table(say h) with a key (0) and value (-1). Add one by one element (i is incerementing) from the array to sum (say sum) and also add the sum as key into the hashtable(h) with value as i (current counter). Before adding to hashtable(h),each time check, if a key already exists in the hashtable with the cumulative sum. If exists, means zero sum formed from h(sum)+1 to current pointer(i), so print them. if the sum not exist in h, simply add it (need to update h(sum) with current i, even it found, so that we can track next occurrence of that sum).
Here is the code:
void PrintCum_Sum(int[] a)
{
Hashtable h = new Hashtable();
h.add(0,-1) // adding key 0 with -1 value
int sum=0;
for (int I=0;i<a.length;a++)
{
sum+=a[i];
if (h[sum].exists())
{
Print ("Below elements form sum 0");
for(int j=h(sum)+1;j<=i; j++)
print(a[j];
}
h(sum) = i; // update with current pointer, to compare for next repetition
}
}
small corrections :(.
void PrintCum_Sum(int[] a)
{
Hashtable h = new Hashtable();
h.add(0,-1) // adding key 0 with -1 value
int sum=0;
for (int i=0;i<a.length;a++)
{
sum+=a[i];
if (h[sum].exists())
{
Print ("Below elements form sum 0");
for(int j=h(sum)+1;j<=i; j++)
print(a[j];
h[sum] = i; // update with current pointer, to compare for next repetition
}
else
{
h.add(sum,i); // add the sum, if not exist
}
}
}
public class Main {
public static final void main(String[] args) {
printSubsequence(new int[] {-1, -3, 4, 5, 4}, 0);
}
private static void printSubsequence(int[] array, int sumTotalToFind) {
final LinkedList<Integer> list = new LinkedList<Integer>();
for(int i = 0, arrLen = array.length; i < arrLen; i++) {
int sum = 0;
for(int j = i; j < arrLen; j++) {
list.add(array[j]);
sum += array[j];
if(sum == sumTotalToFind) {
System.out.println(list);
}
}
list.clear();
}
}
}
Folks.... this is the situation.
Subarray summing to K is the problem.
There are two distinct subcases:
1) If arrays elements are assumed to be nonnegative, then you can do a slick O(N) solution
2) If array elements can be negative too, you can't beat O(N^2) ... last time I tried I couldn't :P
static int[] input_array = {-1, -3, 4, 5, 7};
static int l=input_array.length;
static int total;
static int first;
public static void addThreeSub()
{
for (int i=0; i<l-2; i++)
{
first = input_array[i];
total = input_array[i]+input_array[i+1]+input_array[i+2];
//System.out.println("comparing " + first +" with:" + input_array[i+1]+ " & " +input_array[i+2]);
if (total==0)
{
System.out.println(first +" AND " + input_array[i+1]+ " AND " +input_array[i+2]);
}
}
}
My decision on python:
def find_cont(numbers):
length = len(numbers)
i = 0
while i < length:
def find_sum(numbers):
if not numbers:
return
sum = int(numbers[0])
values = [sum]
if sum == 0:
print values
for num in numbers[1:]:
sum += int(num)
values.append(num)
if sum == 0:
print values
find_sum(numbers[i+1:])
i += 1
My solution in JavaScript - not sure about the time complexity.
(function(){
window.subsetToZero = function(arr){
var i,
j,
k,
subsets = [],
sums = [];
for (i=0; i < arr.length; i++){
sums.push([0]);
for (j=0; j < sums.length; j++){
for (k=0; k <= i; k++){
sums[j][k] += arr[i];
if (sums[j][k] === 0){
subsets.push([j, i]);
}
}
}
}
return subsets;
}
})();
public static void printZero(int[] input)
{
int[] sum = new int[input.Length];
int currSum = 0;
for (int i = 0; i < input.Length; i++)
{
currSum += input[i];
sum[i] = currSum;
}
List<KeyValuePair<int, int>> storePairs = new List<KeyValuePair<int, int>>();
Hashtable map = new Hashtable();
for (int i = 0; i < input.Length; i++)
{
if (sum[i] == 0)
{
KeyValuePair<int,int> kvp = new KeyValuePair<int,int>(0, i);
storePairs.Add(kvp);
}
if (map.ContainsKey(sum[i]) == false)
{
map.Add(sum[i], i);
}
else
{
object key = (object)sum[i];
int startIndex = (int)map[key];
KeyValuePair<int, int> kvp = new KeyValuePair<int, int>(startIndex + 1, i);
storePairs.Add(kvp);
}
}
foreach(KeyValuePair<int,int> kvp in storePairs)
{
int startIndex = kvp.Key;
int endIndex = kvp.Value;
for (int j = startIndex; j <= endIndex; j++)
Console.Write(input[j] + " ");
Console.WriteLine();
}
}
static void Main(string[] args)
{
printZero(new int[] { -1, -2, 4, -1, 0, 4, 2, 3, -5 });
Console.Read();
}
Solution in one pass, without recursion and without additional array to store the sums.
import java.util.HashMap;
import java.util.HashSet;
public class SumZeroContinuousSequences {
public static void printSumZeroContSeq(int[] arr) {
HashMap<Integer, HashSet<Integer>> hmap = new HashMap<Integer, HashSet<Integer>>();
int currentSum = 0;
HashSet<Integer> hset = new HashSet<Integer>();
hset.add(-1);
hmap.put(0, hset);
for (int i = 0; i < arr.length; i++) {
currentSum += arr[i];
if(!hmap.containsKey(currentSum)) {
hset = new HashSet<Integer>();
hset.add(i);
hmap.put(currentSum, hset);
} else {
hset = hmap.get(currentSum);
for (Integer j : hset) {
printSeq(arr, j, i);
}
hset.add(i);
}
}
}
private static void printSeq(int[] arr, int j, int i) {
for (int k = j+1; k < i; k++) {
System.out.print(arr[k] + ", ");
}
System.out.println(arr[i]);
}
public static void main(String[] args) {
int[] arr = {-1, -3, 4, 5, 4, -4, -5};
printSumZeroContSeq(arr);
}
}
Two step process:
1. Figure out the aggregate sum
2. Find the repeated sums (indicating the numbers in between summed to 0).
def get_zero_sum_subsets_smart(integer_set):
integer_sum_set = [0 for x in xrange(0, len(integer_set) + 1)]
integer_map = {}
subsets = []
subset_lists = []
# calculate the cumilative sums
for i in xrange(0, len(integer_set)):
integer_sum_set[i + 1] = integer_sum_set[i] + integer_set[i]
# create a hash table for the sums and find duplicates
for i in xrange(0, len(integer_sum_set)):
sum = integer_sum_set[i]
if sum not in integer_map:
integer_map[sum] = [i]
else:
for start in integer_map[sum]: subsets.append((start, i))
integer_map[sum].append(i)
for start, end in subsets:
subset_lists.append(integer_set[start:end])
return subset_lists
print get_zero_sum_subsets_smart([-1, 1, -1, -3, 4, 5])
This is the classic subset sum problem, which is asked here many many many times before and is NP-complete problem. You can check out en.wikipedia.org/wiki/Subset_sum_problem for more info.
This is not a subset sum problem. It is a subsequence sum problem.
That said, elements should be continuous in the array whose sum is 0.
Mukesh: You should make that clear in the problem, since subsequence does not need the elements to be continuous in the array. [1, 2, 4] is a subsequence of [1, 2, 3, 4]
Miguel Oliveira : The problem statement has been updated. The continuous part was not mentioned before. It was only " subsequence "
@Up The original problem was subset sum and now they added "continuous" part! I've seen this a lot of times, where people keep changing the problem statement after posting.
So, if we are talking about "continuous subsequences", then we just need to traverse the array once, add a[i], a[i+1], a[i+2], and print a[i], a[i+1], a[i+2] whenever the sum is 0, right? Am I missing something here?
static int[] input_array = {-1, -3, 4, 5, 7};
static int l=input_array.length;
static int total;
static int first;
public static void addThreeSub()
{
for (int i=0; i<l-2; i++)
{
first = input_array[i];
total = input_array[i]+input_array[i+1]+input_array[i+2];
//System.out.println("comparing " + first +" with:" + input_array[i+1]+ " & " +input_array[i+2]);
if (total==0)
{
System.out.println(first +" AND " + input_array[i+1]+ " AND " +input_array[i+2]);
}
}
}
There is another solution that works as following:
- joe kidd August 14, 2013Array = [6, -1, -3, 4, 5, 4, -15, 7] then create another array that for position i - keeps the sum of all elements from [0, i] so that we get something like
SumArray = [6, 5, 2, 6, 11, 15, 0, 7]
Now by looking in the SumArray we can see that:
1) when 0 appears at i-position it means that from the begining of the array till i-th position we have a "zero sequence".
2) if there is a matching (two the same elements, like 6, 6 in our case) then we know that from [i+1,j], where i is the first and j is the second matching, the overall change was equall to zero, so we have a "zero sequence" again.