Order-preserving dedupe and a real sliding window

Two containers, two complexity contracts, and a starter that gets each of them half right.

def dedupe_preserving_order(items: Iterable[str]) -> list[str]: ...

class SlidingWindow[T]:
    def __init__(self, maxlen: int) -> None: ...
    def push(self, item: T) -> None: ...
    def oldest(self) -> T | None: ...
    def __len__(self) -> int: ...

dedupe_preserving_order must keep the first occurrence of each item, in the order it first appeared, over a single pass of an Iterable (it may be a generator, so you get one shot at it). The starter returns sorted(set(items)): fast, and it throws the order away. The other reflex — if item not in out against the output list — keeps the order and is O(n²). You need both properties at once, which takes one auxiliary set.

SlidingWindow keeps at most maxlen items, discarding the oldest. oldest() returns the oldest retained item, or None when empty. The starter accepts maxlen and then ignores it, which is an unbounded buffer wearing a window’s name — a shape that appears in real services as a slow memory leak, usually because someone refactored the trim away.

solve runs both:

def solve(n: int, modulus: int, window: int, pushes: int) -> dict[str, object]: ...

It deduplicates a generated stream of n keys of the form f"k{(i * 48271) % modulus}", pushes pushes integers through a window of size window, and returns {"count", "head", "tail", "oldest", "size"} — the deduplicated length, its first and last five entries, the oldest item still in the window, and the window’s length.

The scale is part of the specification. One hidden case runs 200,000 stream items with 200,000 distinct values and 500,000 pushes. A seen: list implementation performs about 2×10¹⁰ comparisons there and does not finish inside the time limit — no assertion mentions time, and it does not need to, because a quadratic solution simply never returns. Measured for calibration: list-based dedupe at n=4,000 took 38.92 ms against 0.083 ms with a set.

Note the generic class syntax: class SlidingWindow[T] is PEP 695, available since 3.12, with no TypeVar boilerplate and variance inferred. oldest() returning T | None is what forces the caller to handle the empty window, which is the case that produces IndexError in untyped code.

Your submission must pass mypy --strict.