Sliding Window And Time Window Counters

What's being tested

Candidates must demonstrate the ability to implement and reason about sliding-window algorithms and time-window counters over streams: correct incremental aggregation, memory/time tradeoffs, and robustness to timestamp issues. Interviewers probe whether you can pick the right data structure (queue, circular buffer, monotonic deque) and complexity bounds for high-throughput online counting or rate-detection tasks.

Patterns & templates

• Sliding-window (contiguous) — two-pointer expand/contract over arrays, O(n) time, O(1) extra space for fixed-size windows; handle empty-window edge cases.

• Fixed-size timestamp queue — collections.deque for append/pop timestamps, remove older-than-window, amortized O(1) per event, store counts or IDs.

• Bucketed time windows (circular buffer) — circular buffer of M buckets for window W, update bucket at ts % M, O(1) update; reset bucket on reuse.

• Monotonic deque for extrema — monotonic deque maintains candidate max/min in O(1) amortized per op, used for sliding max/min detection.

• Prefix-sum / difference arrays — precompute cumulative sums to answer many offline fixed-window queries in O(1) each; O(n) preprocessing.

• Approximate counters — CountMinSketch or exponential decay counters for low-memory, probabilistic counting; track error bounds vs memory.

• Time-decay / exponentially-weighted — use EWMA with factor α: $S_t = α x_t + (1−α) S_{t−1}$; constant memory for recency-weighted rates.

Common pitfalls

Pitfall: assuming strictly increasing timestamps — many streams have out-of-order or late events; you must decide tolerance or buffer/window adjustments.

Pitfall: reusing bucket without clearing — forget to store bucket's last-updated timestamp and you’ll mix old counts.

Pitfall: naive recompute per slide (O(k)) for large k — use incremental updates or monotonic structures to avoid TLE.

Practice these

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