## Facebook Interview Question for SDE1s

Country: United States

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

We could use a hash to remember the sums of the elements we visited so far:

void findTriplet(std::vector<int>& numbers)
{
std::sort(numbers.begin(), numbers.end()); // O(NlogN)
std::unordered_map<int, std::pair<int, int>> Sums; // Keep track of the sums we visited so far
for(size_t i = 0; i < numbers.size(); ++i) {
if(Sums.count(numbers[i])) {
// We already found a pair that matches this sum
std::cout << numbers[i] << "=" << Sums[numbers[i]].first << "+" << Sums[numbers[i]].second << std::endl;
break;
} else {
for(size_t j = 0; j < i; ++j) {
Sums[numbers[j] + numbers[i]] = { numbers[i], numbers[j] };
}
}
}
}

EDIT: updated the solution to support cases such as [7,4,3]

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

@PenChief,
Does your solution work with an input say [7, 3, 4]?
i = 0, map doesn't have 7, move on,
i = 1, map doesn't have 3, j = 0, add 10 to map.
i = 2, map doesn't have 4, j = 0, add 11 to map, j = 1, add 7 to map.
terminate.
doesn't seem to return any result.

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

You can first sort the array. There goes O(nlogn). Then have nested for() loop and use
binary search to find the element = sum of first two. Put early exits when sum is > last
element.

int
bin_search (int a[], int s, int e, int v)
{
int m;
while (s<e) {
m = s + (e-s)/2;
if (a[m] == v) {
return m;
} else if (a[m] > v) {
e = m-1;
} else {
s = m+1;
}
}
return -1;
}

void
find_triplet (int a[], int n)
{
int i, j, k;

// Sort array first - O(nlogn)

for (i=0; i<n-2; i++) {
if ((a[i] + a[i+1]) > a[n-1]) break;
for (j=i+1; j<n-1; j++) {
if (a[n-1] < (a[i] + a[j])) break;
k = bin_search(a, j+1, n-1, a[i] + a[j]);
if (k != -1) {
printf("Found the triplet %d + %d = %d\n", a[i], a[j], a[k]);
}
}
}
}

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

There must be a better solution, but it seems I cannot do better than O(n^2)

A = [1, 2, 4, 9, 10]
B = {}
for(int i = 0; i < A.len; i++) {
for(int j = i+1; j < A.len; j++) {
}
}
intersection(set(A), B)

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

@Thangaprabhu you don't have the "key", you need to find it as well

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

@Alex, the question is to find a, b and c which satisfies the condition : a+b=c
your solution assumes they are part of the input.

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

Is it possible to solve this in less than O(n^2) time?

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

@PenChief. Thank you! I just didn't understand the task :) Updated solution:

void FindTriplet(vector<int> &array)
{
sort(array.begin(), array.end());
unordered_map<int, int> counts;
for (int n : array) {
++counts[n];
}
for (int i = 0; i < array.size(); ++i) {
int c = array[i];
int half = c >> 1;
for (int j = i - 1; j >= 0 && array[j] <= half; --j) {
int a = array[j];
int b = c - a;
if (counts[b] >= (a == half) ? 2 : 1) {
cout << a << " + " << b << " = " << c << "\n";
return;
}
}
}
}

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

public static boolean checkSumInArray(int[] arr){
int n=arr.length;
if(n<2){
return false;
}
for(int k=1;k<n;k++){
for(int i=0; i<=k-1;i++){
for(int j=i+1;j<=k;j++){
if(arr[i]+arr[j]==arr[k]){
return true;
}
}
}

}
return false;
}

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

public static boolean checkSumInArray(int[] arr){
int n=arr.length;
if(n<2){
return false;
}
for(int k=1;k<n;k++){
for(int i=0; i<=k-1;i++){
for(int j=i+1;j<=k;j++){
if(arr[i]+arr[j]==arr[k]){
return true;
}
}
}

}
return false;
}

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

@PenChief,
Does your solution work with an input for example [7, 3, 4]?

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

O(N^2) time, no additional space.
less than O(N^2) time it is not possible to solve the problem.

public boolean mainFunction(int[] arr) {

if (arr.length < 2)
return false;

Arrays.sort(arr);

Tuple inds = new Tuple(0, 1);
int sumInd = 0;

while (inds != null) {
int sum = arr[inds.x] + arr[inds.y];
sumInd = findSumNextInd(arr, sum, sumInd);
if (sum == arr[sumInd]) {
return true;
} else if (sumInd == arr.length - 1) {
return false;
}
inds = getNextLowestSumInds(arr, inds);
}
return false;
}

