Quant Memo
Coding/●●●●●

How many fills in the last five minutes?

Design a class that records fill events by timestamp (seconds, non-decreasing) and, on demand, returns how many fills occurred in the last 300 seconds (a trailing 5-minute window ending at the query time).

c = HitCounter(window=300)
c.hit(1)
c.hit(2)
c.hit(300)
c.count(300)  -> 3        # timestamps 1, 2, 300 all within [1, 300]
c.count(301)  -> 2        # timestamp 1 is now older than 300s (301 - 300 = 1 excludes it)

hit and count should each run in amortized O(1)O(1) and use O(w)O(w) memory, where w is the number of events inside the window.

Your answer

This one is open-ended. Work it through, then check your reasoning against the full solution.

More Coding questions