Two limiters
An alert service promises a subscriber no more than L messages in W seconds. The developers argue about how to ensure this and test two methods on the same stream of events.
- A clock-hour window. Time is divided into intervals [kW, (k + 1)W). In each interval the first L events pass and the rest are dropped.
- A token bucket. The bucket holds up to L tokens, starts full, and gains one token every W/L seconds (W is divisible by L). An event passes if the bucket has a whole token, and takes it.
For each method print how many events passed, and how many events that passed fell into the busiest W seconds: into the interval [s, s + W) for the worst s. The tests include alerts about earthquakes of magnitude 5 or more for 2015–2025.
Input
The first line holds n, L and W (1 ≤ n ≤ 2·105, 1 ≤ L ≤ W ≤ 106, W divisible by L). The second holds the moments of the events in seconds, in non-decreasing order: integers from 0 to 109; several events may come in the same second.
Output
Two lines, for the clock-hour window and for the bucket: the number of events that passed and the largest number that passed in some W seconds.
Examples
Example 1
6 2 10 8 9 10 11 12 25
5 4 3 2
Example 2
10 3 60 0 0 0 0 30 59 60 61 62 200
7 3 7 5
Limits
- Time · Python
- 3000 ms
- Time · Go
- 1000 ms
- Memory
- 256 MB
- Judging
- 8 tests
Walkthrough
Open it step by step: each step gives away a little more. You can jump straight to the solution, but a problem solved with one hint stays with you longer.
1Hint 1
The clock-hour window promises “no more than L per interval”. Does that mean “no more than L in any W seconds”? Look at the first example: what happens at the boundary between intervals?
2Hint 2
The bucket is convenient to keep in integers: instead of a fractional number of tokens, store the moment when the bucket would be full again.
3The idea
The clock-hour window is a counter plus the number of the current interval, t div W. The bucket is the GCRA algorithm: let I = W/L and tat be the time when the bucket would be full; an event at moment t passes if t ≥ tat − (L − 1)·I, and then tat ← max(tat, t) + I. The busiest W seconds among the events that passed are found with two pointers: for each event that passed, move the left pointer while it lags by more than W − 1 seconds.
4Walkthrough
Why GCRA is a bucket. The number of tokens at moment t is L − (tat − t)/I if tat > t, and L otherwise: each event that passes moves the “full bucket time” one interval forward. A whole token is available when tat − t ≤ (L − 1)·I. Network devices compute the bucket exactly this way, without fractions and without a timer.
In the first example L = 2, W = 10: the events at 8 and 9 seconds pass in the first interval, those at 10 and 11 in the second, and all four fit in the interval [8, 18), twice the limit. This is not an implementation bug but a property of the method: in the worst case the clock-hour window lets through 2L in W seconds. The bucket does not keep “L in any W seconds” either: it gives away its reserve of L tokens at once and L more over the next W seconds. The difference is that for the bucket this is the promise itself: at most L + T/I pass in any T seconds; more in the article on rate limiting. On the July 2025 burst the clock-hour window lets through up to 19 alerts in an hour with a limit of 10.
4+Solution
5Complexity
O(n) for both methods and for finding the busiest W seconds.
6Common mistakes
- Taking the busiest W seconds to be the busiest clock interval. No: an interval boundary cuts through them. The first example.
- Fractional tokens in floating point. It will work, but with coinciding moments and long streams the error accumulates; integers are more reliable.
- A bucket that starts empty. By the statement it starts full.
- A window [t − W, t] instead of [s, s + W). Events exactly W seconds apart do not fall into one window.