Sliding-Window Counter (Streaming Feature)

Background

Real-time fraud features are streaming aggregates: number of transactions in the last 5 minutes, geo-hops in the last hour, etc. Each new event updates the count without rebuilding from scratch — the canonical structure is a sliding-window counter backed by a deque of timestamps.

Problem statement

Implement SlidingCounter(window_seconds) with:

• add(timestamp) — record an event at this time (append to the deque).
• count(now) — return the number of events with now - window_seconds <= timestamp <= now. Evict any deque entries with timestamp < now - window_seconds.

Input

• window_seconds — float >= 0, the window width.
• add(timestamp) — float or int.
• count(now) — float or int. Returns events in $[\text{now} - W,\ \text{now}]$ inclusive.

Output

• add returns None.
• count returns int.

Examples

Example 1 — basic count

c = SlidingCounter(60)
c.add(0); c.add(30); c.add(70); c.add(120)
c.count(120) → 2   (only timestamps 70 and 120 are in [60, 120])

Example 2 — all in window

c = SlidingCounter(100)
for t in 0..4: c.add(t)
c.count(4) → 5

Example 3 — zero-length window keeps only exact-now events

c = SlidingCounter(0)
c.add(10); c.add(11)
c.count(11) → 1   (only the event at 11)

Example 4 — persistent eviction across count calls

c = SlidingCounter(10)
c.add(0); c.add(20); c.add(25)
c.count(20) → 1   (only event 20 in [10, 20]; 25 is future)
c.count(25) → 2   (events 20, 25 in [15, 25])

Example 5 — future events don't count yet

c = SlidingCounter(60)
c.add(100)
c.count(50) → 0   (event hasn't happened)
c.count(100) → 1

Example 6 — negative window raises

SlidingCounter(-1) → ValueError

Constraints

• window_seconds >= 0. ValueError otherwise.
• Timestamps may arrive in any order, but the typical case is monotone.
• Each count(now) evicts entries with timestamp < now - window_seconds.
• Counted entries must satisfy timestamp <= now (no counting future events).

Notes

• Why deque. collections.deque gives O(1) append and O(1) popleft. For monotone-arriving timestamps, the amortised cost per add + count is O(1).
• Production refinements. Add a max size cap, store (timestamp, value) tuples for sum-window rather than count-window, and shard by hash of unit ID for distributed deployment.