Per-Client Request Throttle

Design a class Throttle that protects a service from clients that call it too often:

• Throttle(limit, window): each client may have at most limit accepted requests inside any window of window time units.
• allow(client, t) is called when client sends a request at time t. Count the client's accepted requests with a time strictly greater than t - window. If that count is below limit, accept the request (remember it) and return True; otherwise return False. Rejected requests are not remembered and do not count against the client later.

Times passed to allow never decrease (several requests may share a time).

Examples

ops:  ["Throttle", "allow", "allow", "allow", "allow", "allow", "allow", "allow"]
args: [[2, 10], ["a", 1], ["a", 5], ["a", 8], ["b", 8], ["a", 11], ["a", 12], ["a", 15]]
Output: [None, True, True, False, True, True, False, True]
Explanation: at 8 client "a" already has 2 accepted requests; "b" is counted separately.
At 11 the request from time 1 no longer counts (11 - 10 = 1 is not > 1), at 12 the ones
from 5 and 11 still do, and at 15 only the one from 11 does.

Constraints

• 1 <= limit <= 1000, 1 <= window <= 10**6, 0 <= t <= 10**9
• Up to 10**4 calls to allow
• Target: amortised O(1) per allow; memory per client bounded by limit

Goals

• Keep one queue of accepted request times per client
• Expire old timestamps lazily so each request costs amortised O(1)