How should I practice Delete and Compact a Forest Subtree?

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

Is Delete and Compact a Forest Subtree associated with Pinterest?

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

Problem · Array

Delete and Compact a Forest Subtree

Learn this problem

● Medium

PinterestFULLTIMEPHONE SCREEN

Problem statement

A forest of nodes numbered from 0 through n - 1 is represented by parent. Every root points to itself, and every nonroot entry is the index of its parent.

Delete the node deleteIndex and its entire subtree. Keep surviving nodes in their original relative order, assign them consecutive new indices beginning at 0, and return their remapped parent array. A surviving root points to its own new index.

If every node is deleted, return an empty array.

Function

deleteAndCompactSubtree(parent: int[], deleteIndex: int) → int[]

Examples

Example 1

parent = [0,0,0,2,4,4]deleteIndex = 2return = [0,0,2,2]

Survivors 0, 1, 4, and 5 become indices 0 through 3.

Example 2

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

Removing the last leaf leaves all earlier indices unchanged.

Example 3

parent = [0,0,2,2,4]deleteIndex = 0return = [0,0,2]

Surviving roots and their children are remapped after the removed prefix.

Constraints

1 <= parent.length <= 200000.
0 <= parent[i] < parent.length.
The parent links form a valid forest whose only cycles are self-pointing roots.
0 <= deleteIndex < parent.length.