Maximum-Scoring Consecutive Tree Levels
Updated
Problem statement
You are given a rooted tree with n nodes, numbered from 0 to n - 1. Node 0 is the root, and parent[0] is -1. For every other node i, parent[i] is the parent of node i.
The depth of the root is 0. The depth of any other node is one more than the depth of its parent. All nodes with the same depth form one level.
The nodes listed in selected are selected. Every node gets exactly one score, from the first rule below that applies to it:
- If the node is selected, its score is
n1. - Otherwise, if the node is a sibling of a selected node, its score is
n2. Siblings are different nodes with the same parent. - Otherwise, if the node is an ancestor of a selected node, its score is
n3. The ancestors of a node are its parent, its parent's parent, and so on up to the root. - Otherwise, its score is
0.
Choose levelCount consecutive levels of the tree. The chosen levels must include the level of node target. Return the largest possible total score of all nodes in the chosen levels.
Function
maxConsecutiveLevelScore(parent: int[], selected: int[], n1: int, n2: int, n3: int, levelCount: int, target: int) → longExamples
Example 1
parent = [-1,0,0,1,1,2,4,4]selected = [6,5]n1 = 5n2 = 3n3 = 2levelCount = 2target = 2return = 11Node 0 has children 1 and 2. Node 1 has children 3 and 4, node 2 has child 5, and node 4 has children 6 and 7.
The scores are:
- Nodes
5and6are selected, so each scores5. - Node
7is a sibling of6, so it scores3. Node5has no siblings. - Nodes
0,1,2, and4are ancestors of a selected node, so each scores2. - Node
3scores0. It is a sibling of4, but4is not selected.
The level totals are: level 0 is 2, level 1 is 2 + 2 = 4, level 2 is 0 + 2 + 5 = 7, and level 3 is 5 + 3 = 8.
Node 2 is on level 1. The two-level choices that include level 1 are levels 0-1 with 2 + 4 = 6 and levels 1-2 with 4 + 7 = 11. The answer is 11.
Example 2
parent = [-1,0,0,1,1,2,4,4]selected = [6,5]n1 = 5n2 = 3n3 = 2levelCount = 3target = 0return = 13This is the same tree and the same scores as Example 1. Levels 1-3 would give 4 + 7 + 8 = 19, but they do not include level 0, where node 0 is.
The only three-level choice that includes level 0 is levels 0-2, with total 2 + 4 + 7 = 13.
Example 3
parent = [-1,0,0,1]selected = [2,3]n1 = 10n2 = 4n3 = 7levelCount = 2target = 1return = 24Node 0 has children 1 and 2, and node 1 has child 3. Nodes 2 and 3 are selected, so each scores 10.
Node 1 is a sibling of 2 and also an ancestor of 3. The sibling rule comes first, so node 1 scores 4, not 7. Node 0 is an ancestor of both, so it scores 7.
The level totals are 7, 4 + 10 = 14, and 10. Node 1 is on level 1. Levels 0-1 give 21 and levels 1-2 give 24, so the answer is 24.
Constraints
1 <= n <= 10^4, wherenis the length ofparentparent[0] == -1, and0 <= parent[i] < ifor every1 <= i < n0 <= selected.length <= n- The values in
selectedare all different, and each one is from0ton - 1. 0 <= n1, n2, n3 <= 10^90 <= target <= n - 11 <= levelCount <= h + 1, wherehis the largest depth of any node
More Jane Street interview questions
- Tree Selection and VisibilityPHONE SCREEN · Seen Nov 2026
- Load/Store Arithmetic InterpreterPHONE SCREEN · Seen Oct 2026
- Instrument Stack Language JumpsPHONE SCREEN · Seen Oct 2026
- Run a Stack Language InterpreterPHONE SCREEN · Seen Oct 2026
- Positive-Integer Expression EvaluationPHONE SCREEN · Seen Oct 2026
- Code Editor FoldingONSITE INTERVIEW · Seen Oct 2026
- Exact-Sixty Dice Game ValueONSITE INTERVIEW · Seen Oct 2026
- Expected Value of Modified DiceONSITE INTERVIEW · Seen Oct 2026
- Spaceship Equipment LoadoutONSITE INTERVIEW · Seen Oct 2026
- Two-Tower Strategy GameONSITE INTERVIEW · Seen Oct 2026
Similar questions at other companies
- Minimum Edits to a Perfect Binary TreeSnowflake · PHONE SCREENSnowflake interview questions
- Find All Paths for a Name in a File SystemThe Walt Disney Company · PHONE SCREENThe Walt Disney Company interview questions
- Binary Tree Spiral Level OrderAmazon · PHONE SCREEN · ONSITE INTERVIEW
- Check a Complete Binary TreeGoldman Sachs · PHONE SCREENGoldman Sachs interview questions
- Binary Tree Right Side ViewGoogle · PHONE SCREEN · ONSITE INTERVIEWGoogle interview questions
- Same Binary TreeOdoo · PHONE SCREENOdoo interview questions
- Binary Tree Zigzag Level Order TraversalLinkedIn · PHONE SCREEN · ONSITE INTERVIEWLinkedIn interview questions
- Insert an Employee into an Organization HierarchyWaymo · PHONE SCREENWaymo interview questions
- Bottom View of a Binary TreeOracle · PHONE SCREEN · ONSITE INTERVIEWOracle interview questions
- Maximum Value for Two Delivery RobotsNuro · PHONE SCREENNuro interview questions