Top 6 Heaps Interview Questions
Browse 6 real-world technical and behavioral interview questions about Heaps. Review scenarios, edge cases, and architectural best practices.
Given everyone's busy calendar, find the slots when all of them are free. What do you sort, and what breaks at the boundaries?
Pool every busy interval, sort by start, and sweep with a cursor marking the end of the busy block so far. Any start beyond the cursor opens a common free slot. Use half-open intervals so back-to-back meetings leave no zero-length gap, and clip to the working day. Sorting costs O(N log N), or O(N log k) with a heap.
You are handed k sorted lists and asked for one sorted list. What is wrong with concatenating and sorting?
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.
Numbers arrive one at a time and after each one you must answer what the Kth largest so far is. What do you keep, and what do you deliberately throw away?
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.
Given a list of meetings with start and end times, tell me the minimum number of rooms needed to hold all of them.
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.
Numbers arrive one at a time and after each one I want the running median. How would you keep it?
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.
Return the k most frequent elements from a large stream of values. Why not just sort by frequency?
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.