Skip to question
ASIC.FYI

Q264FreeFirmware

Exact Streaming Median

Difficulty
Hard
Topic
Data Structures
Language
SV
Interview prompt

Question

Continuously process signed integers and report the exact median of all values seen so far. The implementation must not sort the complete history on every query.

Starting point

Question code

class StreamingMedian;
  void push(int x);
  bit get_median(output real median);
  int size();
endclass
Reviewed example

Trace one case

Input
stream = [5, 1, 9, 3]
Expected output
median after each insertion = [5, 3, 5, 4]

For even counts the exact median is the average of the two middle values; 1 and 5 therefore yield 3, then 3 and 5 yield 4.

What to cover

Requirements

  1. Support negative values, duplicates, and both odd and even element counts.
  2. Return failure status 0 from get_median when no values have been observed, leaving its output argument unchanged.
  3. Target O(log n) push, O(1) median query, and O(n) storage.
  4. For an even count, average the two middle values without overflowing a 32-bit intermediate.
  5. Keep the lower and upper partitions balanced after every insertion.
Continue practicing
Q217 · Data StructuresExpiring Key-Value StoreQ266 · Data StructuresLongest-Prefix-Match Routing TableQ273 · Data StructuresReturn the first unique value in a stream