Facebook Interview Question for Software Engineer Interns


Country: United States
Interview Type: Phone Interview




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

Another easy to understand solution:

We 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).

- myth January 10, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

This is the correct answer... I totally blanked during the interview and feel so dumb...

- fatenuller January 11, 2015 | Flag
Comment hidden because of low score. Click to expand.
1
of 3 votes

Probably better to use HashSet for that storing all numbers.

- Anonymous January 11, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Yeah I used a HashSet since the sums themselves were the keys.

- fatenuller January 11, 2015 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

@myth: what about repetitions?

- Resh January 12, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- akyker20 January 16, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

It can be solved in n log n, I outlined how, take a look.

- CT January 16, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@CT, n log n is generally slower than solving in n.

- Mike March 18, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@CT, n log n is generally slower than solving in n.

- Mike March 18, 2015 | Flag
Comment hidden because of low score. Click to expand.
3
of 3 vote

public boolean threeSum(int[] a){
		
		HashSet<Integer> set = new HashSet<Integer>();
		for(int c:a){
			set.add(c);
		}
		for(int i:a){
			for(int j:a){
				if(set.contains(-i-j))
					return true;
			}
		}
		
		return false;
	}

- Reese.Marlin January 13, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
2
of 4 vote

Sort an array.

Then for each element a[i] and remained array a[i + 1:] solve two sum problem with sum equal to -a[i]

- glebstepanov1992 January 10, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

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;
	}

- Resh January 12, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 2 vote

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;
}

- indianspartan January 10, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Good and easy to understand code, will work without extra memory.

- myth January 10, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

this solution will not work if repletion is allowed . ex: as provided in the problem,
{10,-2,1}

- rahul.singh4899 April 20, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;

}

- Nelson Perez January 11, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

repetitions are allowed????

- Anonymous January 11, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#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;
}

- Nick January 13, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
    }

- cdog January 15, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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);
    }
}

- akyker20 January 16, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

- CT January 16, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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 January 17, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@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 January 18, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- ko January 22, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

n log n is slower than n anyway

- Anonymous March 18, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

n log n is slower than n anyway

- Anonymous March 18, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
	}

- manuel April 13, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}

- hankm2004 August 17, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;

}

- Long November 12, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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);
            
           }


      }
    }

    
  }

- MDeVogel May 06, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

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;
}

- autoboli January 10, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- myth January 10, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Thank you myth, you were right. I have fixed it, it led to even simpler code :)

- autoboli January 10, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

what was the change, not sure why u were checking j==k or i==k

- rahul.singh4899 April 20, 2015 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

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;

}

- zhangruichang January 10, 2015 | Flag Reply


Add a Comment
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.

Learn More

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.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More