Loadingone moment…
Sign in to run and submit your work
Reading is open to everyone. Running code and saving drafts need an account so your work is yours and comes back on your next visit.
or
CODE WORKSPACE
During an incident review, the on-call engineer wants the tightest moment when a failing request could have passed through every service in its path. The merged log has one entry per service event, sorted by time, and the question is: what is the shortest span of seconds that contains at least one entry from each required service?
Write shortest_covering_span(entries, required). It takes entries, a list of [epoch_seconds, service] pairs sorted by time ascending (the timestamps are small numbers here to stay readable), and required, a list of service-name strings. It returns [start_ts, end_ts], the first and last timestamp of the shortest covering span.
Function to write
shortest_covering_span(entries: list[list], required: list[str]) -> list[int] | NoneA two-item list [start_ts, end_ts] for the earliest shortest span covering every required service, or None when no span covers them.
How to approach it
Count required services inside the window and track how many are covered. Once all are covered, shrink from the left until the next removal would drop a service to zero.
Sample cases
+ 3 held back until you submit
one incident across three services
Of the four candidate tightest spans covering all three services, the 9-second span from 112 to 121 is the tightest.
Input
Argument 1
[
[
100,
'auth'
],
[
105,
'cart'
],
[
112,
'auth'
],
[
118,
'billing'
],
[
121,
'cart'
],
[
140,
'auth'
],
[
141,
'billing'
]
]Argument 2
[
'auth',
'billing',
'cart'
]Returns
[
112,
121
]fewest entries is not fewest seconds
Two entries span 60 seconds, four entries span 3; the span is measured in seconds.
Input
Argument 1
[
[
10,
'ingest'
],
[
70,
'load'
],
[
200,
'ingest'
],
[
201,
'metrics'
],
[
202,
'metrics'
],
[
203,
'load'
]
]Argument 2
[
'ingest',
'load'
]Returns
[
200,
203
]two spans tie
The spans 0-4 and 10-14 are both 4 seconds, so the earlier start_ts wins.
Input
Argument 1
[
[
0,
'api'
],
[
4,
'db'
],
[
10,
'api'
],
[
14,
'db'
]
]Argument 2
[
'api',
'db'
]Returns
[
0,
4
]no log entries
An empty log cannot cover anything, so the answer is None rather than an error.
Input
Argument 1
[] (empty list)
Argument 2
[
'auth'
]Returns
None
Constraints
entries. It covers when it contains at least one entry for every service in required. Entries for other services may sit inside it.end_ts - start_ts in seconds, not the number of entries in it.[start_ts, end_ts] as a two-item list (not a tuple): the timestamp of the span's first entry and of its last.start_ts.required count once: ["cart", "cart"] needs one cart entry.None when entries is empty, when required is empty, or when some required service never appears.Worked example
Take the entries at 100 auth, 105 cart, 112 auth, 118 billing, 121 cart, 140 auth, 141 billing, with required = ["auth", "billing", "cart"]. Grow the window from the left, counting each required service inside it. At 118 billing all three are covered for the first time: the window 100–118 is 18 seconds. Tighten from the left: drop 100 auth (auth still has 112) → 105–118, 13 seconds. Dropping 105 cart would leave no cart, so tightening stops there. Add 121 cart: coverage returns, tighten again — drop 105 cart → 112–121, 9 seconds; dropping 112 auth would lose auth. The later windows 118–140 and 121–141 are longer. The answer is [112, 121].
The trap: minimising entries instead of seconds. In the ingest/load case, [10, 70] has only two entries but spans 60 seconds, while [200, 203] has four entries and spans 3 — the right answer.
What this tests
The covering sliding window with a need counter — LeetCode 'Minimum Window Substring' in incident-log clothing. The target is O(n) time and O(distinct required services) space; trying every start and scanning forward until covered is O(n²) and stalls on a day of logs. Data engineers meet it in distributed-trace analysis, correlation windows across sources, and 'when did every partition report' checks. This exact problem is not named in the data engineering reports we could find; it is the standard Minimum Window Substring shape and covers the covering variant of the pattern.
shortest_covering_span(entries: list[list], required: list[str]) -> list[int] | NoneSubmit for review to find out what your query gets right, what it gets wrong, and how it compares with the best working query for this exercise.
This scenario runs a full workspace — editor, canvas and results side by side. It needs a laptop or desktop to be usable. Open this page on a bigger screen to start building.