Facebook Interview Question Software Developers
Team: Infrastructure
Country: United States
Interview Type: In-Person
@funk, solution which I proposed using set would take O(n) space, but I can improve it to O(1) by using sorting.
Basically Idea goes like this,
1. sort the array
2. for each position i upto n-2:
left = position next to i
right = last position i.e. n-1;
while(left<right)
if(input[i] + input[left] + input[right] < X)
left++;
else if (input[i] + input[left] + input[right] > X)
right--;
else
return true;
3. If no triplet found then return false
Solution:
- Two reasonable easy solution exists with O(n^2). One using extra space
and the other doesn't.
- Input is an array arr of length n
- Sum to reach is x
1. Solution with hash table: O(n^2) time, O(n) space
- arr[a] + arr[b] + arr[c] = sum, where 0 <= a < b < c < n
- hash table val_idx contains the all the values of arr
with the last index they occured
- Find all combinations for a and b and check if sum-arr[a]-arr[b]
is in the HT with an index of last occurence > b
2. Solution with sort: O(n^2) time, O(1) space:
- sort the array, now arr[a] <= arr[b] <= arr[c] if 0 <= a < b < c
- pick a in order, so range [a+1..n) contains c and b
- search in (sorted) [a+1..n) for y = sum - arr[a]:
(well known sum of two in sorted array question)
start with b = a+1 and c = n-1
while b < c:
# if the smallest and largest are to big,
# the largest has no space
if arr[b] + arr[c] > y: c -= 1
# if smallest and largest are too small,
# no combination with the smallest will
# work out
elif arr[b] + arr[c] < y: B += 1
else: found 3-sum
notice that some work is still done multiple times.
So it seems further optimization is possible - but not trivial.
python 3
def sum_of_three_ht(arr, x):
val_idx = {}
for a, va in enumerate(arr):
val_idx[va] = a
for a, va in enumerate(arr):
for b in range(a + 1, len(arr)):
c = val_idx.get(x - va - arr[b])
if c is not None and c > b:
return (True, (x, va, arr[b], arr[c]))
return (False, (x, None, None, None))
def sum_of_three_sort(arr, x):
n = len(arr)
arr.sort()
for a, va in enumerate(arr):
b = a + 1
c = n - 1
y = x - va
while b < c:
vbc = arr[b] + arr[c]
if vbc < y:
b += 1
elif vbc > y:
c -= 1
else:
return (True, (x, va, arr[b], arr[c]))
return (False, (x, None, None, None))
This question can be solved easily by interpreting it in different way as follows:-
Given two integer a,b can you find another integer c from an array such that their sum is equal to value 'X'.
So my solution goes like this, I will use an HashSet to store X-(a+b) for pair (a,b) since it has O(1) lookup and whenever new Integer is encountered, if it exist in HashSet, then we are done.
static boolean isTripletExist ( int[] input, int X ) {
int n = input.length;
if(n<3)
return false;
HashSet<Integer> set = new HashSet<Integer>();
for(int i=0; i<n i++) {
if(set.contains(input[i])
return true;
for(int j=i+1; j<n; j++) {
set.add(X-(input[i]+input[j]));
}
}
return false;
}
Time Complexity: O(n^2) where n is the size of input array
Space Complexity: O(n) due to HashSet
This question can be solved easily by considering the problem statement in the following manner:-
Given 2 integer a and b, can you find another integer c in an array such that a+b+c = X
So my solution goes like this, I will store X-(a+b) for each pair a,b in an array, and whenever new encountered integer exist in our store, we are done. For storing value, I will you HashSet as it has O(1) lookup.
static boolean isTripletExist( int[] input, int X){
int n = input.length;
if(n<=2)
return false;
HashSet<Integer> set = new HashSet<Integer>();
for(int i=0; i<n; i++) {
if(set.contains(a[i]))
return true;
for(int j=i+1; j<n; j++) {
set.add(X-(input[i]+input[j]));
}
}
return false;
}
Time Complexity: - O(n^2) where n is size of input array
Space Complexity :- O(n) due to HashSet
@ChrisK, Thanks for pointing this out.
So Now I need to consider it in other way, Like for every element, I will find a pair such that sum of triplet will be X.
UPDATED SOLUTION :
static boolean isTripletExist( int[] input, int X){
int n = input.length;
if(n<=2)
return false;
for(int i=0; i<n-1; i++) {
HashSet<Integer> set = new HashSet<Integer>();
for(int j=i+1; j<n; j++) {
if(set.contains(X-input[i]-input[j]))
return true;
else
set.add(input[j]);
}
}
return false;
}
@sagartiwari230 yea, that's the one. That's the solution the interviewer wanted me to reach.
When I look at that solution now I think there should be a way in which at the first step when you're sorting the array, you can also look for the three numbers at the same time that you sort, it would duplicate the number of comparisons during the sort process, but chances are you will find the answer during the sort process and if not then you can continue with steps 2 and 3 that you wrote. Thoughts?
My solution will not let you to have duplicates:
private HashMap<Integer, Integer> cache = new HashMap<>();
public boolean isTripletExist(int sum, List<Integer> a) {
int n = a.size();
Collections.sort(a);
if (a.isEmpty()) {
return false;
}
putIntoCache(a.get(0));
for (int i = 0; i < n; i++) {
int a1 = a.get(i);
for (int j = i + 1; j < n; j++) {
int a2 = a.get(j);
int s = sum - (a1 + a2);
if (cache.containsKey(s)) {
if (s == a1 || s == a2) {
if (cache.get(s) > 1) {
return true;
}
} else {
return true;
}
}
putIntoCache(a2);
}
}
return false;
}
private void putIntoCache(int key) {
int newVal = (cache.containsKey(key) ? cache.get(key) + 1 : 1);
cache.put(key, newVal);
}
JS solution:
function checkIfItPosible(arr, num){
posible = false;
for(fnum in arr){ ///// FIRST LOOP START
if(posible ==true) break;
var firstNum = arr[fnum];
for (snum in arr) { ///// SECOND LOOP START
if(posible ==true || snum == fnum ) break;
var secondNum = arr[snum];
for(tnum in arr){ ///// THIRD LOOP START
if(posible ==true || (snum == tnum )) break;
var thirdNum = arr[tnum];
if(firstNum + secondNum + thirdNum == num){
console.log(firstNum +" + "+ secondNum +" + "+ thirdNum +" = "+num);
posible = true;
}
} ///// THIRD LOOP ENDS
} ///// SECOND LOOP ENDS
}; ///// FIRST LOOP ENDS
return posible;
}
var givenArray = [10, 3, 30, 5, 19, 1];
var sumToAchieve = 9;
var isItPosible = checkIfItPosible(givenArray, sumToAchieve);
console.log(isItPosible); // true > 1 + 5 + 3 = 9
JS solution:
function checkIfItPosible(arr, num){
posible = false;
for(fnum in arr){ ///// FIRST LOOP START
var firstNum = arr[fnum];
for (snum in arr) { ///// SECOND LOOP START
if(snum == fnum ){break;};
var secondNum = arr[snum];
for(tnum in arr){ ///// THIRD LOOP START
if(snum == tnum){break;};
var thirdNum = arr[tnum];
if(firstNum + secondNum + thirdNum == num){
posible = true;
return posible;
}
} ///// THIRD LOOP ENDS
} ///// SECOND LOOP ENDS
}; ///// FIRST LOOP ENDS
return posible;
}
var givenArray = [1,200,3,1300,100, 5];
var sumToAchieve = 9;
var isItPosible = checkIfItPosible(givenArray, sumToAchieve);
console.log(isItPosible); // true > 1 + 5 + 3 = 9
This is the 3-Sum problem. And do not make any fun on the name. Please don't.
- NoOne July 05, 2017[ en.wikipedia.org/wiki/3SUM ]
That should answer it. The problem, if there is a solution is less than Theta(n^2) is non trivial.