Peak request burst in a sliding window
A rate limiter must know the worst-case burst: the most requests that ever land inside a fixed-size time window.
- The timestamps are sorted ascending and in whole seconds.
- A window spans [t, t + windowSeconds); a request at exactly t + windowSeconds is outside.
- For every possible window start, count how many timestamps fall inside it; return the largest count.
- When windowSeconds is zero or negative, return 0.
burstWindow(timestamps: list<int>, windowSeconds: int) → int
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 burstWindow(timestamps []int, windowSeconds int) int {
}Worked examples
| Call | Result |
|---|---|
burstWindow([]int{1, 2, 5, 8, 10}, 5) | 3 |
burstWindow([]int{0, 10, 20, 30}, 15) | 2 |
burstWindow([]int{100}, 10) | 1 |
burstWindow([]int{}, 5) | 0 |
Hint
Brute-force every starting index and count forward; the list is sorted, so stop at the first timestamp outside the window.
Reference solution in Go
func burstWindow(timestamps []int, windowSeconds int) int {
if windowSeconds <= 0 {
return 0
}
best := 0
for i := 0; i < len(timestamps); i++ {
count := 0
for j := i; j < len(timestamps); j++ {
if timestamps[j] < timestamps[i]+windowSeconds {
count++
} else {
break
}
}
if count > best {
best = count
}
}
return best
}