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
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 int BurstWindow(List<int> timestamps, int windowSeconds) {
}Worked examples
| Call | Result |
|---|---|
BurstWindow(new List<int> { 1, 2, 5, 8, 10 }, 5) | 3 |
BurstWindow(new List<int> { 0, 10, 20, 30 }, 15) | 2 |
BurstWindow(new List<int> { 100 }, 10) | 1 |
BurstWindow(new List<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 C#
public int BurstWindow(List<int> timestamps, int windowSeconds) {
if (windowSeconds <= 0) return 0;
int best = 0;
for (int i = 0; i < timestamps.Count; i++) {
int count = 0;
for (int j = i; j < timestamps.Count; j++) {
if (timestamps[j] < timestamps[i] + windowSeconds) count++;
else break;
}
if (count > best) best = count;
}
return best;
}