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>
Java 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
List<Boolean> rateLimitDecisions(List<Integer> times, int windowSeconds, int maxCalls) {
}Worked examples
| Call | Result |
|---|---|
rateLimitDecisions(Main.<Integer>ls(0, 1, 2, 3), 10, 3) | Main.<Boolean>ls(true, true, true, false) |
rateLimitDecisions(Main.<Integer>ls(0, 1, 2), 10, 1) | Main.<Boolean>ls(true, false, false) |
rateLimitDecisions(Main.<Integer>ls(0, 10, 20), 10, 1) | Main.<Boolean>ls(true, true, true) |
rateLimitDecisions(Main.<Integer>ls(0, 1, 1, 12), 10, 2) | Main.<Boolean>ls(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 Java
List<Boolean> rateLimitDecisions(List<Integer> times, int windowSeconds, int maxCalls) {
Deque<Integer> allowed = new ArrayDeque<>();
List<Boolean> result = new ArrayList<>();
for (int t : times) {
while (!allowed.isEmpty() && allowed.peekFirst() <= t - windowSeconds) allowed.pollFirst();
boolean ok = maxCalls > 0 && allowed.size() < maxCalls;
if (ok) allowed.addLast(t);
result.add(ok);
}
return result;
}