โ† Amazon questions
CodingReported in a candidate post, Jul 2025

Median of a running stream of integers

Filed under Amazon

Free read 1 of 3

Confirm the number of calls, how frequent each operation is, duplicates, negative numbers and whether values lie in a bounded range.

The question

Design a data structure that receives a continuous stream of integers and can return the median of all numbers seen so far at any time. Provide add(num) and median(). If the count is even, the median is the average of the two middle values.

Constraints

  • Values are integers within the 32-bit range
  • add and median may be called many times in any order

Examples

Input
add(1), add(2), median(), add(3), median()
Output
1.5, then 2
Why
After [1,2] the median is 1.5, after [1,2,3] it is 2.

Approach

  1. Confirm the number of calls, how frequent each operation is, duplicates, negative numbers and whether values lie in a bounded range.

Solution

O(log n) add, O(1) median, O(n) space

Python
import heapq
class MedianFinder:
    def __init__(self):
        self.lo = []                       # max-heap (stored as negatives)
        self.hi = []                       # min-heap

    def add(self, num):
        heapq.heappush(self.lo, -num)
        heapq.heappush(self.hi, -heapq.heappop(self.lo))   # move largest of lo to hi
        if len(self.hi) > len(self.lo):                    # keep lo >= hi in size
            heapq.heappush(self.lo, -heapq.heappop(self.hi))

    def median(self):
        if len(self.lo) > len(self.hi):
            return float(-self.lo[0])
        return (-self.lo[0] + self.hi[0]) / 2

Tips

  • What they are testing: Whether you can maintain an invariant between two structures, and know the heap approach and its balanced-tree alternative.
  • Common mistake: Re-sorting on every query, or forgetting to rebalance the heaps so the median is read from the wrong top.

Related Amazon questions

Collected from public candidate posts and coding forums. Updated Nov 2026.