Problems › Python › monitoring
Decide each call against a rate limit
An API gateway allows a caller so many requests in any trailing window. Requests it turned away do not count towards the limit — otherwise a rejected burst would lock someone out forever.
- Timestamps are in seconds and arrive in the order the calls did.
- A call is allowed when the number of already-allowed calls with a timestamp strictly newer than (now - window) is below the cap.
- Rejected calls leave no trace.
- A cap of zero or less rejects everything.
- The answer is one decision per call, in the same order.
rate_limit_decisions(times: list<int>, window_seconds: int, max_calls: int) → list<bool>
Where you start
def rate_limit_decisions(times: list[int], window_seconds: int, max_calls: int) -> list[bool]:
Worked examples
| Call | Result |
|---|---|
rate_limit_decisions([0, 1, 2, 3], 10, 3) | [True, True, True, False] |
rate_limit_decisions([0, 1, 2], 10, 1) | [True, False, False] |
rate_limit_decisions([0, 10, 20], 10, 1) | [True, True, True] |
rate_limit_decisions([0, 1, 1, 12], 10, 2) | [True, True, False, True] |
Hint
Keep only the timestamps you allowed. For each new call, drop the ones that have aged out, then count what is left.
Reference solution in Python
def rate_limit_decisions(times: list[int], window_seconds: int, max_calls: int) -> list[bool]:
allowed = deque()
result = []
for t in times:
while allowed and allowed[0] <= t - window_seconds:
allowed.popleft()
ok = max_calls > 0 and len(allowed) < max_calls
if ok:
allowed.append(t)
result.append(ok)
return result