Loading page…
Practice problem · easy
A monitoring system pages the on-call engineer when a service has a burst of errors. Your team lead is tuning the alert. A burst is any k consecutive minutes whose errors add up to at least a limit.
Before he turns the alert on, he replays last month's per-minute error counts. How many windows would have fired? Too many, and the alert is noise. Too few, and real incidents go unnoticed.
Write count_bursts(errors, k, limit).
errors[i] is the number of errors in minute i.k consecutive minutes. There are n − k + 1 windows, and they overlap.limit.Input: errors = [3, 0, 5, 2, 4, 1], k = 3, limit = 8
Output: 2| Window | Minutes | Total | At least 8? |
|---|---|---|---|
| 0 to 2 | 3, 0, 5 | 8 | yes |
| 1 to 3 | 0, 5, 2 | 7 | no |
| 2 to 4 | 5, 2, 4 | 11 | yes |
| 3 to 5 | 2, 4, 1 | 7 | no |
Two windows reach the limit. A total of exactly 8 counts, because the rule is "at least".
Input: errors = [0, 0, 0], k = 1, limit = 0
Output: 3With a limit of 0, every window counts, even a quiet one.
Input: errors = [2, 2, 2, 2], k = 2, limit = 5
Output: 0Every window totals 4, which is below the limit.
1 ≤ k ≤ errors.length ≤ 10^50 ≤ errors[i] ≤ 10^40 ≤ limit ≤ 10^9Re-adding every window costs up to about 2.5 × 10^9 additions when k is near n / 2, which is far too slow. Aim for O(n).
Read the values too. A window totals at most 10^5 × 10^4 = 10^9, which fits in a 32-bit integer. Here an int is enough, unlike in the previous problem.
count_bursts · runs in your browserCoding is easiest on a laptop. On a phone, read, trace and try small edits.