How should I practice Maximum Average N-ary Subtree?

Start by reading the full statement, solve the visible examples, then compare the pattern against related Rippling phone screen problems in FastPrep.

Is Maximum Average N-ary Subtree associated with Rippling?

FastPrep tags this as a Rippling phone screen coding practice problem when the problem catalog has that company and stage context.

Maximum Average N-ary Subtree

Rippling● MediumINTERNFULLTIMEPHONE SCREEN

Learn

Problem statement

An n-ary tree has nodes 0 through n - 1. Node 0 is the root, parent[0] = -1, and parent[i] is the parent of every other node. Node i has integer value values[i].

The subtree rooted at a node contains that node and all its descendants. Consider only roots with at least one child. Return the index of the candidate subtree with the greatest average node value. Compare averages exactly. If several candidates tie, return the smallest root index. Return -1 if there is no candidate.

Function

maximumAverageSubtree(parent: int[], values: int[]) → int

Examples

Example 1

parent = [-1,0,0,1,1,1,2,2]values = [20,12,18,11,2,3,15,8]return = 2

The averages at candidate roots 0, 1, and 2 are 89/8, 28/4, and 41/3. Node 2 is best.

Example 2

parent = [-1,0,0,1]values = [0,0,0,0]return = 0

Both candidate roots 0 and 1 have average zero. The smaller index wins.

Constraints

1 <= n == parent.length == values.length <= 20000.
The parent array describes one valid tree rooted at 0; a parent index need not be smaller than its child index.
-10000 <= values[i] <= 10000.