Skip to main content

295. Find Median from Data Stream

hardAsked at Bloomberg

Bloomberg's real-time analytics dashboard streams millions of trade prices per day and must serve a live median price metric at sub-millisecond latency — this problem tests the two-heap trick that keeps median retrieval O(1) even as data flows in.

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

Problem

The MedianFinder class should support two operations: addNum(num) adds a number from the data stream, and findMedian() returns the median of all elements added so far. If there is an even number of elements, the median is the average of the two middle values.

Constraints

  • -10^5 <= num <= 10^5
  • At most 5 * 10^4 calls to addNum and findMedian
  • findMedian will not be called on an empty stream

Examples

Example 1

Input
MedianFinder(); addNum(1); addNum(2); findMedian(); addNum(3); findMedian()
Output
[null, null, null, 1.5, null, 2.0]

Explanation: After [1,2] the median is 1.5. After [1,2,3] the median is 2.

Approaches

1. Sorted array insertion

Maintain a sorted list; binary-search to insert each new number, then read the middle. O(n) insertion due to shifts.

Time
O(n) add, 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]
      : (this.data[(n >> 1) - 1] + this.data[n >> 1]) / 2;
  }
}

Tradeoff:

2. Two heaps (optimal)

A max-heap holds the lower half; a min-heap holds the upper half. Keep them balanced (size difference at most 1). Median is the max-heap top (odd count) or average of both tops (even count). Each addNum is O(log n); findMedian is O(1).

Time
O(log n) add, O(1) findMedian
Space
O(n)
class Heap {
  constructor(cmp) { this.data = []; this.cmp = cmp; }
  push(v) { this.data.push(v); this._up(this.data.length - 1); }
  pop() {
    const top = this.data[0];
    const last = this.data.pop();
    if (this.data.length) { this.data[0] = last; this._down(0); }
    return top;
  }
  peek() { return this.data[0]; }
  size() { return this.data.length; }
  _up(i) {
    while (i > 0) {
      const p = (i - 1) >> 1;
      if (this.cmp(this.data[i], this.data[p])) {
        [this.data[i], this.data[p]] = [this.data[p], this.data[i]]; i = p;
      } else break;
    }
  }
  _down(i) {
    const n = this.data.length;
    while (true) {
      let best = i, l = 2*i+1, r = 2*i+2;
      if (l < n && this.cmp(this.data[l], this.data[best])) best = l;
      if (r < n && this.cmp(this.data[r], this.data[best])) best = r;
      if (best === i) break;
      [this.data[i], this.data[best]] = [this.data[best], this.data[i]]; i = best;
    }
  }
}

class MedianFinder {
  constructor() {
    this.lo = new Heap((a, b) => a > b);
    this.hi = new Heap((a, b) => a < b);
  }
  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() {
    return this.lo.size() > this.hi.size()
      ? this.lo.peek()
      : (this.lo.peek() + this.hi.peek()) / 2;
  }
}

Tradeoff:

Bloomberg-specific tips

Bloomberg asks this specifically for roles touching real-time analytics or risk. The two-heap structure maps directly onto how Bloomberg's internal median-price service partitions the price distribution — lower half in a max-heap, upper half in a min-heap, rebalanced on each new quote. Explain the rebalancing invariant verbally before coding: 'lo.size() is always equal to or one greater than hi.size().' Then implement — interviewers watch whether you handle both the odd and even cases in findMedian.

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

Practice these live with InterviewChamp.AI →