Skip to main content

28. Find Median from Data Stream

hardAsked at Coinbase

Maintain the real-time median bid price as orders stream in — Coinbase uses this dual-heap problem to test whether engineers can design O(log n) insert / O(1) median structures for continuous market-data feeds.

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

Problem

Implement the MedianFinder class: MedianFinder() initialises the object; addNum(num) adds an integer from the data stream to the data structure; findMedian() returns the median of all elements so far. If the total count is even, the median is the average of the two middle values.

Constraints

  • -10^5 <= num <= 10^5
  • There will be at least one element before findMedian is called
  • At most 5 * 10^4 calls will be made to addNum and findMedian

Examples

Example 1

Input
MedianFinder(), addNum(1), addNum(2), findMedian(), addNum(3), findMedian()
Output
1.5, 2.0

Explanation: After [1,2]: median = (1+2)/2 = 1.5. After [1,2,3]: median = 2.

Approaches

1. Sorted array insertion

Keep a sorted array; binary-search insert each new number, return middle element(s). Easy to code, costly at scale.

Time
O(n) addNum, O(1) findMedian
Space
O(n)
class MedianFinder {
  constructor() { this.data = []; }

  addNum(num) {
    let lo = 0, hi = this.data.length;
    while (lo < hi) {
      const mid = (lo + hi) >> 1;
      if (this.data[mid] < num) lo = mid + 1;
      else hi = mid;
    }
    this.data.splice(lo, 0, num);
  }

  findMedian() {
    const n = this.data.length;
    return n % 2 === 1
      ? this.data[(n - 1) / 2]
      : (this.data[n / 2 - 1] + this.data[n / 2]) / 2;
  }
}

Tradeoff:

2. Two heaps (max-heap lower half + min-heap upper half)

Maintain a max-heap of the lower half and a min-heap of the upper half, balanced so their sizes differ by at most 1. Median is top of the larger heap or average of both tops.

Time
O(log n) addNum, O(1) findMedian
Space
O(n)
// Heap helpers (JS has no built-in heap)
class Heap {
  constructor(cmp) { this.h = []; this.cmp = cmp; }
  push(v) { this.h.push(v); this._up(this.h.length - 1); }
  pop() {
    const top = this.h[0];
    const last = this.h.pop();
    if (this.h.length) { this.h[0] = last; this._down(0); }
    return top;
  }
  peek() { return this.h[0]; }
  get size() { return this.h.length; }
  _up(i) {
    while (i > 0) {
      const p = (i - 1) >> 1;
      if (!this.cmp(this.h[i], this.h[p])) break;
      [this.h[i], this.h[p]] = [this.h[p], this.h[i]]; i = p;
    }
  }
  _down(i) {
    const n = this.h.length;
    while (true) {
      let best = i;
      const l = 2*i+1, r = 2*i+2;
      if (l < n && this.cmp(this.h[l], this.h[best])) best = l;
      if (r < n && this.cmp(this.h[r], this.h[best])) best = r;
      if (best === i) break;
      [this.h[i], this.h[best]] = [this.h[best], this.h[i]]; i = best;
    }
  }
}

class MedianFinder {
  constructor() {
    this.lo = new Heap((a, b) => a > b); // max-heap (lower half)
    this.hi = new Heap((a, b) => a < b); // min-heap (upper half)
  }

  addNum(num) {
    this.lo.push(num);
    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:

Coinbase-specific tips

Coinbase asks this almost verbatim as a market-data median tracker: given a continuous stream of trade prices, return the real-time median for circuit-breaker logic. The dual-heap is the canonical answer. They watch how you handle the rebalancing step — specifically, whether you always route through the max-heap first before pushing to the min-heap, which keeps the invariant tight.

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

Practice these live with InterviewChamp.AI →