Remove and Compact a Parent-Index Forest

Question

The question asks the candidate to implement a function that removes and compacts a forest of TreeNodes based on their parent indices.

Codemia · Accepted Answer

To tackle this problem, we need to traverse the forest and identify which nodes should be removed based on their parent indices. We will maintain a list of valid nodes while ensuring that we compact the forest by removing any nodes that do not have valid parents.

We can use a single pass through the forest to build a mapping of valid nodes. Here’s a high-level outline of the algorithm:

1. Initialize a set to keep track of valid indices.
2. Iterate through each TreeNode in the forest:
   - If the parent index is valid (within bounds), add the current node's index to the valid set.
3. Create a new list to store the compacted forest.
4. Iterate through the original forest again, adding nodes to the new list only if their indices are in the valid set.

The time complexity of this approach is O(n), where n is the number of nodes in the forest, since we are making two passes through the data. The space complexity is also O(n) due to the storage of valid indices.

Here is a Python implementation of the described algorithm:

```python
class TreeNode:
    def __init__(self, parent_idx):
        self.parent_idx = parent_idx

def remove_and_compact_forest(forest):
    valid_indices = set()
    for i, node in enumerate(forest):
        if 0 <= node.parent_idx < len(forest):
            valid_indices.add(i)
    compacted_forest = [node for i, node in enumerate(forest) if i in valid_indices]
    return compacted_forest
```

This code defines a `TreeNode` class and a function `remove_and_compact_forest` that implements the logic we discussed.

It is important to consider edge cases such as:
- An empty forest, which should return an empty list.
- Nodes that reference out-of-bounds parent indices, which should be ignored in the output.
- All nodes being valid, which should return the original forest.

Remove and Compact a Parent-Index Forest

Pinterest

What the Interviewer Expects

Key Topics to Cover

How to Approach This

Possible Follow-up Questions

Sharpen Your Skills on Codemia

Sample Answer

Approach

Algorithm

Submit Your Answer

Pinterest Software Engineer Interview Guide

Related Questions

Binary Search on graph

Count kth largest element in array

Find connected components in string

Merge Three Sorted strings

Binary Search on string