Kill Process — Day 77(Python)

Annamariya Tharayil
Feb 17 · 3 min read
Photo by sebastiaan stam on Unsplash

Today’s question is from Leetcode’s daily coding challenge February edition. It is a medium-tagged question on Leetcode. Let us look into the problem statement.

582. Kill Process

Given n processes, each process has a unique PID (process id) and its PPID (parent process id).

Each process only has one parent process, but may have one or more children processes. This is just like a tree structure. Only one process has PPID that is 0, which means this process has no parent process. All the PIDs will be distinct positive integers.

We use two lists of integers to represent a list of processes, where the first list contains PID for each process and the second list contains the corresponding PPID.

Now given the two lists, and a PID representing a process you want to kill, return a list of PIDs of processes that will be killed in the end. You should assume that when a process is killed, all its children processes will be killed. No order is required for the final answer.

Example 1:

Input: 
pid = [1, 3, 10, 5]
ppid = [3, 0, 5, 3]
kill = 5
Output: [5,10]
Explanation:
3
/ \
1 5
/
10
Kill 5 will also kill 10.

Note:

  1. The given kill id is guaranteed to be one of the given PIDs.
  2. n >= 1.

One way to start solving this problem is to use a data structure that keeps track of children nodes of all the nodes. We can use a dictionary to store the parent-child relation.

Let us see how we can store that relation.

parent_dictionary = collections.defaultdict(list)
for p in range(len(ppid)):
parent_dictionary[ppid[p]].append(pid[p])

Next, we need to identify all the nodes that have to be killed. We start with the input node. We look at who are the children of this node. We then look for children of these children. Keep looking for the children until we reach the leaf nodes. Looks like we need to use BFS or DFS to solve this problem.

We will be solving this problem using BFS.

We need a queue that will keep track of which process needs to be killed. We will take the first node from the queue, look for its children in the dictionary, and add children in the queue. Keep repeating the steps until the queue is empty. Every time we remove the node from the queue add it to the output list.

import collections
class ProcessKiller:
def killProcess(self, pid: List[int], ppid: List[int], kill: int) -> List[int]:
parent_dictionary = collections.defaultdict(list)
output = []
next_process_to_kill = [kill]
for p in range(len(ppid)):
parent_dictionary[ppid[p]].append(pid[p])
while(next_process_to_kill):
kill_proc = next_process_to_kill.pop(0)
output.append(kill_proc)
for process in parent_dictionary[kill_proc]:
next_process_to_kill.append(process)
return output

Complexity analysis.

Time Complexity

We are visiting each node in ppid and pid to create the dictionary. The time to kill process will take O(N) if we have to kill off the root node. Hence the time complexity is O(N).

Space Complexity.

Since we are using a dictionary to store the nodes, the space complexity is O(N), where N is the number of nodes.

We can use DFS to solve this problem too. Since we have solved quite a few problems using DFS, we can directly look into the code snippet.

import collections
class ProcessKiller:
def killProcess(self, pid: List[int], ppid: List[int], kill: int) -> List[int]:
parent_dictionary = collections.defaultdict(list)
output = []
next_process_to_kill = [kill]
for p in range(len(ppid)):
parent_dictionary[ppid[p]].append(pid[p])
def dfs(node):
output.append(node)
for child in parent_dictionary[node]:
dfs(child)
dfs(kill)
return output

Complexity analysis.

Time Complexity

We are visiting each node in ppid and pid to create the dictionary. The time to kill process will take O(N) if we have to kill off the root node. Hence the time complexity is O(N).

Space Complexity.

Since we are using a dictionary to store the nodes, the space complexity is O(N), where N is the number of nodes.

Nerd For Tech

NFT is an Educational Media House. Our mission is to bring the invaluable knowledge and experiences of experts from all over the world to the novice. To stay up to date on other topics, follow us on LinkedIn. https://www.linkedin.com/company/nerdfortech

Annamariya Tharayil

Written by

Software Engineer. Find me @ www.linkedin.com/in/annamariya-jt

Nerd For Tech

NFT is an Educational Media House. Our mission is to bring the invaluable knowledge and experiences of experts from all over the world to the novice. To stay up to date on other topics, follow us on LinkedIn. https://www.linkedin.com/company/nerdfortech

Medium is an open platform where 170 million readers come to find insightful and dynamic thinking. Here, expert and undiscovered voices alike dive into the heart of any topic and bring new ideas to the surface. Learn more

Follow the writers, publications, and topics that matter to you, and you’ll see them on your homepage and in your inbox. Explore

If you have a story to tell, knowledge to share, or a perspective to offer — welcome home. It’s easy and free to post your thinking on any topic. Write on Medium

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store