Robber on a Tree
Updated
Problem statement
A tree has nodes 1..n rooted at 1, with parents[v-1] the parent of v and parents[0]=0. At time 0 you stand at root 1 and a robber stands at leaf robber. Each second you move one edge along a chosen root-to-leaf path; the robber moves one edge along its unique path to the root. Each stops upon reaching its destination.
The first person to reach a node receives all its coin value, leaving zero. If both arrive at the same time, each receives half. Coin values may be negative. You must reach a leaf without waiting. Return the maximum total you can receive.
Function
robberOnTree(parents: int[], coins: int[], robber: int) → longExamples
Example 1
parents = [0,1,1,2,2,3,3]coins = [2,4,6,2,2,6,8]robber = 7return = 11Taking path 1,3,6 gives 2+3+6=11.
Example 2
parents = [0,1]coins = [-4,10]robber = 2return = -4You collect the negative root value; the robber already emptied its leaf.
Constraints
- 2 <= n <= 100000 and -10000 <= coins[i] <= 10000.
- For this exercise, assume coins are even integers, the parent array is a valid rooted tree, and robber is a nonroot leaf. Return a signed 64-bit total.
More Intuit Online Assessment questions
- Employee Promotion OpportunitiesOA · Seen Oct 2026
- Next Pascal Row CoefficientOA · Seen Oct 2026
- Parse Router LogsOA · Seen Oct 2026
- Longest Repeated Letter Block with Adjacent SwapsOA · Seen Oct 2026
- Maximum Square-Free DivisorOA · Seen Oct 2026
- Two Tribes from Taller-Person CountsOA · Seen Oct 2026
- Shortest Path from an Encoded GraphOA · Seen Sep 2026
- Oldest and Youngest EmployeesOA · Seen Sep 2026
- Pressure-Isolation Shutdown OrderOA · Seen Sep 2026
- Submask Sum QueriesOA · Seen Sep 2026
Similar questions at other companies
- Base Unit ConversionsAdobe · OAAdobe interview questions
- Count Prime Values in SubtreesVisa · OAVisa interview questions
- Part 1: The Narrowest KeyScale AI · OAScale AI interview questions
- Sewer Drainage PartitionTwo Sigma · OATwo Sigma interview questions
- Count Balanced Nodes in a Rooted TreeDRW · OADRW interview questions
- Chain of CommandIMC Trading · OAIMC Trading interview questions
- Construct Binary Tree S-ExpressionOptiver · OAOptiver interview questions
- Chain of CommandUber · OAUber interview questions
- Maximum Data Transfer TimeMicrosoft · OAMicrosoft interview questions
- Build and Render an Organization Role TreeStripe · OAStripe interview questions