Problems › TypeScript › 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.
rateLimitDecisions(times: list<int>, windowSeconds: int, maxCalls: int) → list<bool>
Where you start
function rateLimitDecisions(times: number[], windowSeconds: number, maxCalls: number): boolean[] {
}Worked examples
| Call | Result |
|---|---|
rateLimitDecisions([0,1,2,3], 10, 3) | [true,true,true,false] |
rateLimitDecisions([0,1,2], 10, 1) | [true,false,false] |
rateLimitDecisions([0,10,20], 10, 1) | [true,true,true] |
rateLimitDecisions([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 TypeScript
function rateLimitDecisions(times: number[], windowSeconds: number, maxCalls: number): boolean[] {
const allowed: number[] = [];
const result: boolean[] = [];
for (const t of times) {
while (allowed.length > 0 && allowed[0] <= t - windowSeconds) allowed.shift();
const ok = maxCalls > 0 && allowed.length < maxCalls;
if (ok) allowed.push(t);
result.push(ok);
}
return result;
}