Count requests in the last five minutes

Question

Build a counter over timestamped events (timestamps arrive non-decreasing):

record(t), log a request at time t.
count_recent(t), return how many requests fall in the trailing window (t - 300, t], that is, within the last 300 seconds.

record(1); record(100); record(3001); record(3002)
count_recent(3002)  -> 2     # only 3001 and 3002 are within (2702, 3002]

Make count_recent run in $O(\log n)$ .

Accepted Answer

Because timestamps are non-decreasing, the log is already sorted, so the window's two edges are two binary searches. The count is (index after the right edge) - (index after the left edge): bisectright(times, t) finds the first entry past t, and bisectright(times, t - 300) finds the first entry past the exclusive left edge t - 300. Their difference is the number of entries in (t - 300, t]. Tracing times = [1, 100, 3001, 3002], countrecent(3002) with window 300: the left edge is t - 300 = 2702; bisectright(times, 2702) = 2 (past 1 and 100), and bisectright(times, 3002) = 4. Count 4 - 2 = 2. Ea…

Count requests in the last five minutes

Your answer

More Coding questions