Maintain median of a data stream
Company: Trexquant
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
Design a data structure that supports:
- `addNum(int x)`: Add an integer from a stream.
- `findMedian()`: Return the median of all inserted numbers so far.
Median definition:
- If the count is odd: the middle element after sorting.
- If the count is even: average of the two middle elements.
### Requirements
- Aim for `O(log n)` per insertion and `O(1)` (or `O(log n)`) per median query.
- Implement in C++.
### Constraints
- Up to ~10^5 insertions/queries.
- Values may be negative and can repeat.
Quick Answer: This question evaluates proficiency in streaming data aggregation, dynamic order-statistics maintenance, and algorithmic complexity analysis for insertion and query operations.
Return the median after each inserted number in the stream.
Constraints
- Values may repeat and may be negative
Examples
Input: ([1, 2, 3],)
Expected Output: [1.0, 1.5, 2.0]
Explanation: Increasing stream.
Input: ([5, 15, 1, 3],)
Expected Output: [5.0, 10.0, 5.0, 4.0]
Explanation: Even and odd counts.
Input: ([-1, -2, -3],)
Expected Output: [-1.0, -1.5, -2.0]
Explanation: Negative values.
Input: ([],)
Expected Output: []
Explanation: Empty stream.
Hints
- Maintain a max-heap for the lower half and a min-heap for the upper half.