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

In the worse case, you need to output the entire array. I am not assuming that I have enough disk space to do so, so let's say I will be outputting to some output stream, it can be the disk or some external service.

In the words case, all the triples matches will appear at the end of the array, so I will have to keep a track on all the numbers at the beginning of the array. I am not assuming that I can put 2/3 of the array in memory so I will store the data in a database, that is not necessary on my machine.

Having said that memory can be optimized by encoding the data, let's say into ranges or using in-memory zip stream, but even with all those optimizations I wouldn't assume that I have enough memory.

```
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