Span Trace Forest

DatadogMedium

A tracing system records spans. Each span is a list [span_id, parent_id, start_time], where span_id is a unique non-empty string, parent_id is either None or the span_id of the span that caused it, and start_time is an integer. The list is unordered. A span whose parent_id is None, or whose parent_id is not the id of any span in the list, starts a trace.

Part 1: Build the trace forest

You are given spans, an unordered list of spans, where each span is [span_id, parent_id, start_time]. A span whose parent_id is None, or whose parent_id is not the id of any span in the list, starts a trace.

Return one tree per trace as a list. Each tree node is [span_id, children], where children is the list of that node's child nodes. Order the trees by the start_time of their root span, and each node's children by start_time. Spans with equal start_time keep the order in which they appear in spans.

Example 1

spans: [["span_1",null,300],["span_2","span_1",500],["span_3","span_1",300],["span_4","span_2",500],["span_5","span_6",600],["span_7",null,1000]]
Output: [["span_1",[["span_3",[]],["span_2",[["span_4",[]]]]]],["span_5",[]],["span_7",[]]]

Why: The roots are span_1 (starts a trace with parent_id = None), span_5 (its parent span_6 is not in the list) and span_7. Under span_1, span_3 (300) comes before span_2 (500), and span_4 hangs under span_2.

Constraints

0 <= len(spans) <= 10^4
span_id values are distinct, non-empty strings
0 <= start_time <= 10^12
Following parent_id links from any span never leads back to that span
Following parent_id links from a root span to a leaf passes through at most 200 spans

Practice this question

Import your own questions

Paste a question you were asked and get a full problem: statement, tests and a checked solution.

Import a question