Span Trace Forest

Asked at Datadog

Reported by the problem's creator, not verified

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.

Example 1
Input: 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",[]]]
Explanation: 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.

Import your own questions

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

Import a question

Span Trace Forest

Examples

Example 1

Code