Loading...
Loading...
Browse 5 real-world technical and behavioral interview questions about Heaps. Review scenarios, edge cases, and architectural best practices.
Nothing about correctness - it works. It throws away the sortedness you were given and pays O of N log N to rebuild it, where merging costs O of N log k, and it requires every element resident at once where a merge requires k. On lists that arrive as streams the second objection is the one that disqualifies it outright.
Keep a min-heap holding exactly the K largest values seen. Its root is the answer, so the query is a read rather than a search, and every value smaller than that root is discarded the moment it arrives. What you give up is the ability to answer for any K larger than the one you chose, which is why the first thing to establish is whether K is fixed.
The answer is the maximum number of meetings running at once, found by sweeping the start and end times in sorted order and tracking a running count. The starts and ends can be sorted independently of each other, and a meeting ending exactly when another begins must free its room or you will overcount.
Split the values across a max-heap of the lower half and a min-heap of the upper half, so the median is read off one or both tops. Balancing by size alone is what breaks it: a new value has to enter through the heap it belongs to by value and be transferred across, never pushed into whichever heap is currently smaller.
Count occurrences, then push counts through a min-heap capped at size k, evicting the smallest whenever the heap overflows. That is O(n log k) rather than the O(n log n) of a full sort, it needs only k items resident at once, and it works on a stream you cannot re-read.