A distributed trace describes how one request fans out through a set of spans. In this simplified model, the spans form a rooted tree and each span contributes its duration to any path that contains it.
Design a TraceCriticalPathAnalyzer class:
TraceCriticalPathAnalyzer() creates a stateless analyzer.int criticalPath(int[][] spans) returns the largest duration sum along any path from the trace root to a leaf.
Each row of spans has the form:
Exactly one span is the root and has parentId = -1. Every other parentId names another span in the input. Rows may appear in any order.
For this exercise, sibling spans are alternative branches. A span's critical path is its own duration plus the largest critical path among its children. Each method call is independent.
Example 1:
Input:
Output:
Explanation: The root has two branches. Path 1 -> 2 totals 10 + 5 = 15, while path 1 -> 3 -> 4 totals 10 + 8 + 2 = 20.
Example 2:
Input:
Output:
Explanation: Path 10 -> 30 totals 10, while path 10 -> 20 -> 40 totals 11, so the latter is critical.
Constraints
1 <= spans.length <= 500spans[i].length == 3- Span IDs are unique positive integers.
- Exactly one row has
parentId == -1. - Every other parent ID exists in
spans, and the relationships form a tree. 0 <= duration <= 10^6- The answer fits in a signed 32-bit integer.
- At most
100 calls are made to criticalPath.
Find a Trace Critical Pathhard