Coding: Time-Window Counters, Heaps, And Stateful Stores

What's being tested

Candidates must show they can build streaming time-window counters, implement top-k or priority-based summaries with heaps, and reason about stateful store choices (in-memory vs persisted) for real-time ML features. Interviewers probe algorithmic correctness, amortized complexity, memory vs accuracy tradeoffs, and operational safety (eviction, clock skew, persistence).

Patterns & templates

• Sliding-window deque: use collections.deque of (ts, value) pairs, pop left while ts < now-window; amortized O(1) per event.

• Fixed-bin circular buffer: partition window into B buckets, update bucket index = floor(ts/bin_width)%B, O(1) writes, memory = O(B).

• Exponential decay (EWMA): single-value O(1) per update, use alpha = 1 - exp(-Δt/τ) for time-aware decay.

• Min-heap top-k: keep size-k min-heap via heapq; compare and replace lowest in O(log k), overall O(n log k) streaming cost.

• Approximate sketches: Count-Min Sketch for heavy-hitters — memory O(1/ε log 1/δ), provides one-sided error guarantees.

• Stateful store pattern: keep hot-state in memory, checkpoint to Redis/RocksDB, persist on TTL or snapshot to avoid data loss.

• Background eviction & compaction: scheduled sweep or lazy eviction on access; avoid full scans by using expiration indices or time-ordered lists.

Common pitfalls

Pitfall: keeping per-event raw timestamps without aggregation leads to unbounded memory growth; use bucketing or summarization.

Pitfall: using a global heap for all items instead of size-k heap causes unnecessary O(n log n) work and memory pressure.

Pitfall: comparing wall-clock timestamps across hosts causes subtle bugs; use monotonic timers (e.g., time.monotonic()) for durations.

Practice these

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