#12MediumDesign· Sliding Window Log

Design a Sliding Window Rate Limiter

Build a rate limiter that admits at most `limit` requests in any time window of length `window`. Implement the class `RateLimiter`: - `RateLimiter(limit, window)` creates a limiter for a single client. - `allow(timestamp)` is called once per incoming request and returns `true` if the request is admitted, `false` if it is rejected. A request at time `t` is admitted if and only if **fewer than** `limit` previously *admitted* requests have timestamps in the half-open interval `(t - window, t]`. Rejected requests are not recorded and never count against later requests. Timestamps are integers and arrive in non-decreasing order; several requests may share a timestamp. **Test format.** `operations[i]` names the call and `arguments[i]` holds its arguments. The first operation is the constructor. The expected output lists each call's return value, with `null` for the constructor.

Input format

operations: array of strings ("RateLimiter", "allow"), arguments: array of argument arrays ([limit, window] for the constructor, [timestamp] for allow)

Output format

Array: `null` for the constructor, then a boolean for each `allow` call

Examples

Input: operations = ["RateLimiter", "allow", "allow", "allow", "allow", "allow", "allow", "allow", "allow"], arguments = [[3, 10], [1], [2], [3], [4], [11], [12], [13], [13]]

Output: [null, true, true, true, false, true, true, true, false]

The first three requests fill the window; the request at 4 is rejected. At 11 the window (1, 11] contains only the admitted requests at 2 and 3, so it is admitted, and so on. The second request at 13 finds 11, 12 and 13 already admitted in (3, 13].

Input: operations = ["RateLimiter", "allow", "allow", "allow", "allow", "allow", "allow", "allow"], arguments = [[2, 10], [0], [1], [2], [3], [10], [11], [12]]

Output: [null, true, true, false, false, true, true, false]

Rejected requests at 2 and 3 are not recorded. At 10 the window (0, 10] only contains the admitted request at 1, so it is admitted.

Constraints

1 <= limit <= 10^4
1 <= window <= 10^9
0 <= timestamp <= 10^9, non-decreasing across calls
At most 10^5 calls to allow.

Study first

#design
#queue
#sliding-window
#rate-limiting