Skip to main content

295. Find Median from Data Stream

hardAsked at LinkedIn

Design a data structure that computes the median of an ever-growing stream using two heaps — LinkedIn runs this pattern to rank feed items by engagement score in real time, where you need a running median without resorting the entire dataset on every new signal.

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

Problem

The MedianFinder class should support two operations: addNum(int num) — adds a number from the data stream, and findMedian() — returns the median of all elements added so far. If the count is even, return 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 always be called after at least one addNum

Examples

Example 1

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

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

Approaches

1. Sorted array insert — brute force

Maintain a sorted array. Use binary search to insert each new number in O(log n), but shift costs O(n). findMedian is O(1). Simple but O(n) per add.

Time
O(n) per addNum, O(1) findMedian
Space
O(n)
class MedianFinderBrute {
  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;
    if (n % 2 === 1) return this.data[n >> 1];
    return (this.data[n/2-1] + this.data[n/2]) / 2;
  }
}

Tradeoff:

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

Keep a max-heap of the smaller half and a min-heap of the larger half. Balance sizes so they differ by at most 1. Median is either the max-heap top (odd total) or average of both tops (even total). O(log n) per add, O(1) median.

Time
O(log n) per addNum, O(1) findMedian
Space
O(n)
// JavaScript lacks a built-in heap — use a MinHeap class:
class MinHeap {
  constructor(cmp = (a,b) => a-b) { 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];}
  size(){return this.h.length;}
  _up(i){while(i>0){const p=(i-1)>>1;if(this.cmp(this.h[i],this.h[p])<0){[this.h[i],this.h[p]]=[this.h[p],this.h[i]];i=p;}else break;}}
  _down(i){const n=this.h.length;while(true){let s=i,l=2*i+1,r=2*i+2;if(l<n&&this.cmp(this.h[l],this.h[s])<0)s=l;if(r<n&&this.cmp(this.h[r],this.h[s])<0)s=r;if(s===i)break;[this.h[i],this.h[s]]=[this.h[s],this.h[i]];i=s;}}
}

class MedianFinder {
  constructor() {
    this.lo = new MinHeap((a,b)=>b-a); // max-heap (lower half)
    this.hi = new MinHeap();            // min-heap (upper half)
  }
  addNum(num) {
    this.lo.push(num);
    this.hi.push(this.lo.pop()); // balance: ensure lo.max <= hi.min
    if (this.lo.size() < this.hi.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:

LinkedIn-specific tips

LinkedIn uses this problem to see if you can design a live-ranking data structure under insertion pressure — the same pattern powers their feed-score stream. The key insight to narrate aloud: 'I'll split the data into a lower and upper half; the lower is a max-heap so I can peek the largest small value in O(1).' The interviewer will probe the balance invariant — explain why you push to lo first, then rebalance to hi. A follow-up is often 'what if the stream contains only integers in [0, 100]?' — bucket-count array, O(1) insert, O(1) median with two pointers.

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

Practice these live with InterviewChamp.AI →