Maintain a Stream Median
Company: Ixl
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: hard
Interview Round: Technical Screen
Design a data structure for a stream of integers. It must support the following operations efficiently:
- `add_num(x)`: insert an integer `x` into the stream.
- `get_median()`: return the median of all numbers seen so far.
The median is defined as:
- the middle value when the count of numbers is odd,
- the average of the two middle values when the count is even.
Implement this data structure so that it can handle many insertions and median queries efficiently.
Quick Answer: This question evaluates the ability to design and implement efficient online data structures and algorithms for maintaining dynamic order statistics and computing the median of a stream of integers.
Process add and median operations over an integer stream using two heaps. Return one output per operation, with None for add.
Constraints
- Inputs are Python literals matching the function signature.
- Return a deterministic exact-match value.
Examples
Input: ([['add',1], ['add',2], ['median'], ['add',3], ['median']],)
Expected Output: [None, None, 1.5, None, 2.0]
Explanation: Odd and even medians.
Input: ([['median'], ['add',-1], ['median']],)
Expected Output: [None, None, -1.0]
Explanation: Empty query and negative value.
Input: ([['add',5], ['add',5], ['median']],)
Expected Output: [None, None, 5.0]
Explanation: Duplicates.
Hints
- Choose a representation that makes the requested operation direct.
- Handle empty inputs and boundary cases first.