Google Interview Question Software Engineers
Country: United States
Interview Type: In-Person
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...
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))
The following is a bit cleaner code and more efficient than yours; however, it is still O(n^2).
def triplet_sum(list1, k):
result = list()
for index, x in enumerate(list1):
set1 = set()
for y in list1[index+1:]:
z = k - (x+y)
if set1.__contains__(z):
result.append([z, x, y])
else:
set1.add(y)
return result
ret = triplet_sum([-1, 0, 1, 2, -1, -4], 0)
print(ret)
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.
/*
Given an array and a value, find if there is a triplet in array whose sum is equal to the given value.
If there is such a triplet present in array, then print the triplet and return true.
Else return false.
For example, if the given array is {12, 3, 4, 1, 6, 9} and given sum is 24,
then there is a triplet (12, 3 and 9) present in array whose sum is 24.
*/
console.log(findTriplet3([1,2,3,4,6,9,20], 18));
function findTriplet(list, target) {
for (let i = 0; i < list.length; i++) {
const first = list[i];
for (let j = i + 1; j < list.length; j++) {
const second = list[j];
for (let h = j + 1; h < list.length; h++) {
const third = list[h];
if (target - third - second - first === 0) {
console.log([first, second, third]);
return true;
}
}
}
}
return false;
}
function findTriplet2(list, target) {
const numbers = new Set(list);
for (let i = 0; i < list.length; i++) {
const first = list[i];
for (let j = i + 1; j < list.length; j++) {
const second = list[j];
if (numbers.has(target - second - first)) {
console.log([first, second, target - second - first]);
return true;
}
}
}
return false;
}
function findTriplet3(list, target) {
list.sort((a, b) => a - b);
let left, right;
for (let i = 0; i < list.length; i++) {
const first = list[i];
left = i + 1;
right = list.length - 1;
while (left < right) {
const second = list[left];
const third = list[right];
const sum = first + second + third;
if (sum === target) {
console.log([first, second, target - second - first]);
return true;
}else if (sum > target) {
right--;
}else if (sum < target) {
left ++;
}
}
}
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;
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;
}
1) For sorting, use extenal sorting
- dadakhalandhar August 05, 20182) 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