Implement a sliding-window rate limiter

Sliding Window Rate Limiter

Design a rate limiter for a distributed system that restricts the number of requests a user can make within a rolling time window. Implement a class RateLimiter that processes incoming requests for a specific user_id.

Requirements

• The rate limiter must support a limit of max_requests per window_size (in seconds).
• The allow_request(user_id) method should return True if the request is permitted, and False otherwise.
• You must account for the sliding nature of the window (i.e., if the window is 60 seconds, a request at time T should be compared against the count of requests in [T - 60, T]).

Function Signature

class RateLimiter:
    def __init__(self, max_requests: int, window_size: int):
        # max_requests: max allowed requests per window
        # window_size: time window in seconds
        pass

    def allow_request(self, user_id: str) -> bool:
        # Returns True if request is allowed, else False
        pass

Examples

Example 1:

• max_requests = 2, window_size = 5
• allow_request("user1") -> True (T=1)
• allow_request("user1") -> True (T=2)
• allow_request("user1") -> False (T=3, limit reached)
• allow_request("user1") -> True (T=7, window is now [2, 7])

Constraints

• Time is represented by epoch timestamps in seconds.
• Assume a single-threaded environment for the implementation.
• Optimize for time complexity where possible.