Enforce Per-Tool Rate Limits Over a Call Stream
Problem Statement
Each tool has a rate limit of limit calls per window seconds. Given a timestamped stream of tool calls, decide which are allowed and which are throttled using a sliding window.
Background
For each tool, a call at time t is allowed if fewer than limit allowed calls to that same tool occurred in the half-open interval (t - window, t]. Throttled calls do not count toward the limit (they never executed). Process calls in the given order.
Your Task
Implement:
def rate_limit(calls, limit, window):
- calls: list of (tool, time) tuples, time non-decreasing.
- Return a list of booleans, True if the call was allowed.
Input Format
- calls (list of (str, int)), limit (int), window (int).
Output Format
- A list of booleans.
Sample
print(rate_limit([("a",0),("a",1),("a",2)], 2, 5))
Output:
[True, True, False]
Example:
print(rate_limit([("a",0),("a",1),("a",2)], 2, 5))[True, True, False]
-
Call 1
("a", 0): The sliding window interval is (0β5,0]=(β5,0]. There are currently 0 allowed calls for tool "a" in this interval. Since 0<2 (the limit), the call is allowed. The history for "a" becomes [0]. -
Call 2
("a", 1): The window is (1β5,1]=(β4,1]. The previous allowed call at t=0 falls within this interval. There is 1 allowed call in the window. Since 1<2, the call is allowed. The history for "a" becomes [0,1]. -
Call 3
("a", 2): The window is (2β5,2]=(β3,2]. Both previous allowed calls (t=0 and t=1) fall within this interval. There are 2 allowed calls in the window. Since 2ξ <2 (the limit is reached), the call is throttled. The history remains [0,1] because throttled calls do not count. -
The final output is
[True, True, False]
Constraints:
- Times are non-decreasing ints; window and limit are positive.
- Only previously-allowed calls to the same tool count.
- Window is half-open: keep calls with
t_prev > t - window.
1. Background Knowledge
This problem models sliding window rate limiting, a standard technique in API gateways and distributed systems to prevent abuse. The core idea is that for any given moment, you only care about activity within a fixed time horizon behind you. If too many requests arrived in that horizon, the current one is rejected.
A critical detail in the specification is that throttled calls do not count toward the limit. This distinguishes it from a simple "count all calls in window" approach. Only allowed (executed) calls contribute to the window's occupancy. This means the state of the system depends on past decisions, not just raw input.
The interval is half-open: (tβwindow,t]. A call at time t is allowed if the number of previously allowed calls to the same tool with timestamps in (tβwindow,t] is strictly less than limit. Note that calls at exactly tβwindow are excluded from the window.
2. Algorithm Approach
Use a per-tool sliding window maintained with a queue (or deque). For each tool, store the timestamps of its allowed calls in chronological order.
For each incoming call (tool, t):
- Look at the queue for that tool.
- Remove (pop from the front) any timestamps that fall outside the window, i.e., timestamps β€tβwindow.
- Check the remaining queue length. If it is <limit, the call is allowed: append t to the queue and record True. Otherwise, record False and do not append.
Because input times are non-decreasing, each timestamp is enqueued at most once and dequeued at most once, giving an amortized O(1) per operation per tool.
3. Step-by-Step Strategy
Continue the full explanation
You're reading the free preview. Unlock the complete walkthrough, the code editor, test runner and reference solution with Premium.
Editor locked
The code editor is locked for Pro problems. It is only available for free problems. Please upgrade to gain access to the code editor for all problems.