Microsoft Interview Question
Software Engineer / DevelopersCountry: United States
Interview Type: Phone Interview
First number of one stream could be higher than (or equal to) the last number of other stream
S1 S2 S3 S4
10 12 15 7
9 11 14 4
5 8 13 3
1 7 6 0
We create a Min-Heap which takes O(nlogn) for creation and
ReadNextNumber - O(1) - findmin operation on min-heap
WriteToStream - O(log n) - insert operation on min-heap
each stream has its worker in a thread. for each read number from any stream we create a process that sleeps (100 + said number). for example for 2 streams: a: 7, 2, 1, 100,... and b: 0, 42, 80928, 124,.... you will have worker_i(n) -> spawn fun(n) -> sleep(100+n), print(n) end, end.
enjoy
- First read 1 number from each of K streams, and build a PriorityQueue
- After that keep removing top from PQ, and add next number from the same stream(from which top came)
----- if this stream is over, just move on
- Now repeat this while PQ is not empty
- X July 13, 2015