FastPrepBuild a Trace Forest
Problems/Build a Trace Forest

Build a Trace Forest

Datadog logoDatadog● MediumFULLTIMEPHONE SCREEN
QuestionFunctionExamplesConstraints

Problem statement

Source note: The firsthand report supplies unordered spans, null or missing-parent roots, timestamp-sorted children and the full six-span example. This exercise uses parallel arrays and preorder rows for the three reported fields; root order, equal-time ties, valid IDs and bounds are specified for practice. The core task matches the report at about 90%.

Build a trace forest from an unordered list of spans. Parallel arrays give each span's ID, original parent ID and start timestamp. An empty parent ID means no parent. If a nonempty parent ID does not occur among the span IDs, the span is an orphan and also becomes a root. Otherwise attach it as a child of that parent, even when the parent appears later in the input.

Keep roots in their original input order. Within each parent, sort its direct children by increasing start timestamp; break equal-time ties by original input order. Do not globally sort unrelated spans.

Output adapter: represent the resulting nested forest by preorder rows [spanId, originalParentId, startTime, depth], with all four entries strings. Start each root at depth zero, output a node before its children, and finish its whole subtree before the next root. Write numeric entries in ordinary decimal notation. Preserve the original parent ID in every row, including an orphan's missing parent name. These rows encode the full hierarchy and child ordering for the three reported metadata fields. An empty input returns an empty array.

Function

buildTraceForest(spanIds: String[], parentIds: String[], startTimes: long[]) → String[][]

Examples

Example 1

spanIds = ["span_1","span_2","span_3","span_4","span_5","span_7"]parentIds = ["","span_1","span_1","span_2","span_6",""]startTimes = [300,500,300,500,600,1000]return = [["span_1","","300","0"],["span_3","span_1","300","1"],["span_2","span_1","500","1"],["span_4","span_2","500","2"],["span_5","span_6","600","0"],["span_7","","1000","0"]]

The roots are span_1, orphan span_5, and span_7, in their input order. The children of span_1 are span_3 at time 300 followed by span_2 at 500. Span span_4 is below span_2 at depth two. The orphan keeps its original missing parent name span_6.

Example 2

spanIds = ["c","b","a"]parentIds = ["a","","b"]startTimes = [5,7,3]return = [["b","","7","0"],["a","b","3","1"],["c","a","5","2"]]

Span b is the only root. Although c appears before its parent a, it attaches below a, which attaches below b. Preorder is b,a,c, with depths 0,1,2. Parent timestamps do not control ancestry.

Example 3

spanIds = []parentIds = []startTimes = []return = []

There are no spans, so the forest and its preorder encoding are empty.

Constraints

  • 0 <= spanIds.length <= 100
  • spanIds.length == parentIds.length and spanIds.length == startTimes.length.
  • Every span ID has between 1 and 32 characters. Span IDs are unique.
  • Every parent ID has between 0 and 32 characters; the empty string means no parent.
  • Nonempty IDs contain only ASCII letters, digits, underscores and hyphens.
  • 0 <= startTimes[i] <= 1000000000
  • Following links to existing parents never forms a cycle.

More Datadog problems

  • Query Log MatchPHONE SCREEN · ONSITE INTERVIEW · Seen Sep 2026
  • Delete a Filesystem TreePHONE SCREEN · ONSITE INTERVIEW · Seen Jul 2026
  • Grouped-Query Attention Forward PassPHONE SCREEN · Seen Jun 2026
All Datadog interview questionsSee Datadog hiring insights
Saved
public String[][] buildTraceForest(String[] spanIds, String[] parentIds, long[] startTimes) {
    // Write your code here.
}
Checking account…