Point72's Streaming Median Question

Point72's coding rounds often start with a clean streaming problem and then squeeze the resources until the exact answer stops fitting. The median of a data stream is the classic: two heaps to start, then a memory limit, then many machines. Here is the full question, Java for each part, and a detailed rubric.

The question

Part 1 · Two heaps

Hold the lower half in a max-heap and the upper half in a min-heap, kept balanced to within one element. The median is the top of the larger heap, or the average of the two tops. Insert is O(log n), read is O(1).

import java.util.*;

class MedianFinder {
    private final PriorityQueue<Integer> low  = new PriorityQueue<>(Collections.reverseOrder()); // max-heap
    private final PriorityQueue<Integer> high = new PriorityQueue<>();                            // min-heap

    void addNum(int num) {
        low.offer(num);
        high.offer(low.poll());                 // pass the largest of the low half up
        if (high.size() > low.size()) low.offer(high.poll());   // keep low >= high in size
    }

    double findMedian() {
        if (low.size() > high.size()) return low.peek();
        return (low.peek() + (double) high.peek()) / 2.0;
    }
}

Part 2 · Bounded memory, approximate

If you cannot keep every number, keep a fixed-size histogram instead. Each value increments one bucket; the median is the bucket where the cumulative count crosses half. Memory is constant in the number of buckets, independent of the stream length, at the cost of bucket-width error.

class ApproxMedian {
    private final double lo, width; private final long[] buckets; private long count;

    ApproxMedian(double lo, double hi, int numBuckets) {
        this.lo = lo; this.width = (hi - lo) / numBuckets; this.buckets = new long[numBuckets];
    }

    void add(double x) {
        int b = (int) ((Math.min(Math.max(x, lo), lo + width * buckets.length) - lo) / width);
        if (b == buckets.length) b--;           // clamp the top edge
        buckets[b]++; count++;
    }

    double median() {
        long target = (count + 1) / 2, cum = 0;
        for (int b = 0; b < buckets.length; b++) {
            cum += buckets[b];
            if (cum >= target) return lo + (b + 0.5) * width;   // bucket midpoint estimate
        }
        return lo + width * buckets.length;
    }
}

For unknown or long-tailed ranges, a t-digest is the better sketch: it keeps more resolution near the median and bounds memory by the number of centroids. The histogram is the version you can write on a whiteboard in two minutes.

Part 3 · Merge across machines

The histogram is mergeable. Each machine builds one over the same bucketing, then you sum the bucket arrays element-wise and read the median off the combined histogram. T-digests merge the same way by combining centroids, which is why these sketches are the standard answer for distributed quantiles.

// Combine partial histograms (same lo, hi, numBuckets) into a global estimate.
static long[] merge(long[] a, long[] b) {
    long[] out = new long[a.length];
    for (int i = 0; i < a.length; i++) out[i] = a[i] + b[i];
    return out;                                  // read the median off 'out' as in Part 2
}

How Point72 scores it

Point72 interview FAQ