Delete and Compact a Forest Stored by Parent Indices
Company: Pinterest
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
## Problem
A forest is stored in an integer array `parent`, where node `i` is a root when `parent[i] == i`; otherwise `parent[i]` is the index of its parent. Delete a target node and every descendant. When `compact` is false, keep the array length and set each deleted entry to `-1`. When `compact` is true, remove deleted entries, preserve the relative order of surviving nodes, and rewrite every surviving parent index to its new index.
### Function Contract
Implement `delete_subtree(parent, target, compact) -> list[int]`. The input array must not be mutated.
### Constraints
- `1 <= len(parent) <= 200000`.
- `0 <= target < len(parent)`.
- Every non-root parent index is valid, and the input contains no directed cycle other than each root's self-loop.
- If `compact` is true, every surviving root must still point to its own new index.
### Examples
- `parent = [0, 0, 0, 2, 4, 4]`, `target = 2`, `compact = false` returns `[0, 0, -1, -1, 4, 4]`.
- The same input with `compact = true` returns `[0, 0, 2, 2]`.
```hint Build child links once
The parent array points upward. A reverse adjacency list lets one traversal discover exactly the target's descendants.
```
```hint Map old indices to new indices
After deciding which nodes survive, assign their compacted indices before rewriting any parent reference.
```
### Edge Cases
- Deleting a root removes only that root's tree, not the other trees.
- Deleting a leaf changes one entry in non-compacting mode.
- The target may be the only node in the forest.
Overview: Delete a target node and all descendants from a forest represented by parent indices. Support both tombstoning and compacting modes, preserve survivor order, rewrite parent references correctly, and keep every surviving root self-referential.
A forest is stored in parent, where node i is a root when parent[i] equals i and otherwise parent[i] is its parent index. Delete the target node and every descendant without mutating parent. If compact is false, preserve the array length and write -1 at every deleted index. If compact is true, remove deleted entries, preserve survivor order, and rewrite each surviving parent to its new index; every surviving root must point to its own new index.
Constraints
- 1 <= len(parent) <= 200000.
- 0 <= target < len(parent).
- A root i satisfies parent[i] == i; every other parent index is valid.
- The forest has no directed cycle except each root's self-loop.
- The input array must not be mutated.
- After compaction every surviving root points to its own new index.
Examples
Input: ([0, 0, 0, 2, 4, 4], 2, False)
Expected Output: [0, 0, -1, -1, 4, 4]
Explanation: Nodes 2 and 3 are deleted while indices are retained.
Input: ([0, 0, 0, 2, 4, 4], 2, True)
Expected Output: [0, 0, 2, 2]
Explanation: Surviving old nodes 0, 1, 4, and 5 are remapped to indices 0 through 3.
Hints
- Build reverse child links so descendants can be found from the target.
- Assign old-to-new indices before rewriting any parent reference.