The machine receives hit(timestamp) calls — timestamps arrive in strictly non-decreasing order — and getHits(timestamp) must return how many hits occurred in the window (timestamp − 300, timestamp]. Two data shapes work: a fixed-size ring buffer of 300 buckets, or a monotonic deque of raw timestamps.
The deque version is the cleanest mental model. hit appends the timestamp to the right. getHits first pops every timestamp from the left that is ≤ t − 300 — those are expired, and because timestamps are monotonic, once one is expired everything behind it is too. The remaining deque length is the answer. Amortized O(1) per call: each timestamp is pushed once and popped at most once.
The ring-buffer version is what a real production counter would use: an array of 300 buckets, each bucket holding (timestamp, count). hit writes into bucket t % 300 only if that bucket's stored timestamp equals t; otherwise the machine overwrites the bucket with (t, 1). getHits sums buckets whose stored timestamp is > t − 300. This gives O(1) worst-case time and O(1) memory — 300 buckets regardless of traffic — at the cost of a 300-entry scan per query.
The key invariant in both: the window is half-open, (t − 300, t], so a hit exactly 300 seconds old is already dead. Edge cases: hits at t=1 and a query at t=301 — the t=1 hit expires. Concurrent bursts of many hits at the same timestamp must all be counted — the deque handles this naturally; the bucket version must accumulate counts rather than overwrite.
from collections import deque
class HitCounter:
def __init__(self):
self.hits = deque()
def hit(self, timestamp):
self.hits.append(timestamp)
def getHits(self, timestamp):
while self.hits and self.hits[0] <= timestamp - 300:
self.hits.popleft()
return len(self.hits)