Best Sum Downward Tree Path
Updated
Problem statement
For a tree with n nodes rooted at node 0 (nodes numbered from 0 to n-1), where each node i has a value given by values[i], determine the maximum sum of values along any path that starts at a node u and only goes downward in the tree.
Consider only paths of the form u₁, u₂, u₃, ..., uₖ where each node uᵢ is a child of node uᵢ₋₁ for 1 < i ≤ k. For example, given the following tree (labeled node number/value):
Two possible paths are 0 → 1 → 2 → 3 which has a sum of 5 + 7 + (-10) + 4 = 6 and 1 → 2 → 3 with a sum of 7 + (-10) + 4 = 1. The highest sum path is 0 → 4 with a sum of 5 + 15 = 20.
Function
bestSumDownwardTreePath(parent: int[], values: int[]) → int
Complete the function bestSumDownwardTreePath in the editor with the following parameter(s):
int parent[n]: eachparent[i]represents the parent node for nodei,parent[i] = -1means nodeiis the rootint values[n]: eachvalues[i]represents the value of nodei
Returns
int: the largest sum of values along a path down the tree from any node u
Examples
Example 1
parent = [-1, 0, 1, 2, 0]values = [5, 7, -10, 4, 15]return = 20The downward path 0 → 4 has value sum 5 + 15 = 20, which is greater than every other downward path.
Constraints
1 ≤ n ≤ 10⁵parent[0] = -10 ≤ parent[i] < nfor0 < i < n-1000 ≤ values[i] ≤ 1000- the tree described is valid
More Citadel interview questions
- Portfolio Tickers with Constant-Time Random PickPHONE SCREEN · Seen Nov 2026
- Square Root FunctionPHONE SCREEN · Seen Oct 2026
- Reachable Transfer PositionsPHONE SCREEN · Seen Oct 2026
- Spreadsheet Formula DependenciesPHONE SCREEN · Seen Oct 2026
- Possible MEX Values After One Optional IncrementOA · Seen Oct 2026
- Merge Price-Delta FeedsPHONE SCREEN · Seen Sep 2026
- Reconcile Unmatched Trades with Timestamp TolerancePHONE SCREEN · Seen Sep 2026
- Top Ten Trades by Notional ValuePHONE SCREEN · Seen Sep 2026
- Busy IntersectionOA · Seen Sep 2026
- Shortest Path in an Unweighted GraphOA · Seen Sep 2026
Similar questions at other companies
- Longest Alternating a/b Path in a TreeHudson River Trading · OAHudson River Trading interview questions
- Maximum Reservoir PowerWells Fargo · OAWells Fargo interview questions
- Minimum Leaf Path Sum over All RootsInfosys · OAInfosys interview questions
- Part 2: Batch Access ReviewScale AI · OAScale AI interview questions
- Binary Tree CamerasAmazon · OA · PHONE SCREEN
- Maximum Sum Path Between Two Leaf NodesGoogle · OAGoogle interview questions
- Maximum Strength of Every NeuronMicrosoft · OAMicrosoft interview questions
- Tree PointsThe D.E. Shaw Group · OAThe D.E. Shaw Group interview questions
- Binary Tree Maximum Path SumArcesium · OAArcesium interview questions
- Tree Node With Maximum BeautyC3.ai · OAC3.ai interview questions
Citadel interview experiences
- Citadel Securities Quant Researcher Intern Loop: 1 Experience
- Citadel Securities Research Engineer Interview: 1 Experience
- Citadel Securities SWE Intern First Round: 2 Experiences
- Citadel Securities Experienced SWE Interviews: 1 Experience
- Citadel SWE Intern Later Rounds and Superday: 13 Experiences
- Citadel SWE Intern First-Round Questions: 20 Experiences