Datadog·Software Engineer·Technical Phone Screen·Intermediate

Intermediate

May 2026

Summary

Datadog coding round, one problem the whole session. It's a tree reconstruction question dressed up in observability language which I thought was a nice touch given the domain, but the core of it is just building a tree from a flat list of nodes.

Questions Asked (1)

Given a flat list of span objects (each with a span ID, parent ID, start time, and possibly other fields), reconstruct the full tree structure. A span is a root if its parent ID is null or points to an ID that doesn't exist in the input. Children at every level must be sorted by start time. Return the list of root spans, each with a nested children field.

Algorithms & Data StructuresSystem Design

Author's notes

The observability framing made me overthink it at first.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Use a hash map to index spans by ID, then iterate through the list to link children to parents. Treat spans with missing or null parents as roots, and sort children at each level by start time. Finally, return the list of root spans with nested children.

Pro tip: Clarify edge cases upfront, such as cycles or duplicate IDs, and discuss how to handle them gracefully. Mention that sorting can be done once per parent after building the tree, or during insertion if using a sorted structure.

1. Clarify requirements and edge cases

Ask about input size, whether spans can have cycles, duplicate IDs, or missing parents. Confirm that sorting is by start time and that root spans are those with null or non-existent parent IDs.

2. Build a hash map for quick lookup

Create a dictionary mapping span ID to span object. This allows O(1) access to any span by ID, which is crucial for linking children to parents efficiently.

3. Link children to parents and identify roots

Iterate through the list: for each span, if its parent ID exists in the map, add it to the parent's children list; otherwise, add it to the roots list. This handles missing parents as roots.

4. Sort children at each level

After building the tree, recursively sort the children of each span by start time. Alternatively, sort during insertion if using a sorted list, but post-processing is simpler.

5. Return the root spans

Return the list of root spans, each with its nested children field populated and sorted. Ensure the output structure matches the expected format.

Key Points to Mention

Time and space complexity: O(n log n) due to sorting, O(n) space for the map and tree.
Handling of cycles: detect and break cycles or treat as invalid input.
Duplicate IDs: decide whether to merge, ignore, or error out.
Sorting stability: if start times are equal, consider secondary sort key (e.g., span ID) for deterministic output.
Memory optimization: avoid deep recursion for very deep trees; use iterative traversal if needed.
Real-world relevance: this mirrors trace reconstruction in observability tools like Datadog.

AI-generated suggestions, not part of the candidate's original notes. May be inaccurate — verify before relying on them.