## Google Interview Question for Software Engineers

Country: United States
Interview Type: In-Person

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

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

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

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

``arr.sort()``

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

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

Assuming you are on a 64-bit system where practically any file on your hard drive can fit in your virtual address space, you just do an external sort, mmap the resultant file and then do a usual 3sum with 3 pointers. OS will take care of (un)loading pages to/from real memory.

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

"given that the array is too big to fit into memory" - was that asked as a followup question? or right from the start?

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

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

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

O(n^2) using single hash table
#1: insert all elems into hash table
#2: for each elem in hash table
---- fix elem i as one of the triplets
---- for all other elements j != i :
----- look for sum - (i + j) in hash table
---- if found, output triplet

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

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

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

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.

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

``````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;
second++;
last--;
}
}
return false;``````

}

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

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

}

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

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

}

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

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

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.