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>
C# needs a compiler and Drill does not host one yet, so this page is the reference rather than an exercise: the problem, worked examples, and the solution in full. To type it out, the same problem runs in Python.
Where you start
public List<bool> RateLimitDecisions(List<int> times, int windowSeconds, int maxCalls) {
}Worked examples
| Call | Result |
|---|---|
RateLimitDecisions(new List<int> { 0, 1, 2, 3 }, 10, 3) | new List<bool> { true, true, true, false } |
RateLimitDecisions(new List<int> { 0, 1, 2 }, 10, 1) | new List<bool> { true, false, false } |
RateLimitDecisions(new List<int> { 0, 10, 20 }, 10, 1) | new List<bool> { true, true, true } |
RateLimitDecisions(new List<int> { 0, 1, 1, 12 }, 10, 2) | new List<bool> { 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 C#
public List<bool> RateLimitDecisions(List<int> times, int windowSeconds, int maxCalls) {
var allowed = new Queue<int>();
var result = new List<bool>();
foreach (var t in times) {
while (allowed.Count > 0 && allowed.Peek() <= t - windowSeconds) allowed.Dequeue();
bool ok = maxCalls > 0 && allowed.Count < maxCalls;
if (ok) allowed.Enqueue(t);
result.Add(ok);
}
return result;
}