24. Flag Duplicate Audio Requests

Problem

A client can retry a TTS/STT request (a flaky network, a double-tap in a UI) and send effectively the same request again seconds later — request bodies that hash to the same fingerprint. Reprocessing it wastes GPU time when the first result can just be replayed.

Given a timestamped stream of incoming requests, each with a content fingerprint, flag which ones are duplicates of a request with the same fingerprint seen within the last dedup_window seconds.

Source: src/24_flag_duplicate_audio_requests.py

def flag_duplicate_audio_requests(
    requests: list[tuple[float, str]], dedup_window: float
) -> list[bool]: ...

>>> flag_duplicate_audio_requests([(0.0, "abc"), (0.5, "abc"), (5.0, "abc")], dedup_window=2.0)
[False, True, False]

Step-by-Step Approach

1. Since requests arrive in non-decreasing timestamp order, a single forward sweep with a hashmap suffices — no need to keep a full history per fingerprint.
2. Keep one hashmap entry per fingerprint holding only its most recently seen timestamp; because arrival order is time-sorted, the most recent sighting is always the closest possible prior match.
3. For each incoming (t, fingerprint), look up the fingerprint's last-seen time. If it exists and t - last_seen <= dedup_window, flag this request as a duplicate.
4. Regardless of the outcome, update the fingerprint's last-seen time to the current request's timestamp, so the next occurrence measures its gap from this one.
5. Append the True/False flag to the result list and continue; the whole pass is O(n) time and O(distinct fingerprints) space.

The key insight is that you only ever need the single most recent timestamp per fingerprint, not a full sliding-window history of every past occurrence — because the stream is time-sorted, an older occurrence of the same fingerprint can never be closer to the current request than the most recent one, so a plain hashmap replaces what might otherwise look like it needs a per-key deque.

Reference solution

def flag_duplicate_audio_requests(
    requests: list[tuple[float, str]], dedup_window: float
) -> list[bool]:
    # One hashmap entry per fingerprint holding only its most recent
    # timestamp is enough: since requests arrive in non-decreasing time
    # order, the most recent sighting is always the closest possible match,
    # so there's no need to keep a full history per fingerprint. O(n) time,
    # O(distinct fingerprints) space.
    last_seen: dict[str, float] = {}
    flags: list[bool] = []
    for t, fingerprint in requests:
        prev = last_seen.get(fingerprint)
        is_dup = prev is not None and (t - prev) <= dedup_window
        flags.append(is_dup)
        last_seen[fingerprint] = t
    return flags

Key Functions & Tricks

• dict.get(fingerprint) — returns None for a never-seen fingerprint without a separate existence check.
• Single hashmap keyed by fingerprint — O(1) amortized lookup/update per request.
• Updating last_seen unconditionally on every request — ensures the next occurrence measures its gap from the true most recent sighting, not a stale one.
• Relying on pre-sorted input to avoid a per-fingerprint deque — the detail that keeps this O(n) instead of needing a sliding-window structure per key.

How to Recognize This Pattern