Quick Overview

This question evaluates understanding of streaming data structures, median maintenance, and algorithmic complexity in the Coding & Algorithms domain by requiring efficient insertions (O(log n)) and constant-time median queries (O(1)).

Design Efficient Data Structure for Median Retrieval

Company: Amazon

Role: Data Scientist

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

##### 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.

Quick Answer: This question evaluates understanding of streaming data structures, median maintenance, and algorithmic complexity in the Coding & Algorithms domain by requiring efficient insertions (O(log n)) and constant-time median queries (O(1)).

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

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

Expected 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.

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

Expected 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.

Loading coding console...