Facebook | Onsite | Merge K Sorted Arrays
Anonymous User
11054

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;
}
Comments (12)