# Evolve Duplicate Detection for Sliding Windows and Read-Heavy Queries You are given a sequence of integer identifiers. Work through three versions of duplicate detection and explain the data structure, invariant, and complexity for each version. ### Clarifying Questions to Ask - Does “within a window” mean an index distance of at most `w`? - May the sequence be rebuilt in batches, or must individual updates be supported online? - In the read-heavy version, do queries vary only by `w` while the sequence stays fixed between rebuilds? ### Part 1 — Detect Any Duplicate Determine whether the sequence contains the same value at least twice. #### What This Part Should Cover - A set-based single pass and the invariant maintained after each element. - Expected time and space complexity, including the effect of hash-table assumptions. ### Part 2 — Detect a Nearby Duplicate For a supplied nonnegative integer `w`, determine whether two equal values occur at indices whose absolute difference is at most `w`. Use a sliding-window approach. #### What This Part Should Cover - Which indices are represented in the window before each lookup. - The exact order of lookup, insertion, and eviction, especially for `w = 0`. - Expected linear time and space bounded by the smaller of the input size and window size. ### Part 3 — Optimize Repeated Read-Heavy Queries Assume the sequence is fixed for many calls to `hasNearbyDuplicate(w)`, where only `w` changes. A batch replacement of the entire sequence is rare. Design preprocessing so each query is constant time, while a replacement may take linear time and the stored state remains linear in the sequence length. #### What This Part Should Cover - A sequence summary sufficient to answer every threshold query. - A linear rebuild that examines consecutive occurrences of each value. - Why the query becomes one comparison and why no smaller gap can be missed. ### What a Strong Answer Covers - The progression from a membership set to a bounded window and then to a precomputed global minimum distance. - Correct boundary behavior for empty input, unique values, adjacent duplicates, and `w = 0`. - The stated O(1) query, O(n) rebuild, and O(n) storage target for the read-heavy workload. - The limitation that incremental point updates would require a different, more complex structure. ### Follow-up Questions - How would you support individual point updates while keeping queries fast? - What changes if the query asks how many duplicate pairs fall within distance `w`? - How would adversarial hash collisions affect the expected complexity claims?