Merge Integer Stream | Yaozong's Blog
Given an interface called IntStream with methods 'bool hasNext()' and 'int next()', implement the function 'IntStream merge(IntStream[] streams)' where each input IntStream produces strictly increasing, possibly infinite number of, integers, and the resultant IntStream also produces strictly increasing integers by merging the input streams. The interviewer also provides a simple test harness that prints the first 5000 integers from that function.
Given an interface called IntStream with methods 'bool hasNext()' and 'int next()', implement the function 'IntStream merge(IntStream[] streams)' where each input IntStream produces strictly increasing, possibly infinite number of, integers, and the resultant IntStream also produces strictly increasing integers by merging the input streams. The interviewer also provides a simple test harness that prints the first 5000 integers from that function.
class MergedIntStream: public IntStream {
public:
MergedIntStream(vector<IntStream*>& arr) {
m_arr = arr;
for (int i = 0; i < arr.size(); ++i) {
if (arr[i]->hasNext()) {
q.push( make_pair(arr[i]->next(), i) );
}
}
}
virtual bool hasNext() {
return !q.empty();
}
virtual int next() {
auto elem = q.top();
q.pop();
if (m_arr[elem.second]->hasNext())
q.push( make_pair(m_arr[elem.second]->next(), elem.second) );
return elem.first;
}
private:
priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> q;
vector<IntStream*> m_arr;
};
IntStream* merge(vector<IntStream*>& arr)
{
MergedIntStream* p = new MergedIntStream(arr);
return p;
}
Read full article from Merge Integer Stream | Yaozong's Blog