Kill Process

Kill Process

1. What is this problem about?

The Kill Process interview question simulates a process management system in an operating system. You are given two arrays: pid (process IDs) and ppid (parent process IDs). These arrays together represent a tree structure of processes. When you "kill" a specific process, all its children and their descendants must also be killed. Your goal is to return a list of all IDs that should be terminated.

2. Why is this asked in interviews?

Companies like Goldman Sachs and Microsoft use the Kill Process coding problem to test a candidate's ability to represent and traverse hierarchical data. It tests whether you can convert a pair of arrays into a more useful structure like an Adjacency List. It evaluations your mastery of Tree interview patterns and graph search algorithms.

3. Algorithmic pattern used

This problem is solved using Graph Traversal (BFS or DFS).

1. Pre-processing: Build a Hash Map where the key is the ppid and the value is a list of its children pids. This effectively transforms the parent pointers into a directed tree.
2. Traversal: Use a queue (BFS) or stack (DFS) starting with the process ID you want to kill.
3. Collection: While the queue/stack is not empty:
   • Pop a process ID and add it to your result list.
   • For all children of this process (found in your map), add them to the queue/stack.
4. Efficiency: The pre-processing is $O(N)$ and the traversal is $O(K)$ where $K$ is the number of descendants.

4. Example explanation

pid = [1, 3, 10, 5], ppid = [3, 0, 5, 3]. Kill process 5.

1. Map: 0: [3], 3: [1, 5], 5: [10].
2. BFS Start: Queue = [5].
3. Pop 5. Children of 5 is [10]. Queue = [10].
4. Pop 10. No children. Result: [5, 10].

5. Common mistakes candidates make

• Linear Search: Searching the ppid array for children at every step ($O(N^2)$), which is too slow. The Hash Map is essential for $O(N)$ time.
• Cycle Confusion: Thinking the process tree might have cycles. By definition, a process hierarchy is a tree (or a forest), so no cycle detection is needed.
• Handling the Root: Forgetting that if you kill the absolute parent (PPID 0), all processes must be terminated.

6. Interview preparation tip

Whenever you are given parent-child relationships in two arrays, your first step should almost always be to build an Adjacency List. This is a foundational Hash Table interview pattern for all tree and graph problems.