Maintain median of a data stream

Q: Maintain median of a data stream

This question evaluates proficiency in streaming data aggregation, dynamic order-statistics maintenance, and algorithmic complexity analysis for insertion and query operations.

Q: How do I approach Coding & Algorithms interview questions?

Coding & Algorithms questions require understanding of core concepts and practice. PracHub provides solutions with explanations to help you master coding & algorithms interviews.

Question

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.

Maintain median of a data stream

Quick Overview

Requirements

Constraints

Comments (0)