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>
Go 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
func rateLimitDecisions(times []int, windowSeconds int, maxCalls int) []bool {
}Worked examples
| Call | Result |
|---|---|
rateLimitDecisions([]int{0, 1, 2, 3}, 10, 3) | []bool{true, true, true, false} |
rateLimitDecisions([]int{0, 1, 2}, 10, 1) | []bool{true, false, false} |
rateLimitDecisions([]int{0, 10, 20}, 10, 1) | []bool{true, true, true} |
rateLimitDecisions([]int{0, 1, 1, 12}, 10, 2) | []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 Go
func rateLimitDecisions(times []int, windowSeconds int, maxCalls int) []bool {
allowed := []int{}
result := []bool{}
for _, t := range times {
for len(allowed) > 0 && allowed[0] <= t-windowSeconds {
allowed = allowed[1:]
}
ok := maxCalls > 0 && len(allowed) < maxCalls
if ok {
allowed = append(allowed, t)
}
result = append(result, ok)
}
return result
}