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.
Overview: This question evaluates proficiency in streaming data aggregation, dynamic order-statistics maintenance, and algorithmic complexity analysis for insertion and query operations.
Read the full Trexquant Software Engineer interview experience this question came from
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.
Hints
- Maintain a max-heap for the lower half and a min-heap for the upper half.