Per-domain sliding-window rate limiter

A gateway receives requests one at a time, at most one per second. Each request names a domain. Build a rate limiter that keeps its state between calls and decides, for each request, whether to let it through.

Implement the DomainRateLimiter class:

class DomainRateLimiter:
    def __init__(self, limit: int, window: int) -> None: ...
    def should_allow(self, timestamp: int, domain: str) -> bool: ...

Rules

• A domain may have at most limit accepted requests in any window seconds. A request at time t shares a window with earlier accepted requests at times in (t - window, t]. A request exactly window seconds older is outside the window.
• should_allow returns True and records the request if the domain is under its limit. Otherwise it returns False.
• A rejected request does not count toward the limit.
• Domains are independent of each other.
• timestamp is an integer number of seconds and never decreases between calls.

Constraints: 1 <= limit <= 1000, 1 <= window <= 10^5, up to 10^6 calls and 10^5 distinct domains. Aim for amortized O(1) per call.

Example 1

limiter = DomainRateLimiter(limit=2, window=5)
should_allow(1, "a.com")  -> True
should_allow(2, "a.com")  -> True
should_allow(3, "a.com")  -> False   # 2 accepted in (−2, 3]
should_allow(4, "b.com")  -> True    # other domain
should_allow(5, "a.com")  -> False   # 1 and 2 are still in (0, 5]
should_allow(6, "a.com")  -> True    # 1 has left the window

Example 2

limiter = DomainRateLimiter(limit=1, window=10)
should_allow(0, "x.io")   -> True
should_allow(9, "x.io")   -> False
should_allow(10, "x.io")  -> True    # 0 is not in (0, 10]

Be ready to discuss: limits that also apply to parent domains (api.x.io counts toward x.io), freeing memory for idle domains, and running the limiter on many threads or machines.

Reconstructed from the reported question; details may differ from what interviewers ask.