Kill Process - Leetcode Solution

Problem statement:

You have N processes to execute, numbered from 0 to N-1. The ith process has a PID = pid[i] and its parent process is pid[i]=ppid[i].

Each process only has one parent process. But there can be multiple children processes for a parent process.

Your task is to kill a given process ID and all its child processes. The given PID will always be valid and you must not kill the root process (PID = 0).

Return a list of PIDs of all the processes that were killed. You may return the answer in any order.

Example:

Input: pid = [1, 3, 10, 5], ppid = [3, 0, 5, 3], kill = 5
Output: [5, 10]
Explanation: Kill process 5 and its child processes 10.

Solution:

The problem requires us to find all the child processes of a given process and then kill them all including the given process itself. We can approach this problem using Depth First Search (DFS).

We can create a dictionary that stores the parent-child relationship between processes. Each process number will be a key in the dictionary and its value will be a list of its children processes.

Using this dictionary and DFS, we can find all the child processes of a given process recursively. We start from the given process and add all its children to the result list. Then we recursively call the DFS function for each child process to find its children and add them to the result list.

Finally, we kill all the processes in the result list.

Here is the Python code implementation for the solution:

class Solution:
    def killProcess(self, pid: List[int], ppid: List[int], kill: int) -> List[int]:
        
        # Create a dictionary to store parent-child relationships
        graph = {}
        for i in range(len(pid)):
            parent = ppid[i]
            child = pid[i]
            if parent in graph:
                graph[parent].append(child)
            else:
                graph[parent] = [child]
        
        # DFS to find all child processes of the given process
        def dfs(graph, pid, result):
            if pid in graph:
                for child in graph[pid]:
                    result.append(child)
                    dfs(graph, child, result)
        
        # Find all child processes and add them to the result list
        result = [kill]
        dfs(graph, kill, result)
        
        # Kill all the processes in the result list
        for process in result:
            os.kill(process, signal.SIGTERM)
        
        return result

Time Complexity: O(N), where N is the number of processes. Space Complexity: O(N), where N is the number of processes.

1