← Datadog Interview Insights

Datadog·Software Engineer·Technical Phone Screen·Intermediate

Intermediate
Jun 2026

Summary

Datadog SWE interview with a tree reconstruction problem that sounds straightforward until you actually sit down and think through the edge cases. The orphan root condition tripped me up more than I expected.

Questions Asked (1)

Q1

Given an unordered list of span dictionaries (each with a span_id, parent_id, start_time, and possibly other fields), reconstruct a list of tree-structured traces. A span is a root if its parent_id is None or its parent_id doesn't appear in the input. Children at each node must be sorted by start_time. Return the list of root spans, each with a nested children field representing its subtree.

Algorithms & Data StructuresData Modeling
Author's notes

The 'orphan root' part is where I lost a minute.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

First, build a hash map from span_id to span for O(1) lookups, then iterate through the spans to assign each to its parent's children list or to the roots list if it's a root. Finally, recursively sort each node's children by start_time and return the roots.

Pro tip: Mention that you can avoid recursion depth issues by using an iterative post-order traversal or by sorting children during the initial pass, and highlight that this approach handles orphaned spans gracefully.

1. Clarify requirements and edge cases

Confirm that spans with missing parents are roots, that children are sorted by start_time, and discuss handling of cycles or duplicate IDs.

2. Build a lookup map

Create a dictionary mapping span_id to span object for O(1) access, and initialize an empty children list for each span.

3. Link spans to parents

Iterate through all spans: if parent_id is None or not in the map, add to roots; otherwise, append to the parent's children list.

4. Sort children recursively

For each root, perform a depth-first traversal to sort children by start_time at every level, ensuring the entire tree is ordered.

5. Return the roots

Return the list of root spans, each with its nested children field representing the sorted subtree.

Key Points to Mention

  • Time and space complexity: O(n log n) due to sorting, O(n) space for the map and output.
  • Handling of orphaned spans (parent_id not in input) as roots.
  • Using a hash map for O(1) parent lookups instead of nested loops.
  • Sorting children by start_time at each node, not just globally.
  • Potential for cycles: detect and handle to avoid infinite loops.
  • Iterative vs recursive traversal for sorting to avoid stack overflow.

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