Basics: count hits in the last N seconds

easy basics ~10 min

Build HitCounter(window), where window is a positive number of seconds.

hit(t) records one event at integer second t.
count(t) returns how many hits happened in the last window seconds, counting back from t: the hits with t - window < time <= t. A hit exactly window seconds old has dropped out.

Across all calls, t never decreases, and several hits can share the same second.

c = HitCounter(10)
c.hit(1); c.hit(1); c.hit(5)
c.count(5)    # 3
c.count(10)   # 3   (1 is 9 seconds old: still inside)
c.count(11)   # 1   (the two hits at 1 are 10 seconds old: gone)
c.count(15)   # 0

Both methods should be fast even after millions of hits: don't rescan every hit on each count.

Show hint

keep the timestamps in a collections.deque and, on each call, pop from the left while the oldest one is <= t - window; the answer is then len(deque).

Topic: Rolling windows and rate counters. QPS over the last N seconds, hit counters, rate limiters.