Tokens-per-minute limiter

A model API sells capacity by the minute: each API key may send so many requests, and use so many tokens, in any 60 seconds. Over four levels you'll build the RateLimiter that decides, request by request, what gets through.

• RateLimiter(requests_per_minute, tokens_per_minute): the limits every key gets. You'll use tokens_per_minute from level 2.
• allow(t_ms, key, tokens) -> bool: a request from API key key at time t_ms (milliseconds) that will use tokens tokens. For now, ignore tokens. Let it through if fewer than requests_per_minute of this key's requests were let through at times in (t_ms - 60000, t_ms]: a request exactly 60,000 ms old no longer counts. Return True and record it, or return False and record nothing.

Keys are counted separately. Across all calls t_ms never decreases, and calls can share a time.

rl = RateLimiter(2, 10**9)
rl.allow(0, "alice", 500)        # True
rl.allow(1000, "alice", 500)     # True
rl.allow(2000, "alice", 500)     # False  (0 and 1000 are in the window)
rl.allow(2000, "bob", 500)       # True   (bob is counted on his own)
rl.allow(60000, "alice", 500)    # True   (the request at 0 is exactly 60 s old: it has left)
rl.allow(60999, "alice", 500)    # False  (1000 and 60000)
rl.allow(61000, "alice", 500)    # True

Constraints: limits are 1..10^5 requests and 1..10^9 tokens; 1 <= tokens <= 10^6; 0 <= t_ms <= 10^12 (use 64-bit integers in C++ and Java). Keys are non-empty strings.

⭐ Bonus: a speed test with 200,000 requests from thousands of keys earns a star if each call is O(1) amortized.