Skip to content
Onsite
17 / 20

Sliding Window Rate Limiter

MediumP2Coding

Design a sliding-window rate limiter that allows at most limit calls per key within any window of windowMs milliseconds.

Implement the SlidingWindowRateLimiter class:

  • SlidingWindowRateLimiter(limit, windowMs) sets the policy, shared by all keys.
  • allow(key, timestamp) returns true and counts the call if fewer than limit calls for that key were allowed in the window (timestamp - windowMs, timestamp]; otherwise returns false.

Rejected calls are not counted. Keys are independent. Timestamps (in milliseconds) never decrease between calls.

Example 1

Input
["SlidingWindowRateLimiter","allow","allow","allow","allow","allow","allow"] [[2,1000],["u",0],["u",100],["u",200],["u",1000],["u",1100],["u",1101]]
Output
[null,true,true,false,true,true,false]
Why
The third call is rejected. At time 1000 the call from time 0 has left the window, so a slot is free again.

Constraints

  • 1 <= limit <= 10^4
  • 1 <= windowMs <= 10^9
  • 0 <= timestamp <= 10^12, non-decreasing
  • At most 10^5 calls.

Hints

Run checks the 2 visible tests, Submit all 8.