## Google Interview Question for Data Engineers

Country: United States

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

algo: O(n^2):
Fill 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

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

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

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

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

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

@jayz: your solution is not O(n^2) as you have to traverse to the list to count elements.

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

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

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.