Kill Process

Problem Statement

In this scenario, we are operating within a system that structures n processes in a tree-like hierarchy. Each process is uniquely identified by an ID. The relationships between these processes are defined by two integer arrays, pid and ppid. The array pid contains the IDs of each individual process, whereas ppid holds the parent IDs corresponding to each process in pid. It's important to note that each process has precisely one parent, except for the root process, which is identified by a ppid entry of 0 indicating it does not have a parent.

If a process must be halted or killed, its termination implies that all its child processes (if any) are also terminated. Given a process ID kill, the task is to determine all the processes that would be terminated as a direct or indirect result of killing the specified process. This includes the process itself and any of its descendants in the hierarchy.

Examples

Example 1

Input:

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

Output:

[5,10]

Explanation:

 The processes colored in red are the processes that should be killed.

Example 2

Input:

pid = [1], ppid = [0], kill = 1

Output:

[1]

Constraints

• n == pid.length
• n == ppid.length
• 1 <= n <= 5 * 104
• 1 <= pid[i] <= 5 * 104
• 0 <= ppid[i] <= 5 * 104
• Only one process has no parent.
• All the values of pid are unique.
• kill is guaranteed to be in pid.

Approach and Intuition

To effectively determine all processes that will be terminated, we can approach the task with the following steps:

1. Construct a representation of the process hierarchy. This can be in the form of an adjacency list where each process ID points to a list of child process IDs. By iterating through the given pid and ppid arrays, we can populate this adjacency list.

2. Once the tree structure is formed, the next task is to perform a traversal from the node/process corresponding to the kill ID. A depth-first search (DFS) or breadth-first search (BFS) can be employed here. Since we need to collect all processes that descend from the killed process, both methods are suitable as they explore all reachable nodes from the starting node.

3. Initiate the traversal from the process to be killed, and collect all IDs encountered into a result list.

Let's illustrate the method with the provided examples:

• Example 1:

  • Process IDs (pid) are [1, 3, 10, 5]
  • Corresponding parent IDs (ppid) are [3, 0, 5, 3]
  • We need to kill process 5. From the ppid array, we see that process 5 has child 10. Hence, killing 5 should also kill 10.
  • Therefore, the output should be [5, 10].

• Example 2:

  • Here, the only process 1 is also the root (no parents). Therefore, killing 1 results in just that process being terminated.
  • Thus, the output is [1].

By following these steps, we ensure that all necessary processes are accounted for when a particular process is terminated. This method covers cases of varied complexities, from a single process to a large hierarchy of interconnected processes.

Solutions

public class Solution {

    public List<Integer> terminateProcesses(List<Integer> pidList, List<Integer> ppidList, int target) {
        HashMap<Integer, List<Integer>> parentToChildren = new HashMap<>();
        for (int index = 0; index < ppidList.size(); index++) {
            if (ppidList.get(index) > 0) {
                List<Integer> children = parentToChildren.getOrDefault(ppidList.get(index), new ArrayList<Integer>());
                children.add(pidList.get(index));
                parentToChildren.put(ppidList.get(index), children);
            }
        }
        Queue<Integer> processQueue = new LinkedList<>();
        List<Integer> terminated = new ArrayList<>();
        processQueue.add(target);
        while (!processQueue.isEmpty()) {
            int current = processQueue.remove();
            terminated.add(current);
            if (parentToChildren.containsKey(current))
                for (int childId : parentToChildren.get(current))
                    processQueue.add(childId);
        }
        return terminated;
    }
}