How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a medium difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at Datadog.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Datadog during technical interviews.

Build span trees from unordered trace spans

Company: Datadog

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

You are given an unordered list of span objects. Each span is a map/dictionary containing at least: - `span_id` (string, unique) - `parent_id` (string or `null`) - `start_time` (integer timestamp) A span is considered a **root** span if: 1. `parent_id` is `null`, or 2. `parent_id` is non-null but does not match any existing `span_id` in the input (i.e., its parent is missing). Such a span is an **orphan** and must be treated as a root. Build the output as a **list of root spans**, where each span is augmented with a `children` field (a list of its direct child spans). The `children` list for every span must be sorted by increasing `start_time` (if two children have the same `start_time`, you may keep input order or break ties by `span_id`, but be consistent). Return the list of root spans (i.e., the forest of span trees). The order of the root spans themselves is not strictly specified unless you choose to sort them similarly (state your choice). ### Example **Input** ```json [ {"span_id":"span_1", "parent_id":null, "start_time":300}, {"span_id":"span_2", "parent_id":"span_1","start_time":500}, {"span_id":"span_3", "parent_id":"span_1","start_time":300}, {"span_id":"span_4", "parent_id":"span_2","start_time":500}, {"span_id":"span_5", "parent_id":"span_6","start_time":600}, {"span_id":"span_7", "parent_id":null, "start_time":1000} ] ``` **Output (one valid formatting)** ```json [ { "span_id":"span_1", "parent_id":null, "start_time":300, "children":[ {"span_id":"span_3","parent_id":"span_1","start_time":300}, { "span_id":"span_2", "parent_id":"span_1", "start_time":500, "children":[ {"span_id":"span_4","parent_id":"span_2","start_time":500} ] } ] }, {"span_id":"span_5","parent_id":"span_6","start_time":600}, {"span_id":"span_7","parent_id":null,"start_time":1000} ] ``` ### Notes / Assumptions to clarify in your solution - Every `span_id` is unique. - There may be multiple roots. - A span whose `parent_id` is missing becomes a root (an orphan). - (Optional) Decide how to handle cycles if they appear (not expected in valid traces).

Quick Answer: This question evaluates skill in reconstructing hierarchical relationships from unordered span records, testing understanding of tree structure assembly, orphan/root detection, and ordering children by timestamp within the Coding & Algorithms domain.

You are given an unordered list of span dictionaries. Each span contains at least the keys `span_id` (unique string), `parent_id` (string or None), and `start_time` (integer). Build the trace forest by attaching each span to its parent. A span is a root if its `parent_id` is None, or if its `parent_id` does not match any `span_id` in the input. Such missing-parent spans are orphans and must also be treated as roots. Return the list of root spans, where every returned span is a copy of the original span augmented with a `children` field containing its direct children recursively. Preserve any extra fields that already exist on a span. In this problem, sort both the root list and every `children` list by increasing `start_time`; if two spans have the same `start_time`, preserve their original input order. You may assume the parent relationships are acyclic.

Constraints

0 <= len(spans) <= 200000
Each `span_id` is unique
`parent_id` is either None or a string
-10^9 <= start_time <= 10^9
Evaluation inputs do not contain cycles in the parent relationships

Examples

Input: [{'span_id':'span_4','parent_id':'span_2','start_time':500}, {'span_id':'span_2','parent_id':'span_1','start_time':500}, {'span_id':'span_5','parent_id':'span_6','start_time':600}, {'span_id':'span_1','parent_id':None,'start_time':300}, {'span_id':'span_7','parent_id':None,'start_time':1000}, {'span_id':'span_3','parent_id':'span_1','start_time':300}]

Expected Output: [{'span_id':'span_1','parent_id':None,'start_time':300,'children':[{'span_id':'span_3','parent_id':'span_1','start_time':300,'children':[]}, {'span_id':'span_2','parent_id':'span_1','start_time':500,'children':[{'span_id':'span_4','parent_id':'span_2','start_time':500,'children':[]}]}]}, {'span_id':'span_5','parent_id':'span_6','start_time':600,'children':[]}, {'span_id':'span_7','parent_id':None,'start_time':1000,'children':[]}]

Explanation: The input is unordered. `span_1` is a real root, `span_5` is an orphan because `span_6` is missing, and `span_7` is another root. Children are sorted by `start_time`, so under `span_1`, `span_3` comes before `span_2`.

Input: []

Expected Output: []

Explanation: An empty input produces an empty forest.

Input: [{'span_id':'root','parent_id':None,'start_time':42}]

Expected Output: [{'span_id':'root','parent_id':None,'start_time':42,'children':[]}]

Explanation: A single span with no parent is a root and has no children.

Input: [{'span_id':'b','parent_id':'a','start_time':5}, {'span_id':'c','parent_id':'a','start_time':5}, {'span_id':'a','parent_id':None,'start_time':1}, {'span_id':'x','parent_id':'missing','start_time':1}]

Expected Output: [{'span_id':'a','parent_id':None,'start_time':1,'children':[{'span_id':'b','parent_id':'a','start_time':5,'children':[]}, {'span_id':'c','parent_id':'a','start_time':5,'children':[]}]}, {'span_id':'x','parent_id':'missing','start_time':1,'children':[]}]

Explanation: Both `a` and `x` are roots with the same `start_time`, so their relative order follows input order among roots. Children `b` and `c` also share the same `start_time`, so their input order is preserved.

Input: [{'span_id':'child','parent_id':'root','start_time':20,'service':'api'}, {'span_id':'orphan','parent_id':'zzz','start_time':5,'service':'worker'}, {'span_id':'grand','parent_id':'child','start_time':30,'service':'db'}, {'span_id':'root','parent_id':None,'start_time':10,'service':'frontend'}]

Expected Output: [{'span_id':'orphan','parent_id':'zzz','start_time':5,'service':'worker','children':[]}, {'span_id':'root','parent_id':None,'start_time':10,'service':'frontend','children':[{'span_id':'child','parent_id':'root','start_time':20,'service':'api','children':[{'span_id':'grand','parent_id':'child','start_time':30,'service':'db','children':[]}]}]}]

Explanation: This case shows that extra fields such as `service` must be preserved. `orphan` becomes a root because its parent is missing.

Hints

A hash map from `span_id` to span node lets you find each parent in O(1) time.
Create copies of all spans with empty `children` lists first, then do a second pass to attach each span to its parent or classify it as a root.

Quick Overview

This question evaluates skill in reconstructing hierarchical relationships from unordered span records, testing understanding of tree structure assembly, orphan/root detection, and ordering children by timestamp within the Coding & Algorithms domain.