Tree Node With Maximum Beauty
Updated
Problem statement
You are given a tree with treeNodes nodes labeled from 1 to treeNodes. For each index i, there is an undirected edge between nodes treeFrom[i] and treeTo[i]. Every edge has length 1, so the distance d(i, j) between two nodes is the number of edges on the path between them, and d(i, i) = 0.
You are also given an array a of length treeNodes, where a[j - 1] is the weight of node j.
The beauty of node i is the sum of d(i, j) * a[j - 1] over every node j in the tree.
Return the label of the node with the largest beauty. If several nodes share the largest beauty, return the smallest of their labels.
Function
findMaxBeautyNode(treeNodes: int, treeFrom: int[], treeTo: int[], a: int[]) → intExamples
Example 1
treeNodes = 4treeFrom = [1,3,2]treeTo = [2,2,4]a = [4,3,2,1]return = 4Node 2 is joined to nodes 1, 3 and 4. The beauties are:
- Node 1:
0 * 4 + 1 * 3 + 2 * 2 + 2 * 1 = 9 - Node 2:
1 * 4 + 0 * 3 + 1 * 2 + 1 * 1 = 7 - Node 3:
2 * 4 + 1 * 3 + 0 * 2 + 2 * 1 = 13 - Node 4:
2 * 4 + 1 * 3 + 2 * 2 + 0 * 1 = 15
Node 4 has the largest beauty, so the answer is 4.
Example 2
treeNodes = 3treeFrom = [1,2]treeTo = [2,3]a = [1,1,1]return = 1The tree is the path 1 - 2 - 3. Node 1 has beauty 0 + 1 + 2 = 3, node 2 has 1 + 0 + 1 = 2, and node 3 has 2 + 1 + 0 = 3. Nodes 1 and 3 tie, so return the smaller label, 1.
Example 3
treeNodes = 1treeFrom = []treeTo = []a = [5]return = 1With one node, every distance is 0, so node 1 has beauty 0 and is the answer.
Constraints
1 <= treeNodes <= 2 * 10^4treeFrom.length == treeTo.length == treeNodes - 11 <= treeFrom[i], treeTo[i] <= treeNodes- The edges form a tree: all nodes are connected and there are no cycles.
a.length == treeNodes0 <= a[i] <= 10^4
More C3.ai interview questions
- Drop Recent Duplicate MessagesOA · Seen Oct 2026
- Maximum K-Star SumOA · Seen Oct 2026
- Largest Square Sub-Grid Within a Sum LimitOA · Seen Jan 2023
- Prefix Scores With the Running MaximumOA · Seen Jan 2023
- Count Vowel Strings With Follow RulesOA · Seen Apr 2022
- Photo Album Insert OrderOA · Seen Apr 2022
- Sort by Frequency, Then ValueOA · Seen Apr 2022
- Count Distinct Binary Search TreesOA · Seen Mar 2022
- Count Palindromic Subsequences of Length KOA · Seen Mar 2022
- Fewest Turns to Open a Wheel LockPHONE SCREEN · Seen Nov 2024
Similar questions at other companies
- Minimum Leaf Path Sum over All RootsInfosys · OAInfosys interview questions
- Maximum Strength of Every NeuronMicrosoft · OAMicrosoft interview questions
- Maximum Reservoir PowerWells Fargo · OAWells Fargo interview questions
- Sum of Weighted Distances in a TreeGoogle · ONSITE INTERVIEWGoogle interview questions
- Distance Sums to Special Nodes in a Weighted TreeNutanix · ONSITE INTERVIEWNutanix interview questions
- Part 2: Batch Access ReviewScale AI · OAScale AI interview questions
- Sum Dynamic Weighted Tree DistancesJuspay · OA
- Binary Tree CamerasAmazon · OA · PHONE SCREEN
- Special Diameter EndpointsAgoda · OAAgoda interview questions
- Tree PointsThe D.E. Shaw Group · OAThe D.E. Shaw Group interview questions