A trace groups recorded operations as spans. Each span has its own identity, context and timing; parent-child relationships describe nesting or attribution. Parent elapsed time usually includes time spent waiting for child operations. Adding every inclusive span duration double-counts nesting and parallel work. A trace can be useful evidence without being a complete causal schedule.
The first graded model estimates uncovered parent wall time. A parent covers [0,100], and its direct children cover [10,60] and [40,90]. The child durations sum to 100, but they overlap for twenty. Their union covers eighty, leaving twenty uncovered. Subtract the union, not the sum. Even the remaining twenty is not necessarily CPU time: it can include uninstrumented waits, scheduling and work that lacks a child span.
For arbitrary intervals, sort by start and maintain the rightmost already covered endpoint. Add only the portion beyond that endpoint; gaps stay uncovered. Validate containment before calculation. Duplicate children, nested intervals, touching endpoints and zero-duration intervals should not produce negative uncovered time. This local function assumes comparable timestamps in one fixture time coordinate.
The second model computes a critical path from explicit dependencies. Each operation provides a duration and IDs it must wait for. We assume unlimited workers, no dispatch overhead and immediate start once all dependencies finish. Independent operations may overlap. A join starts at the maximum predecessor finish time, then adds its own duration. The longest chain determines the ideal completion bound under that model.
finish = {"cache": 1.5, "db": 5.5}
encode_duration = 2
print(max(finish.values()) + encode_duration)The modeled result is 7.5 ms. Summing cache and database times would incorrectly serialize parallel branches. Processing operations in input order is also unsafe when a dependency appears later in the fixture. Repeatedly process operations whose dependencies are complete; if none are ready while work remains, the validated graph has a cycle. Production tools may use more efficient graph algorithms, but the invariant is the same.
Ties need a reproducible rule. The build chooses the lexicographically smallest complete ID sequence among paths with maximum duration ending at any operation. Zero durations make a path tie its own extension; normal prefix ordering applies. This is a presentation contract, not a physical claim that one equal-duration route was uniquely responsible.
Do not infer this dependency graph from parent IDs alone. Sequential sibling calls, fan-out, async work and resource queues need additional evidence. Missing spans and cross-host clock differences complicate real trace analysis. The exercises deliberately separate interval coverage from dependency scheduling so success does not imply that a learner has instrumented distributed tracing or proven an actual production critical path.
For practice, inspect overlapping spans, diagnose double subtraction, and fix a join that chooses the fastest dependency. The build must reject cycles, unknown dependencies and invalid intervals, preserve input, and report the idealized path with its stated limits.