Skip to main content
ELYTE
HardAlgorithms & Data StructuresDebug

Debug the Live Median Tracker

A teammate built a live median tracker — `add(value)` inserts a number, `median()` returns the current median over everything inserted so far — using the standard two-heap technique. The code looks reasonable and the sm...

Start problemBrowse all problems

What you will practice

PythonSorting & SearchingHeap / Priority QueueInvariantsDebugging

Requirements

  • `add(value)` accepts any int or float and inserts it.
  • `median()` returns the median over all values inserted so far: the middle element for odd counts, the average of the two middle elements for even counts.
  • The median must be correct after every single `add`, not just at the end. (The judge checks after each step.)
  • Ascending sequences (`1, 2, 3, ...`) and descending sequences (`9, 8, 7, ...`) must both produce correct medians at every step.
  • After every `add`, the size invariant must hold: `len(lo) == len(hi)` or `len(lo) == len(hi) + 1`.
  • After every `add`, the ordering invariant must hold: every value in `lo` is `<=` every value in `hi`.

Starter files

median_tracker.pyEditable starter

What the judge checks

  • Runs in the python environment with the python-pytest runner.
  • Uses a 6000ms judge budget.
  • Behavior rules include: Median Correct For Odd Count, Median Correct For Even Count, Invariant Holds After Every Insert, Handles Descending Insert Sequence.

Constraints

  • Do not change the public API (`__init__`, `add`, `median`).
  • Keep using two heaps backed by `heapq` — don't replace the whole approach with sorted-list bisect.
  • `median` must run in O(1); `add` must run in O(log n).

Example behavior

Input
add(1); add(2); add(3)
Output
median() after each step: 1, 1.5, 2
Input
add(9); add(8); add(7); add(6)
Output
median() after each step: 9, 8.5, 8, 7.5

Follow-up

How would you extend this to support `remove(value)` efficiently — say, for a sliding-window median over a stream?