Google Interview Question
Data EngineersCountry: United States
we can use 1d arrays:
unsigned count_tuples(vector<int>& numbers){
unordered_map<int, unsigned> sum2;
unordered_map<int, unsigned> sum3;
unsigned result = 0;
for(unsigned i = 0; i < numbers.size(); ++i){
auto sum3it = sum3.find(numbers[i]);
if(sum3it != sum3.end()){
result += sum3it->second;
}
for(const auto& sum : sum2){
auto newSum = sum.first +numbers[i];
auto sum3it = sum3.find(newSum);
if(sum3it == sum3.end()){
sum3.insert(make_pair(newSum, sum.second));
} else {
sum3it->second += sum.second;
}
}
for(unsigned y = 0; y < i; ++y){
auto newSum = numbers[y] +numbers[i];
auto sum2it = sum2.find(newSum);
if(sum2it == sum2.end()){
sum2.insert(make_pair(newSum, 1));
} else {
++sum2it->second;
}
}
}
return result;
}
we can use just two additional 1-d arrays to solve
unsigned count_tuples(vector<int>& numbers){
unordered_map<int, unsigned> sum2;
unordered_map<int, unsigned> sum3;
unsigned result = 0;
for(unsigned i = 0; i < numbers.size(); ++i){
auto sum3it = sum3.find(numbers[i]);
if(sum3it != sum3.end()){
result += sum3it->second;
}
for(const auto& sum : sum2){
auto newSum = sum.first +numbers[i];
auto sum3it = sum3.find(newSum);
if(sum3it == sum3.end()){
sum3.insert(make_pair(newSum, sum.second));
} else {
sum3it->second += sum.second;
}
}
for(unsigned y = 0; y < i; ++y){
auto newSum = numbers[y] +numbers[i];
auto sum2it = sum2.find(newSum);
if(sum2it == sum2.end()){
sum2.insert(make_pair(newSum, 1));
} else {
++sum2it->second;
}
}
}
return result;
}
Python:
from collections import Counter
def num_of_summing_tuples(ar,n=4):
num_of_matches = 0
endings = Counter() #(result,numofops) -> count
for value in reversed(ar):
updater = Counter()
updater.update({(-value,1) : 1})
for k,count_so_far in endings.items():
end_v , num_of_ops = k
new_ending = value+end_v
new_num_of_ops = num_of_ops + 1
if new_ending==0 and new_num_of_ops==n:
num_of_matches+=count_so_far
if new_num_of_ops <= n-1:
updater.update({(new_ending,new_num_of_ops) : count_so_far})
endings.update(updater)
return num_of_matches
algo: O(n^2):
- jayz January 27, 2018Fill 2 2d arrays with
arr1[i][j]=a[i]+a[j]
arr2[i][j]=a[j]-a[i]
j>i
In a map<int,list<int>>, map[arr1[i][j]].push_back(j)
For each element in arr2, search in the map.
Count all hits where j < k