Extract the Smallest Matching Log Window
You're triaging a production incident. The logs from one node contain a sequence of event types, and you need to find the smallest contiguous window of log entries that contains every event type from a required set.
Implement smallest_window(events, required) that returns (start, end) — where events[start:end] is the shortest matching window. If no window matches, return (0, 0).
The judge runs your solution against a 200,000-entry log with sparse coverage and enforces a real time limit. A naive O(n²) sweep won't finish in time.
- Return a
(start, end)tuple whereendis exclusive —events[start:end]is the matching window. - If multiple windows have the same minimum length, return the leftmost one.
- If no window contains every required event type, return
(0, 0). - If
requiredis empty, return(0, 0)— an empty requirement is trivially satisfied by an empty window. - If
requiredcontains duplicates (e.g.['A', 'A', 'B']), the window must contain at least that many occurrences of each event. - Run in O(n) over the events list — the perf test will TLE an O(n²) solution.
events = ['A', 'C', 'B', 'A', 'D', 'B', 'A'] required = ['A', 'B']
(2, 4)
events[2:4] = ['B', 'A'] — smallest window containing both required types.
events = ['X', 'X', 'X'] required = ['Y']
(0, 0)
No 'Y' anywhere in the log.
events = ['A', 'B', 'A', 'C'] required = ['A', 'A', 'B']
(0, 3)
Need two A's and one B. The window events[0:3] = ['A', 'B', 'A'] satisfies that.
- Do not modify the inputs.
- Use only the standard library. No NumPy, no external packages.
- The perf test runs on
len(events)up to 200,000 — any algorithm worse than O(n) on the inputs and requirements will exceed the time limit.
How would you change the algorithm if the events were arriving as a stream and you couldn't hold all of them in memory at once?
Keep moving through related algorithms & data structures problems and build a stronger search-friendly practice loop around this topic.
View track →