# Holding the Center > The middle value keeps moving as new data arrives. Canonical URL: Domain: Python · Difficulty: hard · Seniority: L5 ## Problem A latency monitor emits a reading after every request, and a live dashboard refreshes the median of all readings seen so far each time one arrives. Given `stream`, the readings in arrival order, return the running median after each reading, taking the average of the two middle values whenever an even number of readings has arrived. Each median comes back as a float, and a stream of a single reading reports that reading itself. ## Worked solution and explanation ### What this really is Strip the dashboard framing and this is the streaming-median problem: you need the middle of a growing multiset, recomputed on every arrival, without ever re-sorting. The trap is reaching for `sorted(seen)[mid]` inside the loop, which is O(n log n) per element and O(n squared log n) overall. What separates a senior answer is noticing you only ever need the two values straddling the middle, so you keep the lower half and the upper half as separate structures and read the boundary in constant time. > **Trick to solving** > > Split the stream into two halves: a max-heap for the lower half and a min-heap for the upper half. The median is always at the top of one or both heaps. Python's `heapq` is a min-heap only, so push negated values to fake a max-heap. --- ### Break down the requirements #### Step 1: Maintain two heaps: max-heap for the lower half, min-heap for the upper half The max-heap (`lo`) holds elements at or below the median. The min-heap (`hi`) holds elements above it. Because `heapq` is a min-heap, negate every value going into `lo` so its top is the largest of the lower half. #### Step 2: Route each value through both heaps Push to `lo` first, then immediately move `lo`'s top into `hi`. This guarantees every element in `lo` is smaller than every element in `hi` before you worry about sizes. #### Step 3: Rebalance after each insertion The heaps may differ in size by at most one. If `hi` ends up larger, move its top back into `lo` so `lo` is never smaller than `hi`. #### Step 4: Read the median off the tops If `lo` is the larger heap, its top is the median, and you wrap it in `float()` so an odd-count answer reports as a float like the even case. If the sizes are equal, average the two tops (division already yields a float). Both reads are constant time. --- ### The solution **Two-heap streaming median tracker** ```python import heapq def compute_running_median(stream): lo = [] # max-heap (negated) for the lower half hi = [] # min-heap for the upper half result = [] for num in stream: heapq.heappush(lo, -num) heapq.heappush(hi, -heapq.heappop(lo)) if len(hi) > len(lo): heapq.heappush(lo, -heapq.heappop(hi)) if len(lo) > len(hi): median = float(-lo[0]) else: median = (-lo[0] + hi[0]) / 2 result.append(median) return result ``` *float(-lo[0]) keeps the odd-count median a float, matching the even-count average.* > **Time and space complexity** > > **Time:** O(n log n) total. Each arrival does up to three heap operations, each O(log n). > > **Space:** O(n) for the two heaps combined. > **Interviewers watch for** > > The tell is whether you can explain why negation simulates a max-heap. Storing `-x` means the smallest stored value corresponds to the largest original value, so `-lo[0]` recovers the true maximum of the lower half. > **Common pitfall** > > Pushing straight into the heap you think it belongs in. The invariant only holds because every value goes into `lo` first, then to `hi`, then gets rebalanced. Skip that funnel and a value can land in the wrong half, silently corrupting every later median. The quieter miss is returning `-lo[0]` raw: an odd-count median then comes back as an int and breaks the dashboard's one-type contract. --- ## Common follow-up questions - What if you needed to support removing elements from the stream? _(Tests lazy deletion with a hash map tracking removed elements.)_ - How would you handle this if the stream had billions of elements? _(Tests approximate median algorithms like t-digest or reservoir sampling.)_ - What if medians needed to be computed over a sliding window? _(Tests combining the two-heap approach with window expiration logic.)_ - Why not use a balanced BST instead of two heaps? _(Tests trade-off analysis: BSTs give O(log n) median too but with higher constant factors in Python.)_ ## Related - [All practice problems](https://datadriven.io/problems) - [Mock interview mode](https://datadriven.io/interview/holding_the_center) - [Python Interview Questions](https://datadriven.io/python-interview-questions) - [Data Engineering Interview Prep Guide](https://datadriven.io/data-engineer-interview-prep) - [Daily Challenge](https://datadriven.io/daily) --- Source: DataDriven (https://datadriven.io). DataDriven is the data engineering interview community. Live code execution in SQL, Python, and Spark sandboxes. Every feature is open to every member.