Skip to main content

24. Find Median from Data Stream

hardAsked at Activision

Design a structure that supports addNum and findMedian — Activision uses this to gauge dual-heap design before live leaderboard percentile-tracking questions.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Problem

Implement MedianFinder with addNum(num) to ingest stream values and findMedian() returning the running median. Median is average of the two middle values for even-sized streams.

Constraints

  • -10^5 <= num <= 10^5
  • Up to 5 * 10^4 calls
  • findMedian called only after at least one addNum

Examples

Example 1

Input
ops=["MedianFinder","addNum","addNum","findMedian","addNum","findMedian"], args=[[],[1],[2],[],[3],[]]
Output
[null,null,null,1.5,null,2.0]

Example 2

Input
addNum(2); addNum(3); findMedian()
Output
2.5

Approaches

1. Sorted insertion

Insert each number in sorted order via binary search.

Time
O(n) per add
Space
O(n)
// splice into sorted array — O(n) addNum, O(1) findMedian

Tradeoff:

2. Two heaps (max-heap low, min-heap high)

Keep a max-heap of the lower half and a min-heap of the upper half, balanced within one element. Median is either the larger heap's root or the average of both roots.

Time
O(log n) per add, O(1) findMedian
Space
O(n)
class MedianFinder {
  constructor() { this.lo = new MaxHeap(); this.hi = new MinHeap(); }
  addNum(n) {
    this.lo.push(n);
    this.hi.push(this.lo.pop());
    if (this.hi.size() > this.lo.size()) this.lo.push(this.hi.pop());
  }
  findMedian() {
    if (this.lo.size() > this.hi.size()) return this.lo.peek();
    return (this.lo.peek() + this.hi.peek()) / 2;
  }
}

Tradeoff:

Activision-specific tips

Activision wants you to spell out the balance invariant before coding — same dual-heap shape they use when streaming live leaderboard percentile cuts every tick.

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Practice these live with InterviewChamp.AI

Drill Find Median from Data Stream and other Activision interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →