Skip to main content

22. Find Median from Data Stream

hardAsked at Rappi

Support addNum and findMedian on a streaming sequence of integers — Rappi frames this as tracking the running median delivery ETA across an open stream of in-flight orders.

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

Problem

Design a MedianFinder class with addNum(num) and findMedian(). findMedian returns the median of all numbers added so far.

Constraints

  • -10^5 <= num <= 10^5
  • At most 5 * 10^4 calls

Examples

Example 1

Input
addNum(1); addNum(2); findMedian()
Output
1.5

Example 2

Input
addNum(3); findMedian()
Output
2.0

Approaches

1. Sort on every query

Store values in an array; sort and pick middle on each findMedian call.

Time
O(n log n) per query
Space
O(n)
class MedianFinder {
  constructor() { this.a = []; }
  addNum(n) { this.a.push(n); }
  findMedian() { const s = [...this.a].sort((a,b)=>a-b); const m = s.length>>1; return s.length%2 ? s[m] : (s[m-1]+s[m])/2; }
}

Tradeoff:

2. Two heaps (max+min)

Keep a max-heap for the lower half and a min-heap for the upper half; rebalance on each insert so sizes differ by at most one — median is roots.

Time
O(log n) add, O(1) median
Space
O(n)
// Pseudocode — use a real heap library.
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() {
    return this.lo.size > this.hi.size ? this.lo.top() : (this.lo.top() + this.hi.top()) / 2;
  }
}

Tradeoff:

Rappi-specific tips

Rappi insists on the two-heap pattern — they'll explicitly ask you to defend why a balanced BST or sorted-insertion is strictly worse for their streaming ETA percentile job.

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 Rappi interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →