Katkat
Back

Build span trees from unordered trace spans

DatadogSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

This problem tests your ability to reconstruct a parent-child hierarchical tree from an unordered collection of trace spans by leveraging parent ID references and sorting mechanisms.

Build Span Tree

You are given a collection of unordered trace spans. Each span represents an operation in a distributed system and contains a unique spanId, an optional parentId, and a startTime. If a span does not have a parentId, it is considered a root span of a trace.

Your task is to organize these spans into a tree structure. Each node in the resulting structure should contain the span data and a list of its children, which must be sorted by their startTime in ascending order.

Function Signature

def build_span_trees(spans: List[dict]) -> List[dict]

Input

  • spans: A list of dictionaries, where each dict has keys: spanId (int/str), parentId (int/str or None), and startTime (int).

Output

  • A list of root spans, where each span dictionary includes an additional key children (a list of span dictionaries).

Constraints

  • spanId is unique.
  • parentId refers to a valid spanId present in the list unless it is a root.
  • spans length is up to 10,000.

Examples

# Input:
spans = [
    {"spanId": 1, "parentId": None, "startTime": 10},
    {"spanId": 2, "parentId": 1, "startTime": 20},
    {"spanId": 3, "parentId": 1, "startTime": 15}
]

# Output:
[
    {
        "spanId": 1, "parentId": None, "startTime": 10,
        "children": [
            {"spanId": 3, "parentId": 1, "startTime": 15, "children": []},
            {"spanId": 2, "parentId": 1, "startTime": 20, "children": []}
        ]
    }
]

Hints

Hint 1

Use a hash map (dictionary) to store each span by its `spanId` for O(1) access during the tree construction process.

Hint 2

Initialize an empty `children` list for every span object before linking them together.

Hint 3

Iterate through the spans once to create the lookup map, a second time to assign children to their respective parents, and identify roots as those with no `parentId`.

Follow-up questions

  • How would you handle or detect cycles if a malicious or malformed trace contains a circular parent-child reference?
  • If the input spans arrive as a stream, how would you modify your algorithm to maintain the tree incrementally?
  • What is the time and space complexity of your solution, and can you optimize it if the spans are already partially sorted by `startTime`?