Problem. Design MedianFinder with add_num(x) and find_median(). The median is the middle value of all numbers
added so far, or the mean of the two middle values when the count is even.
add 1, add 2 → median 1.5
add 3 → median 2.0
Lesson 5.9 found the median of two static sorted arrays. Here the data arrives, and each query must be cheap. The trick is that the median only needs the boundary between the lower and upper halves, never the full order inside them.
ML context. Medians and percentiles are the honest summaries of skewed quantities: request latency, tokens per response, gradient norms, per-batch loss (a mean is dragged by one huge outlier). Monitoring computes them online as samples stream in, usually over a sliding window (Change A) and for several percentiles (Change B), and at fleet scale approximately (Change D).