Implement Sliding-Window Rate Limiter

Sliding-Window Rate Limiter

You are tasked with building a RateLimiter class that enforces a rate limit for a specific user. The goal is to allow a maximum of k requests within any rolling window of t milliseconds.

Implement the following interface:

class RateLimiter:
    def __init__(self, k: int, t: int):
        """
        Initializes the rate limiter with capacity k and window size t (in ms).
        """
        pass

    def allow_request(self, user_id: str, timestamp: int) -> bool:
        """
        Returns True if the request at 'timestamp' is allowed, False otherwise.
        Assume timestamps are provided in strictly increasing order.
        """
        pass

Constraints

• k (capacity) is a positive integer.
• t (window size) is a positive integer.
• timestamp is a positive integer.
• The solution should efficiently evict expired timestamps to save memory.

Examples

Example 1: Capacity k = 2, window t = 1000 ms.

• allow_request("user1", 100) -> True
• allow_request("user1", 500) -> True
• allow_request("user1", 1200) -> True (The request at 100 is evicted because 1200 - 1000 = 200, which is > 100)
• allow_request("user1", 1300) -> False (Only request at 500 and 1200 remain; at 1300, 500 is still within the window [300, 1300])

Edge Cases

• Concurrent calls for different user_ids.
• Requests arriving at the exact boundary of the window.
• High-frequency requests exceeding k.