Fix the sliding window check in a rate limiter

Review the AI's codeMedium15 min

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 time t is still in the window when now - t is less than window_ms. So a request exactly window_ms later no longer sees it.
  • Allow the request when limit is above 0 and fewer than limit accepted requests are still in the window. Record an allowed request at now. A refused request is not recorded.

Examples

sliding_window_allow(arrival_times_ms: list[int], limit: int, window_ms: int) -> list[bool]
Example 1
Inputsliding_window_allow([0, 100, 200, 300], 3, 1000)
Output[True, True, True, False]
Example 2
Inputsliding_window_allow([0, 100, 200, 1000], 3, 1000)
Output[True, True, True, True]
Example 3
Inputsliding_window_allow([0, 999], 1, 1000)
Output[True, False]