Sliding-Window Rate Limiter

A model API limits every API key in two ways at once: a number of requests and a number of tokens in any rolling window of window seconds. Two limits matter because a few huge prompts can cost more GPU time than thousands of tiny ones.

Requests arrive in time order. Request i comes at second times[i] from key keys[i] and asks for tokens[i] tokens. When it arrives at second t, look at the requests from the same key that were accepted in the window (t - window, t], that is, strictly after t - window. The new request is accepted when, counting it too:

• the number of accepted requests in the window is at most maxRequests, and
• their tokens add up to at most maxTokens.

Otherwise it is refused, and a refused request does not count towards anything later. Each key has its own limits; keys do not affect each other.

Return, for every request, whether it was accepted.

Example

window = 60, maxRequests = 3, maxTokens = 1000. Key 1 sends 400 tokens at second 0 and 400 at 10 (both accepted). At 20 it asks for 300, which would make 1,100 tokens: refused. At 30, 200 tokens make exactly 1,000: accepted. Key 2 is unaffected at 40. At 50, key 1 would make a fourth request: refused. At 60 the request from second 0 has left the window (it is not after 60 - 60 = 0), leaving 600 tokens in 2 requests, so 100 more is accepted. At 61 the window holds the requests from 10, 30 and 60, already three: refused.

The answer is [true, true, false, true, true, false, true, false].