In-Memory Per-Second API Rate Limiter: Accept or Reject Each Request

An API endpoint is protected by an in-memory rate limiter. The limiter is created with one value, `max_per_second`, the largest number of requests it lets through per second. Every request to the endpoint first asks the limiter whether it still has capacity, and the limiter accepts or rejects the request. Implement the limiter's decisions: given the arrival times of the requests, return whether each one is accepted. ### Function Signature ```python def rate_limit(timestamps: list[int], max_per_second: int) -> list[bool]: ``` `timestamps[i]` is the arrival time of request `i` in milliseconds. The result has one entry per request, in input order: `True` if the request is accepted and `False` if it is rejected. ### Rules - Requests are decided one at a time in list order, and `timestamps` is non-decreasing. Several requests may share a timestamp. - A request arriving at time `t` is accepted if fewer than `max_per_second` earlier requests were accepted with a timestamp `s` satisfying `t - 1000 < s <= t`. Otherwise it is rejected. - A request accepted exactly 1000 ms before `t` no longer counts against the request at `t`. - Rejected requests use no capacity: they never count against later requests. ### Constraints - `1 <= len(timestamps) <= 2 * 10^5` - `0 <= timestamps[i] <= 10^9` - `1 <= max_per_second <= 10^5` ### Examples **Example 1** The times are written in milliseconds after 09:30:00.000, so 09:30:05.250 is `5250`. ```text Input: timestamps = [5250, 5400, 5700, 6250, 6300, 6400], max_per_second = 2 Output: [True, True, False, True, False, True] ``` At 5700, the requests at 5250 and 5400 were both accepted within the last second, so the limit of 2 is reached. At 6250, the request at 5250 is exactly 1000 ms old and no longer counts; only 5400 counts, so the request is accepted. At 6300, the accepted requests at 5400 and 6250 count, so it is rejected. At 6400, the request at 5400 is exactly 1000 ms old; only 6250 counts, so it is accepted. **Example 2** ```text Input: timestamps = [0, 0, 999, 1000, 1000, 2500], max_per_second = 1 Output: [True, False, False, True, False, True] ``` The second request at 0 and the request at 999 both see the accepted request at 0. The first request at 1000 does not, because that request is exactly 1000 ms old, so it is accepted, and the second request at 1000 then sees it. At 2500 nothing accepted is recent enough to count. **Example 3** ```text Input: timestamps = [100, 200, 300, 400, 1150, 1250, 1350], max_per_second = 3 Output: [True, True, True, False, True, True, True] ``` The request at 400 is rejected because 100, 200 and 300 were accepted. At 1150 the accepted requests that count are 200 and 300; the rejected request at 400 uses no capacity, so 1150 is accepted. At 1250 the requests at 300 and 1150 count, and at 1350 the requests at 1150 and 1250 count, so both are accepted.