Design Efficient Data Structure for Median Retrieval

Scenario

Senior problem-solving round assessing algorithmic thinking under time pressure.

Question

Design a data structure that supports inserting integers from an endless stream and returning the median in O(log n) per insertion and O(1) per query. Provide code and complexity analysis.

Hints

Two heaps approach; keep sizes balanced; median at roots.

Design Efficient Data Structure for Median Retrieval

Design a data structure that ingests integers from an endless stream and can return the running median efficiently. It must support two operations:

• addNum(num): add the integer num to the structure.
• findMedian(): return the median of all integers added so far. With an even count the median is the average of the two middle values; with an odd count it is the single middle value. If no numbers have been added, return null.

Your insert must run in O(log n) and each median query in O(1).

To make the design executable here, implement a single function/method that replays a list of operations and returns one entry per findMedian call. Each operation is a list: ["addNum", num] inserts num, and ["findMedian"] queries the current median. Return a list whose i-th element is the median produced by the i-th findMedian operation (use null/None when the structure is empty). Medians are returned as floating-point values (e.g. an integer median of 4 is 4.0).

Hint: keep two heaps — a max-heap holding the smaller half and a min-heap holding the larger half — and rebalance after each insert so their sizes differ by at most one. The median is then read off the heap roots in O(1).

Constraints

• 1 <= number of operations <= 5 * 10^4
• -10^5 <= num <= 10^5 for each addNum
• findMedian on an empty structure returns null
• addNum must be O(log n); findMedian must be O(1)

Examples

Example 1

Input: ([["addNum", 1], ["addNum", 2], ["findMedian"], ["addNum", 3], ["findMedian"]],)
Output: [1.5, 2.0]

Explanation: After adding 1 and 2 the two middle values are 1 and 2, so the median is (1+2)/2 = 1.5. After adding 3 the values are [1,2,3] and the single middle value is 2.0.

Example 2

Input: ([["addNum", 5], ["findMedian"], ["addNum", 5], ["findMedian"], ["addNum", 5], ["findMedian"]],)
Output: [5.0, 5.0, 5.0]

Explanation: All inserted values are equal, so the median is 5.0 regardless of count, covering the duplicate-values case.

Hints

1. Maintain two heaps: a max-heap for the smaller half of the numbers and a min-heap for the larger half.
2. After each insert, rebalance so the heaps' sizes differ by at most one — push the offending root across when one heap grows too large.
3. If the heaps are equal in size, the median is the average of the two roots; otherwise it is the root of the larger heap. Both are O(1) reads.