Facebook Interview Question
Software Engineer InternsCountry: United States
Interview Type: Phone Interview
This is the correct answer... I totally blanked during the interview and feel so dumb...
Thats good for looking at a sum composed of 3 numbers, but what are you going to do when (as expected) the interviewer turns around and says change your solution to find a sum of zero composed of n numbers. My recursive function below is definitely slower than yours, but it could be easily modified to check for a sum of zero for n numbers.
public static boolean threeNumberSum(int[] arr){
HashSet<Integer> hashmap = new HashSet<Integer>(); //complexity is O(n) and O(n) for storing
for(int i:arr){
hashmap.add(i);
}
//complexity is O(n^2)
for(int a = 0;a<arr.length;a++){
for(int b=a;b<arr.length;b++){
int c = arr[a]+arr[b];
if(hashmap.contains(-c)){
return true;
}
}
}
return false;
}
bool sum3 ( vector<int> &arr) {
sort(arr.begin(), arr.end() );
cout << "New vector : ";
copy ( arr.begin(), arr.end(), ostream_iterator<int>(cout, " "));
cout << endl;
// for element c[0,n) search if a+b exists in the array
for(int i=0; i<arr.size(); ++i) {
int c = -arr[i];
int left=0, right=arr.size()-1;
while( left <= right ) {
int sum = arr[left] + arr[right];
if ( sum == c && ! (i == left || i == right) )
return true;
if ( sum > c )
right--;
else
left++;
}
}
return false;
}
Seems that everyone has a O(n^3) solution except for one written but you can do it O(n^2) using a HashTable/HashSet/HashMap as the last number you just need to look up.
public static bool FindSum10Combo(int[] A)
{
// This takes O(n) to populate.
HashSet<int> map = new HashSet<int>(A);
for(int i = 0; i < A.Length-2; i++)
for(int j = i + 1; j < A.Length-1; j++)
{
int missing = 10 - (A[i] + A[j]);
if(map.Contains(missing))
{
return true;
}
}
return false;
}
#include <unordered_set>
using namespace std;
bool threesum(int in[], int len)
{
unordered_set<int> set;
for (int i = 0; i < len; ++i)
{
set.insert(in[i]);
}
for (int i = 0; i < len; ++i)
{
for (int j = 0; j < len; ++j)
{
if (set.find(-(in[i] + in[j])) != set.end())
{
return true;
}
}
}
return false;
}
Simple problem is a+b+c=0 <=> a+b=-c. We just generate all possible pairs a+b=-c and then check if -c is in the set of numbers.
Allowing repetitions introduces two special cases:
1. The only case where we could repeat a single number is 0+0+0=0, so just check if the sequence contains 0
2. We need to also allow pairs a+b where a==b (same index)
static boolean threeSum(int[] A) {
HashSet<Integer> numbers = new HashSet<>();
for (Integer num : A) numbers.add(num); // allow checking if a number is in A in O(1)
if (numbers.contains(0)) return true; // only case with 3 repetitions 0+0+0
int n = A.length;
for (int i=0; i<n; i++) // all pairs (A[i],A[j]) with i<=j -> O(n^2)
for (int j=i; j<n; j++) // allow for repetitions i==j <=> A[i]=A[j]
if (numbers.contains(-A[i]-A[j])) // A[i]+A[j]+A[k]=0 <=> there exists A[k]=-A[i]-A[j]
return true;
return false;
}
Here is, in my opinion, a fairly elegant solution. Obviously, its slower than some messy iterative function. The advantage of this function however is that it could be easily modified to check for a sum of zero composed with n numbers (instead of 3).
import java.util.Arrays;
public class Algorithm {
public boolean threeNumbersAddUpToZero(int[] input) {
return recursiveHelper(0, 0, input);
}
private boolean recursiveHelper(int sum, int numNumbers, int[] input) {
if(numNumbers == 3) return sum == 0;
if(input.length == 0) return false;
int[] subarray = Arrays.copyOfRange(input, 1, input.length);
return recursiveHelper(sum+input[0], numNumbers+1, subarray) ||
recursiveHelper(sum, numNumbers, subarray);
}
}
n log n solution:
Separate negatives from positive and if encountered 0, return true because of tripple 0. Sort postive and negative by absolute value. This is most time consuming step - n log n.
From now on, treat all numbers by absolute value and lets consider them as two sorted arrays.
Take the last element of first array and attempt to find two elements on the second array with the sum equal to that element. It is well know how to do that, peek up two elements from both end and walk down higher one if sum is bigger, walk up smaller one if sum is smaller. You can meet at the same index, in which case take the double. If cannot find pair this way move down to the next in the first array but you can continue in the second array where you left off (with minor adjustment).
Repeat same logic for these two arrays, but swap in which one we select one element and in which two.
How it can be n log n solution?
the first step, sorting two array takes
n - creating two arrays
n log n/2 for sorting two arrays
then finding sum of two elements in an array = an element in another array takes (n^2)/2
so it takes (n^2)/2 + (n log n/2)
@anderson, the idea is that when you look for next pair, you don't have to start again from two ends, but adjust last two indexes based on the difference. I will provide more details soon.
@CT : Yes we are not looking back, but we are not jumping to next element by iterating to next. So for each element, we are keeping two indexes, which in the worst case needs to be moved by (n-1)/2 times, which makes the order for all elements to be n^2.
In Java:
public static boolean checkZero(Integer[] array) {
Arrays.sort(array);
if (array[array.length - 1] <= 0
|| array[0] >= 0) {
//Only positive or negatives values
return false;
}
int positiveValuesStart = 0;
for (int i = 0; i < array.length; i++) {
if (array[i] >= 0) {
positiveValuesStart = i;
}
}
List<Integer> list = Arrays.asList(array);
List<Integer> negativeList = list.subList(0, positiveValuesStart);
List<Integer> positiveList = list.subList(positiveValuesStart, list.size());
for(int i = 0; i < negativeList.size(); i++) {
for (int j = 0; j < negativeList.size(); j++) {
int positiveValue = Math.abs(negativeList.get(i) + negativeList.get(j));
if (positiveList.contains(positiveValue)) {
return true;
}
}
}
return false;
}
Here is O(N^2) alogrithm. (assuming the hashtable gives O(1) lookup time).
In the current implementation, it would be O(N^2*logN).
#include <unordered_map>
#include <iostream>
using namespace std;
bool dfs(int* input, int left, int len, int depth, unordered_map<int, int>& map)
{
if (depth == 2)
return (map.find(-1*left) != map.end());
for (int i = 0; i < len; i++)
{
left += input[i];
if (dfs(input, left, len, depth+1, map))
return true;
left -= input[i];
}
return false;
}
bool find_zero_sum(int * input, int len)
{
unordered_map<int, int> hashtable;
for ( int i = 0; i <len; i++){
if (hashtable.find(input[i]) == hashtable.end())
hashtable[input[i]] = input[i];
}
int left = 0;
bool found = false;
for (int i = 0; i <len; i++)
{
left += input[i];
if ((found = dfs(input, left, len, 1, hashtable)))
return found;
left -= input[i];
}
return found;
}
public static boolean solve(int[] a) {
if (a.length < 3) {
return false;
}
Arrays.sort(a);
int rightIndex = -1;
for (int i = 0; i < a.length; i++) {
if (a[i] > 0) {
rightIndex = i;
break;
}
}
int leftIndex = rightIndex - 1;
if (rightIndex == -1 || leftIndex == -1) {
return false;
}
while (leftIndex >= 0 && rightIndex < a.length) {
int leftValue = -a[leftIndex];
int rightValue = a[rightIndex];
if (leftValue < rightValue) {
int ll = leftValue + leftValue;
if (ll == rightValue) {
return true;
} else if (ll > rightValue) {
leftIndex--;
} else {
for (int i = leftIndex - 1; i >= 0; i--) {
int currValue = leftValue - a[i];
if (currValue == rightValue) {
return true;
} else if (currValue > rightValue) {
break;
}
}
leftIndex--;
}
} else {
int rr = rightValue + rightValue;
if (rr == leftValue) {
return true;
} else if (rr > leftValue) {
rightIndex++;
} else {
for (int i = rightIndex + 1; i < a.length; i++) {
int currValue = rightValue + a[i];
if (currValue == leftValue) {
return true;
} else if (currValue > leftValue) {
break;
}
}
rightIndex++;
}
}
}
return false;
}
static int[] arr = {8,-3,8,8,-5,8,8};
static int req = 0;
public static void main(String[] args) {
// O(N^2)
for(int i = 0; i < arr.length; i++)
{
// new find
int find = req - arr[i];
// combine 2 numbers
HashSet<Integer> set = new HashSet<Integer>();
for(int j = 0; j < arr.length; j++)
{
if(i != j)
{
int cur = arr[j];
if(set.contains(find - cur))
{
System.out.println(cur + " " + (find - cur) + " " + arr[i]);
return; // remove if you need multiple answers;
}
set.add(cur);
}
}
}
}
First, sort the array in ascending order. Second, for each element k in the array do the following:
1) Set index 'i' to 0, 'j' to N-1
2) Compute the sum of three, if the sum equals zero return true, otherwise:
a) If the sum is greater than zero you want to decrease the sum, this can be achieved only by decrementing 'j'
b) If the sum is less than zero increment 'i'
Sorting is O(N log N), the scanning is O(N^2), hence the complexity is O(N^2).
A sample code is shown below:
public boolean sumsToZero(int[] a) {
int N = a.length;
Arrays.sort(a);
for (int k=0; k<N; k++) {
int i = 0; j = N-1;
while (i < j) {
int sum = a[k]+a[i]+a[j];
if (sum > 0 || j == k) j--;
else if (sum < 0 || i == k) i++;
else return true;
}
}
return false;
}
One point which i want to raise in this solution is that you are considering repetition. As i = 0, j = N-1 and k can be 0 and N-1. We can have a[0] + a[N-1] + a[k=0] as 0 which will give us i = 0, j = N-1 and k = 0 which will be a incorrect answer. You have mentioned if condition check for equality in the end which will fail as we will get sum 0 in start.
Otherwise approach seems good to me as it is without extra space.
bool ThreeSum_hash(vector<int>& num)
{
int n=num.size();
unordered_set<int> hash;
for(int i=0;i<n;i++) for(int j=0;j<n;j++) hash.insert(num[i]+num[j]);
for(int i=0;i<n;i++)
{
auto it=hash.find(-num[i]);
if(it!=hash.end()) return 1;
}
return 0;
}
bool ThreeSum_Loop(vector<int>& num)
{
sort(num.begin(), num.end());
int n=num.size();
for(int i=0;i<n;i++)
{
for(int j=i,k=n-1;j<=k;)
{
int cursum=num[i]+num[j]+num[k];
if(cursum>0) k--;
else if(cursum<0) j++;
else return 1;
}
}
return 0;
}
Another easy to understand solution:
- myth January 10, 2015We can see this problem as find pair of elements having a + b = -c. If we can find one pair satisfying this condition, we can say there are three elements having a + b + c = 0;
To solve this problem, we can use hashmap.
Step 1: Store all numbers in a HashMap O(n) time complexity and O(n) space.
Step 2: traverse through our original array and for each element a[i], find (-c - a[i]) element in hashmap which will be done in O(1) time. Total time in this step is O(n) as we need to do this for complete array.
We need to consider c as each and every element so that we can find pairs, so we need to make a loop for c starting from a[0] to a[size-1], which will take O(n) time. We need to skip cth place when running above steps so that we get all numbers seperate.
Total complexity is O(n^2) and space is O(n).