// always keep x < y
public Tuple getNextLowestSumInds(int[] arr, Tuple currIndices) {

// invalid input
if (arr == null || currIndices == null)
return null;

int currX = currIndices.x;
int currY = currIndices.y;

// invalid input
if (currX >= currY)
return null;

// nothing to search
if (currX >= arr.length - 2 && currY >= arr.length - 1) {
return null;
}

int newX, newY;
if (currX + 1 == currY) {
return new Tuple(currX, currY+1);

} else {
if (currY == arr.length - 1) {
return new Tuple(currX+1, currX+2);
} else {
// 2 options:
// 1. (currX, currY+1) or (currX+1, currY)
int sum1 = arr[currX] + arr[currY+1];
int sum2 = arr[currX+1] + arr[currY];

if (sum1 > sum2) {
return new Tuple(currX, currY+1);
} else {
return new Tuple(currX+1, currY);
}
}
}
}

public int findSumNextInd(int[] arr, int sum, int startIndex) {
int ind = startIndex;

if (arr[ind] >= sum) return ind;

while (ind < arr.length - 1 && arr[ind+1] <= sum) {
ind++;
}
return ind;
}

public static class Tuple {
public int x;
public int y;

public Tuple(int x, int y) {
this.x = x;
this.y = y;
}
}

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

javascript
var arr = [1,2,4,6,9];
arr.some ( function ( val, ind ) {
if ( typeof ( ind + 2 ) !== 'undefined' ) {
return ( val + b[ind + 1] === b[ind + 2] )
}

});

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

javascript

var arr = [1,2,4,6,9];
arr.some(function(val, ind){
if(typeof (ind + 2) !== 'undefined'){
return (val + b[ind + 1] === b[ind + 2])
}

})

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

I don't think we can do better then O(N^2).
First sort the array, and iterate c from len(arr)-1 to 2. Look for a and b with starting idx as 0, and b-1.

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

xzc

Comment hidden because of low score. Click to expand.
-1
of 1 vote

public static boolean findSum(Integer a[], Integer key) {
Set<Integer> set = new HashSet<>();
for(int i=0; i<a.length; i++) {
if(set.contains(key-a[i])) {
return true;
} else {
}
}
return false;
}

Comment hidden because of low score. Click to expand.
0

Understand the question properly first.

Comment hidden because of low score. Click to expand.
-1
of 1 vote

O(N) time, O(N) space.

bool TripletExists(vector<int> const &array, int a, int b, int c)
{
unordered_map<int, int> seen;
int needed_ab_count = (a == b) ? 2 : 1;
int needed_c_count = 1;
if (a == b && b == c) {
needed_ab_count = needed_c_count = 3;
}
for (int n : array) {
++seen[n];
if (n == a ||
n == b)
{
if (seen[c - n] >= needed_ab_count &&
seen[c] >= needed_c_count)
{
return true;
}
}
if (n == c) {
if (seen[a] >= needed_ab_count &&
seen[b] >= needed_ab_count)
{
return true;
}
}
}
return false;
}

Comment hidden because of low score. Click to expand.
-1
of 1 vote

<?php

function getVariants(\$arr, \$path = [], &\$list = []) {
if (empty(\$arr)) return \$list;

if (count(\$path) == 3) {
if (\$path[0] < \$path[1] && \$path[1] < \$path[2]) {
if (!isset( \$list[implode('+', \$path)] )) {
\$list[implode('+', \$path)] = \$path;
}
}
return \$list;
}

foreach (\$arr as \$num) {
if (!in_array(\$num, \$path)) {
getVariants(\$arr, array_merge(\$path, [\$num]), \$list);
}
}

return \$list;
}

// check that the array has a + b = c
function checkABC(\$arr) {
\$path = [];
\$list = [];
\$variants = getVariants(\$arr, \$path, \$list);
foreach (\$variants as \$vKey => \$variant) {
if (\$variant[0] + \$variant[1] == \$variant[2]) {
echo "the case is ", \$vKey, "\n";
return true;
}
}
}

\$arr = [1, 15, 6, 2, 9, 12];
checkABC(\$arr);

Comment hidden because of low score. Click to expand.
-2
of 4 vote

public static boolean findSum(Integer a[], Integer key) {
Set<Integer> set = new HashSet<>();
for(int i=0; i<a.length; i++) {
if(set.contains(key-a[i])) {
return true;
} else {
}
}
return false;
}

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.

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