## Google Interview Question

Software Engineers**Country:**United States

**Interview Type:**In-Person

1) For sorting, use extenal sorting

2) For finding touples, use modified solution of the problem:

Given an array A[] and a number x, check for pair in A[] with sum as x - ( Fro GeeksforGeeks)

Where it is not a single array but two arrays. The arrays contain partial data one from the begninig and one from the end of the data. Say for example we have the data as follows

1 3 4 5 6 7 8 9 10 11 14 16 ........

....................................

....................................

99999999994 100000000000

And supposed we want sum of 100000000001 and we can read only four elements. We read first two elements A0 = [1,3] and A1 = [99999999994, 100000000000] into the memory.

intialize l = 0 and r = 1

A0[0] + A1[1] = 1+100000000000 = 100000000001, a hit and do l++, r--

A0[1] + A1[0] = 3 + 99999999994 = 99999999999, a miss and 99999999999<100000000001 so increament l++

But l crossed A0 boundary. So read next check form the begining [4,5] and set l=0

Repeat this till we left with only array

If we left with A0 then set r as length(A0)-1 in this case 1. If we left with A1 then set l as 0. Then use the logic l<r

I wanted to make function that find any triplet that sum-up is same as given amount... code does not seem to be quite optimized but it works.

```
def threesum(nums, amount):
temp=[]
distance=0
d={}
for i in range(len(nums)):
left = nums[:i]
right = nums[i+1:]
current = nums[i]
rest = left+right
ret = twocombo(rest)
for c in ret:
a = sorted([current]+c)
if a not in temp and sum(a) == amount:
temp.append(a)
return temp
def twocombo(rest):
temp = []
for i in range(len(rest)):
for j in range(i, len(rest)):
if i != j:
a = sorted([rest[i]]+[rest[j]])
if not a in temp:
temp.append(a)
return temp
arr=[-1, 0, 1, 2, -1, -4]
amount = 0
print(threesum(arr, amount))
```

Assuming the integers are positive, and that we only need unique triplets. Some de-duping is done in the code, but de-duping on the whole triplet should be done to get really unique triplets.

```
#include <unordered_set>
#include <unordered_map>
#include <vector>
#include <iostream>
using namespace std;
void Triplets(const vector<uint32_t>& a, uint32_t sum_needed)
{
unordered_set<uint32_t> sums_of_1;
unordered_map<uint32_t, unordered_set<uint64_t>> sums_of_2;
for (uint32_t n : a)
{
if (n <= sum_needed)
{
auto it = sums_of_2.find(sum_needed - n);
if (it != sums_of_2.end())
{
const unordered_set<uint64_t>& s = it->second;
for (uint64_t key : s)
{
uint32_t n1 = key >> 32;
uint32_t n2 = key;
cout << n1 << ", " << n2 << ", " << n << "\n";
}
}
for (uint32_t n1 : sums_of_1)
{
uint32_t sum_of_2 = n1 + n;
if (sum_of_2 <= sum_needed)
{
uint64_t key = n1 < n
? (static_cast<uint64_t>(n1) << 32) | n
: (static_cast<uint64_t>(n) << 32) | n1;
sums_of_2[sum_of_2].insert(key);
}
}
sums_of_1.insert(n);
}
}
}
int main()
{
Triplets({7, 2, 8, 5, 9, 1, 3}, 15);
return 0;
}
```

```
public static void main(String[] args) {
int[] arr = {1, 2, 3, 4, 5, 6, 7, 8, 1, 2, 3, 4, 5, 6};
int sum = 22;
boolean isTripletAvailable = findPossibleTriplets(arr, sum);
System.out.println("Triplet is " + (isTripletAvailable ? "available." : "not available."));
}
private static boolean findPossibleTriplets(int[] arr, int sum) {
int size = arr.length - 1;
Set<Integer> set = new HashSet<Integer>();
for(int i=0; i<size-2;i++) {
set.clear();
int sumRequired = sum - arr[i];
if(set.contains(sumRequired)) return true;
int second =i+1;
int last = size;
while(second < last) {
int s = arr[second] + arr[last];
if(s == sumRequired) return true;
set.add(s);
second++;
last--;
}
}
return false;
```

}

```
public static void main(String[] args) {
int[] arr = {1, 2, 3, 4, 5, 6, 7, 8, 1, 2, 3, 4, 5, 6};
int sum = 22;
boolean isTripletAvailable = findPossibleTriplets(arr, sum);
System.out.println("Triplet is " + (isTripletAvailable ? "available." : "not available."));
}
private static boolean findPossibleTriplets(int[] arr, int sum) {
int size = arr.length - 1;
for(int i=0; i<size-2;i++) {
int sumRequired = sum - arr[i];
int second =i+1;
int last = size;
while(second < last) {
int s = arr[second] + arr[last];
if(s == sumRequired) return true;
second++;
last--;
}
}
return false;
```

}

```
public static void main(String[] args) {
int[] arr = {1, 2, 3, 4, 5, 6, 7, 8, 1, 2, 3, 4, 5, 6};
int sum = 22;
boolean isTripletAvailable = findPossibleTriplets(arr, sum);
System.out.println("Triplet is " + (isTripletAvailable ? "available." : "not available."));
}
private static boolean findPossibleTriplets(int[] arr, int sum) {
int size = arr.length - 1;
for(int i=0; i<size-2;i++) {
int sumRequired = sum - arr[i];
int second =i+1;
int last = size;
while(second < last) {
int s = arr[second] + arr[last];
if(s == sumRequired) return true;
second++;
last--;
}
}
return false;
```

}

function findTriplet(arr,sum){

var result = false;

arr = arr.sort(function(a,b) { return a - b; });

var next;

var last;

for(var i =0; i< arr.length-2;i++){

next = i+1;

last = arr.length - 1;

while(next < last){

if(arr[i] + arr[next] + arr[last] === sum) {

result = true;

break;

} else if (arr[i] + arr[next] + arr[last] < sum){

next++;

} else {

last--;

}

}

}

return result;

}

I would agree that having it sorted is the proper approach, however by calling

would require loading the array into memory, which the question states cannot be done. You would have to do an external merge sort using small chunks of the entire array. I think you're missing a critical component of the question...

- andrei.hetman July 20, 2018