Remove Duplicates in Order and Keep the Latest Items

Write two helpers for a stream of event keys. One drops repeated keys but keeps the order they first appeared in. The other remembers only the most recent items.

Remove duplicates in order

dedupe_preserving_order(items: Iterable[str]) -> list[str] returns each distinct string once, in the order it first appears.

assert dedupe_preserving_order(iter(["b", "a", "b", "", "A"])) == ["b", "a", "", "A"]
assert dedupe_preserving_order(iter([])) == []

• Read the input once. It can be a generator, which you cannot read twice.
• Keep each string exactly as it is. "a" and "A" are different, and "" is a value like any other.

The starter sorts the keys, which loses their order. Checking each key against the output list gives the right answer but is far too slow. With 200,000 distinct keys it makes about 20 billion comparisons. Keep a set of the keys you have seen next to the output list.

Keep a sliding window

Fill in the generic class SlidingWindow[T]:

• SlidingWindow(maxlen) starts empty and holds at most maxlen items. A maxlen of zero keeps nothing. A negative maxlen raises ValueError.
• push(item) adds the item and returns None. If the window is full, the oldest item drops out.
• oldest() returns the oldest item without removing it, or None when the window is empty.
• len(window) returns the number of items it holds.

Store the items in deque(maxlen=maxlen). It drops the oldest item for you, and it raises the ValueError for a negative maxlen.

recent: SlidingWindow[int] = SlidingWindow(2)
for item in [10, 20, 30]:
    recent.push(item)
assert len(recent) == 2
assert recent.oldest() == 20
assert recent.oldest() == 20  # reading does not remove it

What the driver reports

Keep solve(n, modulus, window, pushes) as it is. It removes duplicates from n generated keys of the form f"k{(i * 48271) % modulus}". Then it pushes the numbers 0 to pushes - 1 into a window of size window. It returns:

• count is the number of distinct keys.
• head and tail hold the first five and the last five distinct keys. With five or fewer keys, both hold the whole list.
• oldest and size are the window's oldest item and its length.

The largest test has 200,000 distinct keys and 500,000 pushes. Your submission must pass mypy --strict.