Temporal Event Processing and Interval Logic

What's being tested

These problems test precise interval logic and time-series grouping: mapping events to intervals, resolving ties/boundaries, and maintaining per-entity state over time. Interviewers want to see correct ordering (sorting vs streaming), single-pass reasoning, and careful handling of open/closed intervals and missing data.

Patterns & templates

• Sort-then-scan: sort events by timestamp, then scan once; total cost O(n log n) for sort, O(n) for scan, O(k) extra per-key state.

• Sweep-line / event delta: convert interval starts/stops to +1/-1 events and aggregate with a running sum for concurrent-count problems.

• Sliding window / deque: maintain a time-ordered collections.deque for 60s counts or TTL-based windows, amortized O(1) per event.

• Two-pointer on timestamps: use left/right pointers on sorted arrays for fixed-length windows — O(n) time, watch empty-window edge cases.

• Per-key single-pass state (hash-map): track running minima/maxima or last-seen event per symbol/user; clear state when groups end.

• Binary-search interval lookup: store sorted interval boundaries and use bisect to find containing interval in O(log m) per query.

• Handle open intervals and missing end-times: treat absent end as +∞ or use sentinel; be explicit about inclusive/exclusive boundaries.

Tip: declare and stick to an inclusive/exclusive rule up front (e.g., [start, end) unless interviewer specifies otherwise).

Common pitfalls

Pitfall: Misinterpreting boundary semantics — treating both ends as inclusive can double-count events occurring exactly at a boundary.

Pitfall: Assuming input is time-ordered — failing to sort or to document streaming constraints leads to incorrect single-pass logic.