Compute a Rolling Median with a Bounded deque

A dashboard shows the median of the last few readings and updates it as each reading arrives. Write rolling_median, which reads the values once, in order, and returns the median of every full window.

rolling_median([1.0, 3.0, 2.0, 8.0, 5.0], 3)
# windows [1.0, 3.0, 2.0], [3.0, 2.0, 8.0] and [2.0, 8.0, 5.0]
# returns [2.0, 3.0, 5.0]

What to write

def rolling_median(values: Iterable[float], window: int) -> list[float]: ...
def headroom(buffer: deque[float]) -> int: ...
def solve(values: list[float], window: int) -> dict[str, object]: ...

rolling_median(values, window):

• Read values once, in order. It may be a one-shot iterator, which is an iterator you can loop over only once, such as a generator or an open file. The article "Generators and One-Shot Iterators", later in this track, covers them.
• Keep at most window values in a deque(maxlen=window). The result list and a temporary copy for each median do not count toward that limit.
• Return one median per full window. For n values that is max(0, n - window + 1) medians.
• Compute each median with statistics.median. It returns the middle value, or the mean of the two middle values when the window size is even. Return floats.
• Raise ValueError when window < 1, before you read any input.

headroom(buffer):

• Return buffer.maxlen - len(buffer) for a deque with a limit, or -1 for a deque with no limit.
• buffer.maxlen is int | None, so check for None before you subtract.

solve(values, window) returns a dict with four keys:

• error: "" for a valid window, or "ValueError" when window < 1.
• medians: the list from rolling_median, or [] on error.
• tail: the last window values in their original order, or all of them if there are fewer. On error, it is [].
• headroom: the unused room in the tail deque, or -1 on error.

Build the tail with deque(values, maxlen=window). Unlike rolling_median, solve gets a list, which you can loop over more than once. So it may read the values once for the medians and again for the tail. Do not change the caller's list.

All values are finite floats. Your code must pass mypy --strict.

Edge cases

• Empty input, or fewer values than window, gives no medians.
• A deque with maxlen=0 has headroom 0.