Implement a method to merge K sorted arrays.
The time complexity must be better than O(N*K).
Method signature (C++): vector<char> merge(vector<vector<char>> chunks)
(Edit) Here is an O(N log K) solution I proposed (the interviewer seemed to be satisfied with it).
If anyone has a better idea - please post.
vector<char> merge(vector<vector<char>>& chunks)
{
typedef pair<vector<char>::iterator, vector<char>::iterator> it_pair;
auto comp = [](auto& a, auto& b){return *a.first > *b.first;};
priority_queue<it_pair, vector<it_pair>, decltype(comp)> q(comp);
for(auto& v : chunks) q.push({v.begin(), v.end()});
vector<char> res;
while(q.size())
{
auto [it, end] = q.top(); q.pop();
res.push_back(*it);
if(++it != end) q.push({it, end});
}
return res;
}