Delete and Compact a Forest Stored by Parent Indices

Question

The question asks the candidate to implement a function that deletes a subtree from a forest represented by an array of parent indices, marking the target node and all its descendants with -1.

Codemia · Accepted Answer

To solve the problem, we can use a Depth-First Search (DFS) approach to traverse the tree and mark the target node and all its descendants with -1. After marking, we will need to compact the array by shifting the remaining nodes forward and updating their parent indices accordingly.

1. Define a function `deleteSubtree(parentIndex, target)` that takes the parent index array and the target node.
2. Use a DFS helper function to traverse the tree:
   - If the current node is the target, mark it as -1.
   - Recursively call the DFS for all children of the current node.
3. After marking, create a new array to store the remaining nodes and their updated indices.

The time complexity of this solution is O(n), where n is the number of nodes in the forest, since we are visiting each node once. The space complexity is O(h) for the recursion stack, where h is the height of the tree.

```python
def deleteSubtree(parentIndex, target):
    n = len(parentIndex)
    marked = set()

def dfs(node):
        if node in marked:
            return
        marked.add(node)
        for i in range(n):
            if parentIndex[i] == node:
                dfs(i)

# Mark the target and its descendants
    dfs(target)

# Compact the array
    new_index = 0
    new_parentIndex = [-1] * n
    for i in range(n):
        if i not in marked:
            new_parentIndex[new_index] = parentIndex[i] if parentIndex[i] not in marked else -1
            new_index += 1
    return new_parentIndex
```

Interviewers look for clarity in the candidate's explanation of the approach, the correctness of the implementation, and the ability to handle edge cases. They also assess the candidate's understanding of the underlying data structures and algorithms used in the solution.

Delete and Compact a Forest Stored by Parent Indices

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