Event Filtering, Deduplication, And Time Windowing

What's being tested

These problems test event-stream processing: filtering records by type and field validity, maintaining global state with set, and propagating information across events in order. You must also demonstrate stable sorting, identifier-based deduplication, timestamp windowing, and the ability to analyze time and space complexity.

Patterns & templates

• Use a global set for distinct nonempty PII values; membership and insertion are amortized O(1), with O(U) space for U unique values.

• Filter early by event type and recognized fields, then normalize or validate values before adding them to state.

• Process events chronologically with sorted(events, key=lambda e: e["timestamp"]); preserve input order for equal timestamps when required.

• For deduplication by identifier, use a set of seen IDs or a dictionary retaining the first/last record, depending on requirements.

• Implement time windows with timestamp >= start and timestamp <= end; explicitly confirm inclusive versus exclusive boundaries.

• Fraud propagation requires checking suspicious PII before mutating state; classify the current event first, then add its values.

• A one-pass scan after sorting is typically O(n log n) time and O(n + U) space; avoid nested comparisons that become O(n²).

Common pitfalls

Pitfall: Counting repeated values, empty strings, None, or unrecognized fields instead of filtering them before set insertion.

Pitfall: Adding an underwriting event’s PII before checking it, which incorrectly makes the event suspicious based on its own newly introduced value.

Pitfall: Sorting without a deterministic tie-breaker or silently choosing the wrong timestamp-window inclusivity.

Practice these

The practice cards below cover the canonical variants — solve all of them and time yourself.