Mark and Compact a Heap-Indexed Subtree
Company: Pinterest
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Take-home Project
# Mark and Compact a Heap-Indexed Subtree
An interview report describes an array-encoded tree, marking a target and its descendants with `-1`, then moving all `-1` values to the right. The exact encoding is not preserved, so use this explicit practice interpretation: the input is a dense binary tree in heap-index order.
```python
def remove_subtree_and_compact(
tree: list[int],
target: int,
) -> list[list[int]]:
...
```
For an index `i`, its children are at `2 * i + 1` and `2 * i + 2` when those indices exist. Values are unique and `-1` is reserved as the removal marker.
Perform two phases:
1. Find the node whose value equals `target` and replace it and every heap-indexed descendant with `-1`. If `target` is absent, make no replacements.
2. Stable-compact the marked array by moving every non-`-1` value to the left in its existing order, followed by the same number of `-1` markers.
Return `[marked, compacted]`, where both elements are new arrays of the same length as `tree`. The compacted array is an array-transformation result; after indices move, it is not claimed to preserve the original heap parent-child relationships.
## Example
```text
Input: tree = [10, 20, 30, 40, 50, 60, 70]
target = 20
Marked: [10, -1, 30, -1, -1, 60, 70]
Compacted: [10, 30, 60, 70, -1, -1, -1]
Output:
[
[10, -1, 30, -1, -1, 60, 70],
[10, 30, 60, 70, -1, -1, -1]
]
```
## Constraints and Errors
- `0 <= len(tree) <= 200_000`
- Every value is an integer in `[-10**9, 10**9]` except that `-1` is forbidden in the input.
- Values are unique.
- `target` must be an integer other than `-1`; Boolean values do not count as integers.
- An invalid value type, duplicate value, reserved marker, or invalid target raises `ValueError`.
- Validate all inputs before producing output and do not mutate `tree`.
## Hints
- Descendant indices can be discovered with a stack or queue without building node objects.
- Bounds checks stop traversal below leaves.
- Stable compaction can be built from the surviving values plus the removed count.
Quick Answer: In a dense heap-indexed binary tree array, mark a target node and all indexed descendants with -1, then stable-compact the survivors. Return separate marked and compacted arrays, validate reserved values and uniqueness, and never mutate the input.
In a dense heap-indexed binary tree array, mark the target value and every indexed descendant as -1, then stable-compact all surviving values left and append the same number of -1 markers. Return independent marked and compacted arrays.
Constraints
- Tree values are unique integers and -1 is reserved.
- The target is an integer other than -1.
- Children of index i are 2*i+1 and 2*i+2 when in bounds.
- An absent target causes no replacements.
- Validate inputs and do not mutate tree.
Examples
Input: ([], 5)
Expected Output: [[], []]
Explanation: An empty tree returns two empty arrays.
Input: ([10, 20, 30, 40, 50, 60, 70], 20)
Expected Output: [[10, -1, 30, -1, -1, 60, 70], [10, 30, 60, 70, -1, -1, -1]]
Explanation: The prompt subtree rooted at index one is removed and compacted.
Hints
- Map the target value to its index during validation.
- Use a stack of indices to visit only descendants in bounds.
- Build the compacted list from surviving values followed by markers.