Linkedin Interview Question Software Engineer / Developers
Good answer but I think you should use a priority queue. Store the array from which each element came and set the value of the element as the priority.
Concur..
Strategy is to ignore how big the data is and deal with it in a controlled way.
Min or Max heap (depending on sorting order) with initial pull from the first (top) element in each stream.
Whenever the top of heap is extracted, pull another top from the same stream.
- some extra pointer here needed to associate the heap element back to the parent data stream.
I'd assume that, unless this was too far along in the interview process to possibly be that simple. My association with 'streams' is that they're lazy, ie on-demand. So, every time you get a 'demand' for an item, walk the fronts of the non-empty streams, keeping track of the lowest item and where it was. At the end, produce that lowest item (taking care to remove it from its stream).
but how is heap going to help if it's an infinite stream? even that will require memory. Actually I didn't get the question well.. What is significance of the stream being "infinite"? how exactly we delimit the stream into workable subsets etc.. ?
Since it is a stream, it probably means that we can read it sequentially. Also the problem says that stream is sorted so the first element in a stream is smaller than the second element. The solution seems simple:
1. Read first element from stream 1
2. Read first element from stream 2
3. Compare the two and write the smaller one to output stream keeping the other one with us.
4. If the element that was written to stream was from stream1 pick the next element from stream1 else pick from stream2 and compare with the element with us in step 3 and write the smaller to output stream.
5. Repeat
It is kinda like merge-sort
Question is with 'n' streams which is a finite value, & implicitly means that you can store those many values.. Only problem is that, you cannot store these values all in one go, as they are infinite stream ==> that cannot be contained by your RAM size.... Now if you know, how min-heap works, the first answer is closest one till now
Assuming the arrays are sorted in ascending order.
- Paras February 25, 20111. Create a Min Heap of size n.
2. Insert every 1st element of the arrays into heap.
3. Get the top element out of the heap and pop it out (print/store it).
4. Keep a track of the array from which the popped element came from and insert the next element from that array only.
4. reheap/heapfy the heap.
5. repeat 2-4 untill the element count in heap becomes zero.