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
std::vector<bool> rateLimitDecisions(std::vector<int> times, int windowSeconds, int maxCalls) {
}Worked examples
| Call | Result |
|---|---|
rateLimitDecisions(std::vector<int>{0, 1, 2, 3}, 10, 3) | std::vector<bool>{true, true, true, false} |
rateLimitDecisions(std::vector<int>{0, 1, 2}, 10, 1) | std::vector<bool>{true, false, false} |
rateLimitDecisions(std::vector<int>{0, 10, 20}, 10, 1) | std::vector<bool>{true, true, true} |
rateLimitDecisions(std::vector<int>{0, 1, 1, 12}, 10, 2) | std::vector<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++
std::vector<bool> rateLimitDecisions(std::vector<int> times, int windowSeconds, int maxCalls) {
std::deque<int> allowed;
std::vector<bool> result;
for (int t : times) {
while (!allowed.empty() && allowed.front() <= t - windowSeconds) allowed.pop_front();
bool ok = maxCalls > 0 && (int) allowed.size() < maxCalls;
if (ok) allowed.push_back(t);
result.push_back(ok);
}
return result;
}