Stateful Stream Processing And Time Scheduling

What's being tested

These problems test stateful stream processing: applying events in deterministic time order while maintaining per-entity state such as balances, locks, fraud counters, schedules, or notification queues. Interviewers look for clean data structures, explicit ordering rules, and edge-case handling around time, retries, conflicts, and mutations.

Patterns & templates

• Sort-then-scan event streams — events.sort(key=(ts, tie_breaker)), then single pass; usually O(n log n) time, O(k) state.

• Per-key state maps — use dict[(account_id, currency)] -> balance or dict[user_id] -> schedule; initialize defaults carefully.

• Priority queue scheduler — heapq by (next_run_at, stable_id) for due jobs; push updated recurrence after processing.

• Interval / TTL rules — store active rules by start <= ts < end; expire with min-heaps or ordered scans to avoid stale decisions.

• LRU eviction — combine dict plus doubly linked list or OrderedDict; get, put, and eviction are O(1).

• Deterministic conflict resolution — define tie-breakers for same timestamp: cancellation before creation, rule update before auth, rejection before overdraft.

• Timezone-safe scheduling — convert user-local wall time with zoneinfo; store canonical UTC instants; handle DST gaps and duplicated hours explicitly.

Common pitfalls

Pitfall: Processing input order as truth instead of sorting by timestamp produces wrong balances, fraud decisions, and email order.

Pitfall: Treating recurring schedules as precomputed infinite lists can explode memory; generate the next occurrence lazily.

Pitfall: Ignoring idempotency or duplicate event IDs leads to double-charged balances, duplicate notifications, or repeated lock acquisition.

Practice these

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