Meta Interview Question
Given two sorted input arrays which contain a two element array of [key, value], write a function which multiplies the two arrays together and sums them where the "key" matches. Example: "v1 = [[1, 3], [2, 4], [99, 3]]; v2 = [[2,3],[5,9],[99,1]]" results in "15". I first brute forced it with O(n*m) then used two pointers which resulted in O(n+m) then he asked me to write it in O(n log m). I could not think of an algorithm at the time for O(n log m).
Interview Answers
That would be O(n+m) not O(max(n,m)) the O(n log m) solution is a divide and conquer algorithm like merge sort.... Middle out.
Can't you add the elements of both the arrays into a HashMap and then iterate through the smaller map find matching keys in the other map and sum them up.
Foreach key in the 2nd set, binary search in the first set, multiply and accumulate. This is O(NLogN).
Just as a note, O(N+M) is equivalent to O(max(N, M)). To prove it:
N + M = N.
For example, if N == M, then the running times become:
O(N+M) = O(2N) = O(N)
O(N*log M) = O(N * log N)
and the two pointer solution will perform better.
But if M == N^2, then
O(N+M) = O(N + N^2) = O(N^2)
O(N log M) = O(N * log N^2) = O(N * log N)
and the binary search method will perform better.
Solution is similar to Merge Sort algorithm.
Using binary search, O(N logM)
#include
#include
#include
int searchVal(std::vector >& v1, int val, uint32_t init, uint32_t end)
{
int middle = (end + init )/2;
if (v1.at(middle).first == val)
return v1.at(middle).second;
if (middle == init){
return -1;
}
else
{
if (v1.at(middle).first > val)
{
return searchVal(v1, val, init, middle-1);
}
else
{
return searchVal(v1, val, middle+1, end);
}
}
}
int getSum(std::vector > v1, std::vector > v2)
{
int sum = 0;
for (int i = 0; i > v1;
std::vector > v2;
v1.push_back(std::pair (1, 3));
v1.push_back(std::pair (2, 4));
v1.push_back(std::pair (99, 3));
v2.push_back(std::pair (2, 3));
v2.push_back(std::pair (5, 9));
v2.push_back(std::pair (99, 1));
std::cout << getSum(v1, v2) << std::endl;
return 0;
}
#include
#include
#include
int searchVal(std::vector >& v1, int val, uint32_t init, uint32_t end)
{
int middle = (end + init )/2;
if (v1.at(middle).first == val)
return v1.at(middle).second;
if (middle == init){
return -1;
}
else
{
if (v1.at(middle).first > val)
{
return searchVal(v1, val, init, middle-1);
}
else
{
return searchVal(v1, val, middle+1, end);
}
}
}
int getSum(std::vector > v1, std::vector > v2)
{
int sum = 0;
for (int i = 0; i > v1;
std::vector > v2;
v1.push_back(std::pair (1, 3));
v1.push_back(std::pair (2, 4));
v1.push_back(std::pair (99, 3));
v2.push_back(std::pair (2, 3));
v2.push_back(std::pair (5, 9));
v2.push_back(std::pair (99, 1));
std::cout << getSum(v1, v2) << std::endl;
return 0;
}
Here is the missing fuction that it is being left out for some reason:
int getSum(std::vector > v1, std::vector > v2)
{
int sum = 0;
for (int i = 0; i < v1.size(); ++i)
{
int search = searchVal(v2, v1.at(i).first, 0, v2.size()-1);
if ( -1 != search)
{
sum += search * v1.at(i).second;
}
}
return sum;
}