How should I practice Minimum Rounds to Inform an N-ary Tree?

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

Is Minimum Rounds to Inform an N-ary Tree associated with Rippling?

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

Minimum Rounds to Inform an N-ary Tree

Rippling● HardINTERNFULLTIMEPHONE SCREEN

Learn

Problem statement

An n-ary tree is represented by parent. Node 0 is the root, parent[0] = -1, and each other entry gives that node's parent.

At time zero only the root knows a message. In each round, every node that already knew the message at the beginning of the round may send it to at most one of its children that does not yet know it. Different informed nodes may send simultaneously. A child informed during a round can first send in the next round.

You may choose each node's child order. Return the minimum number of rounds needed to inform every node.

Function

minimumBroadcastRounds(parent: int[]) → int

Examples

Example 1

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

The root has three children and can inform only one per round, so three rounds are necessary.

Example 2

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

Inform node 1 first. In round two the root informs node 2 while node 1 informs node 3. Node 3 informs node 4 in round three.

Constraints

1 <= parent.length <= 20000.
The array describes one valid tree rooted at 0.
A parent index need not be smaller than its child index.