Rate limiter with multiple sliding-window rules

Build a rate limiter that enforces several rules at once.

Each rule is a pair (limit, window): at most limit accepted requests may fall in any window of window time units. Use the half-open window (t - window, t], so a request accepted at time s stops counting at exactly s + window.

Implement RateLimiter:

• RateLimiter(rules: List[Tuple[int, int]]): sets up the limiter. There is at least one rule, every limit >= 0 and every window > 0.
• allow(t: int) -> bool: a request arrives at time t. Accept it and return True only if every rule still has room. Otherwise return False. A rejected request is not counted by any rule.
• next_allowed(t: int) -> int (part 2): return the earliest time >= t at which a request would be accepted, without recording anything.

Calls arrive with non-decreasing t. Several requests may share a timestamp. Aim for time per call proportional to the number of rules, and memory that does not grow with total traffic.

Example 1

rules = [(3, 10), (5, 60)]
allow(1)  -> True
allow(2)  -> True
allow(3)  -> True
allow(4)  -> False   # 3 accepted in (-6, 4]
allow(11) -> True    # only 2 and 3 are in (1, 11]
allow(12) -> True    # 5 accepted in the last 60
allow(13) -> False   # 10-unit rule has room, 60-unit rule is full
next_allowed(22) -> 61   # the request at t=1 leaves the 60-unit window

Example 2

rules = [(2, 5)]
allow(0), allow(0), allow(0) -> True, True, False
allow(5), allow(5), allow(5) -> True, True, False

The rejected request at time 0 does not block the requests at time 5.

Be ready to discuss per-client limits, thread safety, and a version that queues requests instead of rejecting them.

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