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 . There are currently 0 allowed calls for tool "a" in this interval. Since (the limit), the call is allowed. The history for "a" becomes . -
Call 2
("a", 1): The window is . The previous allowed call at falls within this interval. There is 1 allowed call in the window. Since , the call is allowed. The history for "a" becomes . -
Call 3
("a", 2): The window is . Both previous allowed calls ( and ) fall within this interval. There are 2 allowed calls in the window. Since (the limit is reached), the call is throttled. The history remains 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.