How should I practice Minimum N-ary Tree Depth Deletions?

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

Is Minimum N-ary Tree Depth Deletions associated with Snowflake?

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

Minimum N-ary Tree Depth Deletions

Snowflake● MediumFULLTIMEPHONE SCREEN

Problem statement

You are given a rooted n-ary tree with nodes labeled 1 through n. Node 1 is the root; parent[i - 2] is the parent of node i. The root has depth 1, and tree height counts nodes on a longest root-to-leaf path.

You may delete any non-root node. Deleting it attaches all its current children directly to its parent. The root must remain, and repeated deletions leave one rooted tree.

Find a minimum-cardinality deletion set that makes the resulting height at most k. To select one deterministic optimum, return, in ascending ID order, exactly the non-root nodes whose original subtree height is at least k. A leaf has subtree height 1. This set is always optimal; other optimal sets may exist. If no deletion is needed, return an empty array. The number of returned IDs is the minimum deletion count.

For this exercise, the ascending-set result preserves the callable interface. The returned IDs identify one optimal set, and their count is the minimum number of deletions.

Function

minimumDepthDeletions(parent: int[], k: int) → int[]

Examples

Example 1

parent = [1,1,1,2,2]k = 2return = [2]

Delete internal node two to promote both children.

Example 2

parent = [1,2,3]k = 1return = [2,3,4]

Keep only the root of a four-node chain.

Example 3

parent = [1,1,1]k = 3return = []

A short star already satisfies the height limit.

Constraints

1 <= n = parent.length + 1 <= 200000.
The parent array describes one valid tree rooted at 1; parent IDs need not be smaller than child IDs.
1 <= k <= 200000.
The root is never deleted. Return the specified optimum in ascending node-ID order.