Questions / Quant development, Algorithms & structures
Maintain only the top k
A size-3 min-heap keeps the largest values seen. The stream is 5, 1, 9, 3, 7, 8. What is the heap root at the end?
Answer it in the app It's free. You get hints, a second try if you miss, and a follow-up question.
Show the answer and worked solution
Answer: 7 value
- After 5, 1, 9 the heap holds {1, 5, 9}.
- 3 replaces 1, 7 replaces 3, and 8 replaces 5.
- The heap holds {7, 8, 9}, so the root, the cutoff, is 7.
Interview shortcut. Top three {7, 8, 9}; the root is the smallest.
Takeaway. The min-heap root is the k-th largest so far.
In the app this has a follow-up where one thing about the setup changes. Try the follow-up.