Problem Description

The "Kill Process" problem involves simulating the termination of a process in an operating system, along with all of its child processes (and their descendants). You are given three lists:

• pid: a list of unique process IDs.
• ppid: a list where ppid[i] is the parent process ID of pid[i].
• kill: the process ID of the process you want to terminate.

When you "kill" a process, all of its child processes (and their children, recursively) should also be terminated. The goal is to return a list of all process IDs that will be killed as a result, in any order.

Constraints:

• There is exactly one process with ppid = 0 (the root process).
• No process has more than one parent.
• Each process is uniquely identified by its pid.
• There is always a valid solution.

Thought Process

The core challenge is to efficiently find all descendants of a given process. At first glance, you might think to check, for each process, whether it is a descendant of the process to be killed. However, this would be very inefficient, especially as the number of processes grows.

Instead, it's helpful to think of the processes as forming a tree (or forest) where each process points to its children. If we can quickly look up all children of a process, we can traverse the tree starting from the process to be killed, collecting all descendants along the way.

This naturally suggests building a mapping from parent process IDs to their child process IDs, and then using a traversal (such as BFS or DFS) to gather all processes to kill.

Solution Approach

Here’s how we can systematically solve the problem:

1. Build the Parent-to-Children Map:
   • Iterate through the pid and ppid lists together.
   • For each pair, add the pid as a child under the corresponding ppid in a hash map (dictionary).
2. Traverse the Process Tree:
   • Start with the process to kill (kill).
   • Use either Depth-First Search (DFS) or Breadth-First Search (BFS) to visit all descendants:
     • For each visited process, add its children to the stack/queue.
     • Continue until there are no more children to visit.
3. Collect and Return Results:
   • As you traverse, collect all process IDs that are visited.
   • Return the list of these process IDs.

We use a hash map for fast lookups of children given a parent, and a stack/queue for traversal.

Example Walkthrough

Sample Input:
pid = [1, 3, 10, 5]
ppid = [3, 0, 5, 3]
kill = 3

Step 1: Build the Parent-to-Children Map

• ppid 3: children [1, 5]
• ppid 0: child [3]
• ppid 5: child [10]

Step 2: Traverse from kill = 3

• Start with [3]
• 3 has children [1, 5] → add them to the list
• Visit 1: no children
• Visit 5: has child [10] → add to the list
• Visit 10: no children

Result: All visited processes = [3, 1, 5, 10]

Time and Space Complexity

Brute-force Approach:
If you checked every process to see if it is a descendant of kill by walking up the parent chain, it would take O(N^2) time, where N is the number of processes.

Optimized Approach:

• Time Complexity: O(N), since we build the mapping in O(N) and traverse each node at most once.
• Space Complexity: O(N), for storing the parent-to-children map and the output list.

Summary

The "Kill Process" problem is a classic tree traversal problem disguised in process management terms. By mapping parents to their children and using a simple traversal, we efficiently gather all processes that should be terminated. The key insight is to represent the process relationships as a tree and use standard traversal algorithms to solve the problem in linear time.

Code Implementation

from collections import defaultdict, deque

class Solution:
    def killProcess(self, pid, ppid, kill):
        tree = defaultdict(list)
        for child, parent in zip(pid, ppid):
            tree[parent].append(child)
        result = []
        queue = deque([kill])
        while queue:
            curr = queue.popleft()
            result.append(curr)
            for child in tree[curr]:
                queue.append(child)
        return result
      

#include <vector>
#include <unordered_map>
#include <queue>
using namespace std;

class Solution {
public:
    vector<int> killProcess(vector<int>& pid, vector<int>& ppid, int kill) {
        unordered_map<int, vector<int>> tree;
        for (size_t i = 0; i < pid.size(); ++i) {
            tree[ppid[i]].push_back(pid[i]);
        }
        vector<int> result;
        queue<int> q;
        q.push(kill);
        while (!q.empty()) {
            int curr = q.front(); q.pop();
            result.push_back(curr);
            for (int child : tree[curr]) {
                q.push(child);
            }
        }
        return result;
    }
};
      

import java.util.*;

public class Solution {
    public List<Integer> killProcess(List<Integer> pid, List<Integer> ppid, int kill) {
        Map<Integer, List<Integer>> tree = new HashMap<>();
        for (int i = 0; i < pid.size(); i++) {
            tree.computeIfAbsent(ppid.get(i), k -> new ArrayList<>()).add(pid.get(i));
        }
        List<Integer> result = new ArrayList<>();
        Queue<Integer> queue = new LinkedList<>();
        queue.add(kill);
        while (!queue.isEmpty()) {
            int curr = queue.poll();
            result.add(curr);
            List<Integer> children = tree.get(curr);
            if (children != null) {
                queue.addAll(children);
            }
        }
        return result;
    }
}
      

/**
 * @param {number[]} pid
 * @param {number[]} ppid
 * @param {number} kill
 * @return {number[]}
 */
var killProcess = function(pid, ppid, kill) {
    const tree = {};
    for (let i = 0; i < pid.length; i++) {
        if (!tree[ppid[i]]) tree[ppid[i]] = [];
        tree[ppid[i]].push(pid[i]);
    }
    const result = [];
    const queue = [kill];
    while (queue.length > 0) {
        const curr = queue.shift();
        result.push(curr);
        if (tree[curr]) {
            queue.push(...tree[curr]);
        }
    }
    return result;
};