‹ DS&A interview · Socratic
DSA · Heap · #72

Find Median from Data Stream

Module 61 · difficulty 4/5·⏱ 30:00starts on first keystroke

The **median** is the middle value in an ordered list. If the list has an even number of elements, the median is the average of the two middle values. Design a data structure that supports adding integers from a data stream and finding the median of all elements added so far. Implement the class `MedianFinder`: - `MedianFinder()` initializes the object. - `addNum(num)` adds the integer `num` to the structure. - `findMedian()` returns the median of all elements so far. Answers within `1e-5` of the true value are accepted.

Examples
  • addNum(1); addNum(2); findMedian(); addNum(3); findMedian(); → 1.5, 2.0 — After adding 1 and 2 the sorted list is [1,2] -> median (1+2)/2 = 1.5. After adding 3 the list is [1,2,3] -> median 2.
  • addNum(5); findMedian(); → 5.0 — Single element: the median is the element itself.
  • addNum(-1); addNum(-2); addNum(-3); findMedian(); → -2.0 — Sorted [-3,-2,-1] -> middle value is -2.
Constraints
  • · -10^5 <= num <= 10^5
  • · findMedian() is only called after at least one element has been added.
  • · At most 5 * 10^4 calls will be made to addNum and findMedian.
  • · Each median answer within 1e-5 of the true value is accepted.
Session phases
A · Clarify
B · Approach
C · Complexity
D · Edges
E · Code
F · Tradeoff
G · Score
Phase A — Clarify
Ask questions about input bounds, types, and edge constraints.
Ask the coach clarifying questions about the problem.
When you've covered this phase, advance to the next.