1,000+ ASIC Interview Questions: SystemVerilog, UVM & RTL

DescriptionQ264

Page ↗

Q264FWDVASIC interview problem

Exact Streaming Median

TechniquesDVFWTwo heapsStreamingNumerical safety

DifficultyHard

TopicData Structures

LanguageSystemVerilog

Requirements5 checkpoints

Problem

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.

Class declarationSystemVerilog

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

Example input and output

Use this case to check your interpretation

Input

stream = [5, 1, 9, 3]

Output

median after each insertion = [5, 3, 5, 4]

Explanation

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.

Requirements (5)

Support negative values, duplicates, and both odd and even element counts.
Return failure status 0 from get_median when no values have been observed, leaving its output argument unchanged.
Target O(log n) push, O(1) median query, and O(n) storage.
For an even count, average the two middle values without overflowing a 32-bit intermediate.
Keep the lower and upper partitions balanced after every insertion.