Facebook Interview Question
SDE1sCountry: United States
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]);
}
}
}
}
@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;
}
}
}
}
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;
}
}
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 {
set.add(a[i]);
}
}
return false;
}
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;
}
<?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);
We could use a hash to remember the sums of the elements we visited so far:
EDIT: updated the solution to support cases such as [7,4,3]
- PenChief October 02, 2017