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.