Loading page…
Practice problem · medium
During an incident, Kestrel Observe engineers read a service's log, where each line carries one numeric code. The incident checklist names the error codes that matter. The root cause usually sits where those codes cluster.
Kenji Sato, the site reliability engineer on call this week, wants a new search. It finds the shortest stretch of consecutive lines that shows every checklist code at least once, and returns its first and last line. If two stretches are equally short, he wants the earlier one. If no stretch shows every code, there is nothing to read.
Write shortest_window(codes, required).
codes[i] is the code on line i of the log, in order.required lists the checklist codes. No code appears in it twice.required appears in it at least once. Other codes may appear too.[start, end], the first and last line of the shortest covering window.[-1, -1]. This includes the case where required has more codes than the log has lines.Input: codes = [503, 404, 404, 429, 500, 404, 503, 429, 500], required = [429, 500, 503]
Output: [6, 8]missing starts at 3, one for each required code. Code 404 is not on the checklist, so it never changes missing.
| right | Joins | missing after joining | Recorded, then the left line leaves | left after | Best |
|---|---|---|---|---|---|
| 0 | 503 | 2 | none | 0 | none |
| 1 | 404 | 2 | none | 0 | none |
| 2 | 404 | 2 | none | 0 | none |
| 3 | 429 | 1 | none | 0 | none |
| 4 | 500 | 0 | lines 0 to 4, then 503 leaves (missing 1) | 1 | 0 to 4 |
| 5 | 404 | 1 | none | 1 | 0 to 4 |
| 6 | 503 | 0 | lines 1 to 6, 2 to 6, 3 to 6; then 404, 404, 429 leave (missing 0, 0, 1) | 4 | 3 to 6 |
| 7 | 429 | 0 | lines 4 to 7, then 500 leaves (missing 1) | 5 | 3 to 6 |
| 8 | 500 | 0 | lines 5 to 8, 6 to 8; then 404, 503 leave (missing 0, 1) | 7 | 6 to 8 |
Lines 6 to 8 show 503, 429 and 500 in 3 lines.
Input: codes = [500, 503, 500], required = [503, 504]
Output: [-1, -1]Code 504 never appears, so no window covers the checklist.
Input: codes = [500, 502, 404, 502, 500], required = [500, 502]
Output: [0, 1]Lines 0 to 1 and lines 3 to 4 both cover the checklist in 2 lines. The earlier one wins.
1 ≤ codes.length ≤ 10^5 (about 30 days of one service's log, at Kestrel Observe's average of about 3,300 lines a day)1 ≤ codes[i] ≤ 10^51 ≤ required.length ≤ 1,000, and the codes in required are distinct1 ≤ required[i] ≤ 10^5Starting at every line and extending until the window covers the checklist is O(n^2) when one required code is rare. On the large test stress-rare-code, that is about 4.9 × 10^9 steps. Aim for O(n + k), where k is the length of required.
Checking coverage by looping over all k required codes at every step is O(n × k). With k = 1,000, that is up to about 2 × 10^8 lookups. Keep one counter that says how many required codes are still missing, so each step costs O(1).
shortest_window · runs in your browserCoding is easiest on a laptop. On a phone, read, trace and try small edits.