Fix the sliding window check in a rate limiter
Your task
Your API allows each key at most limit requests in any window_ms milliseconds. It uses a sliding window log: it keeps the times of the requests it accepted and counts the recent ones. The first version read time.time(), a wall clock that jumps backward when the server's clock is corrected. The new version takes the arrival times as input, so the decision is testable.
An assistant wrote sliding_window_allow(arrival_times_ms, limit, window_ms). It is in the editor. It has a bug. Find it and fix it.
Input and output:
arrival_times_ms: the clock reading at each request, in milliseconds, in arrival order. Because the clock can be corrected, a reading can be earlier than the one before it.limit: the most requests allowed in a window.window_ms: the window length.- Return one true (allowed) or false (refused) per request, in order.
Rules the tests check:
- Time never moves backward. If a reading is earlier than the latest reading so far, use that latest reading instead, both for the decision and for the time recorded.
- At time
now, an accepted request at timetis still in the window whennow - tis less thanwindow_ms. So a request exactlywindow_mslater no longer sees it. - Allow the request when
limitis above 0 and fewer thanlimitaccepted requests are still in the window. Record an allowed request atnow. A refused request is not recorded.
Examples
sliding_window_allow(arrival_times_ms: list[int], limit: int, window_ms: int) -> list[bool]Example 1
Input
sliding_window_allow([0, 100, 200, 300], 3, 1000)Output
[True, True, True, False]Example 2
Input
sliding_window_allow([0, 100, 200, 1000], 3, 1000)Output
[True, True, True, True]Example 3
Input
sliding_window_allow([0, 999], 1, 1000)Output
[True, False]