Process Tree Recovery - Tree Reconstruction Coding Interview

Question

## Problem

A system crash corrupted a process tree. You are given a flat list of process records, each with `(pid, ppid, name)`, but some parent processes are missing from the list (their records were lost). Reconstruct as much of the tree as possible and return:
1. All root-level nodes (processes whose parent is missing or ppid=0).
2. For each subtree, a nested dict representation.

```python
def recover_tree(processes: list[tuple[int,int,str]]) -> list[dict]:
    # Each returned dict: {"pid": int, "name": str, "children": [...]}
    ...
```

**Example:**
```
processes = [(1,0,"init"),(3,1,"bash"),(5,3,"vim"),(7,99,"orphan")]
Output: [
  {"pid":1,"name":"init","children":[
    {"pid":3,"name":"bash","children":[
      {"pid":5,"name":"vim","children":[]}
    ]}
  ]},
  {"pid":7,"name":"orphan","children":[]}
]
```

## Follow-ups
- How do you detect and handle cycles in the parent references?
- Extend to return the path from any given pid to its root.
- Given memory pressure: if only top-3 levels of the tree can be kept in memory, how do you reconstruct level by level?

Process Tree Recovery - Tree Reconstruction Coding Interview

Question Details

Full Details

Topics

More from Bloomberg