Katkat
Back

Maintain median of a data stream

TrexquantSoftware Engineer · Onsite
MediumSoftware EngineerOnsiteCoding & Algorithms

Last updated

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

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.