Sliding Window Rate Limiter
Hard · Classes
APIs protect themselves with rate limits like "at most 5 requests per 10 seconds per user". Code that reads the real clock is hard to test, so a common trick is to inject the clock: the limiter receives a clock function and calls clock() whenever it needs the current time.
Write a class RateLimiter(limit, window, clock) with a method allow(key) that returns True or False:
- each key (a user) has its own limit
- a request at time t is allowed when fewer than limit allowed requests for that key happened at times s with t - window < s <= t
- rejected requests do not count
- times are whole numbers and never go backwards
The driver run_limiter(limit, window, requests) is already written. Each request is [time, user]: the driver sets its fake clock to time and calls allow(user). It returns the list of answers.