How should I practice Maximum Invitations on 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 Maximum Invitations on 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.

Maximum Invitations on an N-ary Tree

Rippling● MediumINTERNFULLTIMEPHONE SCREEN

Learn

Problem statement

An n-ary tree has nodes 0 through n - 1, with root 0. The array parent has parent[0] = -1; every other entry names that node's parent.

Choose as many nodes as possible to receive invitations. Two nodes connected by a tree edge cannot both receive an invitation. Return the maximum number of invited nodes. Every node contributes one invitation; there are no node weights.

Function

maximumInvitations(parent: int[]) → int

Examples

Example 1

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

Inviting nodes 2, 3, and 4 is valid. No selection can contain more than three nodes.

Example 2

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

Invite all three leaves and leave the root uninvited.

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.