Temporal Event Processing And Interval Algorithms

What's being tested

This tests interval algorithms and timestamp-ordered event processing: sorting ranges, merging boundaries, replaying events deterministically, and preserving accounting invariants under out-of-order input. Interviewers are probing whether you can turn ambiguous time semantics into precise code with clear complexity and edge-case handling.

Patterns & templates

• Sort-then-scan interval merge — sort by start, maintain current [lo, hi]; O(n log n) time, O(n) output space.

• Endpoint semantics — decide whether [a,b] and [b,c] merge; closed intervals usually merge on next.start <= cur.end.

• Zero-length intervals — handle [t,t] explicitly; they may represent instantaneous events, empty ranges, or valid closed intervals.

• Event replay ledger — store events sorted by (timestamp, tie_breaker, sequence_id) and recompute balances deterministically after inserts.

• Tie-breaking rules — define add-before-charge or charge-before-add at equal timestamps; encode it directly in the sort key.

• Expiring credits — model credits as lots with amount, created_at, expires_at; consume using FIFO/earliest-expiry via queue or heap.

• Complexity tradeoff — full replay is simple but O(n) per insert; balanced trees or indexed timelines improve repeated historical queries.

Common pitfalls

Pitfall: Treating touching intervals inconsistently; state whether end == start means overlap before writing merge logic.

Pitfall: Sorting only by timestamp in ledgers; equal-time adds and charges need deterministic tie-breaking to avoid flaky balances.

Pitfall: Mutating current balance incrementally for out-of-order events without replay or correction; historical inserts can change all future states.

Practice these

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