Home
The Process Killing Algorithms using Depth First Search or Breadth First Search (Kill a Process)
Tags:, , , , ,

The Process Killing Algorithms using Depth First Search or Breadth First Search (Kill a Process)

July 4, 2019 No Comments algorithms, BFS, c / c++, DFS, python, recursive

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 list 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:
The given kill id is guaranteed to be one of the given PIDs.
n >= 1.

This is a good coding exercise to practice the BFS (Breadth First Search) or DFS (Depth First Search) algorithm on a tree or graph.

Intuitive Depth First Search via Recursion

We can iterate the parent list and if it is the parent of the target process, we recursively kill its target process.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

class Solution {
public:
    vector<int> killProcess(vector<int>& pid, vector<int>& ppid, int kill) {
        vector<int> res;
        if (kill == 0) return res;
        // kill the 'kill'       
        res.push_back(kill); 
        for (int i = 0; i < pid.size(); ++ i) {
            if (ppid[i] == kill) {
                // if the parent is kill, then we need to kill current
                vector<int> n = killProcess(pid, ppid, pid[i]);
                res.insert(res.end(), begin(n), end(n));
            }
        }
        return res;
    }
};
class Solution {
public:
    vector<int> killProcess(vector<int>& pid, vector<int>& ppid, int kill) {
        vector<int> res;
        if (kill == 0) return res;
        // kill the 'kill'       
        res.push_back(kill); 
        for (int i = 0; i < pid.size(); ++ i) {
            if (ppid[i] == kill) {
                // if the parent is kill, then we need to kill current
                vector<int> n = killProcess(pid, ppid, pid[i]);
                res.insert(res.end(), begin(n), end(n));
            }
        }
        return res;
    }
};

This is very inefficient, as in worst cases, O(N^N) function calls will be made. Caching the intermediate results does not help much as the number of function calls stays the same regardless of the caching.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

class Solution {
public:
    vector<int> killProcess(vector<int>& pid, vector<int>& ppid, int kill) {
        vector<int> res;
        if (kill == 0) return res;
        if (cached.find(kill) != cached.end()) {
            return cached[kill];
        }
        res.push_back(kill);
        for (int i = 0; i < pid.size(); ++ i) {
            if (ppid[i] == kill) {
                vector<int> n = killProcess(pid, ppid, pid[i]);
                res.insert(res.end(), begin(n), end(n));
            }
        }
        cached[kill] = res;
        return res;
    }
private:
    unordered_map<int, vector<int>> cached;
};
class Solution {
public:
    vector<int> killProcess(vector<int>& pid, vector<int>& ppid, int kill) {
        vector<int> res;
        if (kill == 0) return res;
        if (cached.find(kill) != cached.end()) {
            return cached[kill];
        }
        res.push_back(kill);
        for (int i = 0; i < pid.size(); ++ i) {
            if (ppid[i] == kill) {
                vector<int> n = killProcess(pid, ppid, pid[i]);
                res.insert(res.end(), begin(n), end(n));
            }
        }
        cached[kill] = res;
        return res;
    }
private:
    unordered_map<int, vector<int>> cached;
};

At each call, in worst cases, we have to search N items, which is the inherent problem of the above recursion algorithm.

How to Kill a Process Tree using Depth First Search Algorithm?

The inputs can be processed so that it would be easier to apply the BFS or DFS. We first iterate both arrays at the same time to process the data structure so that we know the children nodes given a process ID.

Then, we can easily DFS in time scale of O(N). The space complexity is O(N) as we are using a hash table to store the parent-children mapping and the stack O(N) implied by using recursion.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

class Solution {
public:
    vector<int> killProcess(vector<int>& pid, vector<int>& ppid, int kill) {
        for (int i = 0; i < pid.size(); ++ i) {
            children[ppid[i]].push_back(pid[i]);
        }
        vector<int> r;
        r.push_back(kill);
        killAll(children[kill], r);
        return r;
    }
private:
    unordered_map<int, vector<int>> children;
    void killAll(vector<int> c, vector<int> &r) {        
        for (const auto &x: c) {
            r.push_back(x);
            killAll(children[x], r);
        }
    }
};
class Solution {
public:
    vector<int> killProcess(vector<int>& pid, vector<int>& ppid, int kill) {
        for (int i = 0; i < pid.size(); ++ i) {
            children[ppid[i]].push_back(pid[i]);
        }
        vector<int> r;
        r.push_back(kill);
        killAll(children[kill], r);
        return r;
    }
private:
    unordered_map<int, vector<int>> children;
    void killAll(vector<int> c, vector<int> &r) {        
        for (const auto &x: c) {
            r.push_back(x);
            killAll(children[x], r);
        }
    }
};

The DFS algorithm in Python is implemented as follows using a collections.defaultdict:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

from collections import defaultdict;
 
class Solution:
    def killProcess(self, pid: List[int], ppid: List[int], kill: int) -> List[int]:
        children = defaultdict(list)
        for i in range(len(pid)):
            children[ppid[i]].append(pid[i])
        r = []
        def dfs(kill):
            nonlocal r
            r.append(kill)
            for i in children[kill]:
                dfs(i)
        dfs(kill)
        return r            
from collections import defaultdict;

class Solution:
    def killProcess(self, pid: List[int], ppid: List[int], kill: int) -> List[int]:
        children = defaultdict(list)
        for i in range(len(pid)):
            children[ppid[i]].append(pid[i])
        r = []
        def dfs(kill):
            nonlocal r
            r.append(kill)
            for i in children[kill]:
                dfs(i)
        dfs(kill)
        return r

An alternative DFS implementation in Python:

1
2
3
4
5
6
7
8
9
10
11

class Solution:
    def killProcess(self, pid: List[int], ppid: List[int], kill: int) -> List[int]:
        children = defaultdict(list[int])
        for p, pp in zip(pid, ppid):
            children[pp].append(p)
        def dfs(p, children):
            ans = [p]
            for pp in children[p]:
                ans += dfs(pp, children)
            return ans
        return dfs(kill, children)
class Solution:
    def killProcess(self, pid: List[int], ppid: List[int], kill: int) -> List[int]:
        children = defaultdict(list[int])
        for p, pp in zip(pid, ppid):
            children[pp].append(p)
        def dfs(p, children):
            ans = [p]
            for pp in children[p]:
                ans += dfs(pp, children)
            return ans
        return dfs(kill, children)

How to Kill a Process Tree using Breadth First Search Algorithm?

Once we have a parent-children mapping, we can also BFS iteratively using a queue. The time and space complexity is O(N). 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

class Solution {
public:
    vector<int> killProcess(vector<int>& pid, vector<int>& ppid, int kill) {
        unordered_map<int, vector<int>> children;
        for (int i = 0; i < pid.size(); ++ i) {
            children[ppid[i]].push_back(pid[i]);
        }
        vector<int> r;
        queue<int> Q;
        Q.push(kill);
        while (!Q.empty()) {
            auto p = Q.front();
            r.push_back(p);
            Q.pop();
            for (const auto &n: children[p]) {
                Q.push(n);
            }
        }
        return r;
    }
};
class Solution {
public:
    vector<int> killProcess(vector<int>& pid, vector<int>& ppid, int kill) {
        unordered_map<int, vector<int>> children;
        for (int i = 0; i < pid.size(); ++ i) {
            children[ppid[i]].push_back(pid[i]);
        }
        vector<int> r;
        queue<int> Q;
        Q.push(kill);
        while (!Q.empty()) {
            auto p = Q.front();
            r.push_back(p);
            Q.pop();
            for (const auto &n: children[p]) {
                Q.push(n);
            }
        }
        return r;
    }
};

And here is the Python implementation of the Breadth First Search Algorithm to Kill a Process and its descendants.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

class Solution(object):
    def killProcess(self, pid, ppid, kill):
        d = defaultdict(list)        
        for i in range(len(ppid)):
            d[ppid[i]].append(pid[i])        
        queue = [kill]    
        visited = set()
        while queue:
            newqueue = []
            while queue:
                pop = queue.pop()
                if pop in visited:
                    continue
                visited.add(pop)
                if pop in d:
                    newqueue += d[pop]
            queue = newqueue[:]
        return list(visited)
class Solution(object):
    def killProcess(self, pid, ppid, kill):
        d = defaultdict(list)        
        for i in range(len(ppid)):
            d[ppid[i]].append(pid[i])        
        queue = [kill]    
        visited = set()
        while queue:
            newqueue = []
            while queue:
                pop = queue.pop()
                if pop in visited:
                    continue
                visited.add(pop)
                if pop in d:
                    newqueue += d[pop]
            queue = newqueue[:]
        return list(visited)

We probably don’t need to store the visited nodes as they are unique and there is no cycles (trees are Directed Acyclic Graphs DAG): Teaching Kids Programming – Remove a Node and Subtree using Depth First Search or Breadth First Search Algorithm

–EOF (The Ultimate Computing & Technology Blog) —

GD Star Rating
loading...
1152 words
Last Post: Breadth-First Search Algorithm to Solve Puzzle (Rotting Oranges) in a Grid
Next Post: Facebook Onsite Interview Preparation Part 2: Coding Questions

The Permanent URL is: The Process Killing Algorithms using Depth First Search or Breadth First Search (Kill a Process)

Related posts:

  1. Teaching Kids Programming – Kth Smallest Element in a BST via Iterative Inorder Traversal Algorithm Teaching Kids Programming: Videos on Data Structures and Algorithms Given a binary search tree, write...
  2. Bruteforce or Line Sweep Algorithms to Remove Covered Intervals Given a list of intervals, remove all intervals that are covered by another interval in...
  3. Two Pointer and Sliding Window Algorithm to Find K-Length Substrings With No Repeated Characters Given a string S, return the number of substrings of length K with no repeated...
  4. Fixing Profile Query Command due to API Change in Steem Blockchain Due to an API change in SteemIt see this post, the following code to get...
  5. O(NLogN) to Compute the Median in a Stream using Two Priority Queues You’re given a list of n integers arr. You must compute a list output such...
  6. Three ways of Running a continuous NodeJS Application on Your Server Let’s say, I have an application that is written in NodeJs, that process the latest...
  7. Teaching Kids Programming – Restore the Word from Rules Teaching Kids Programming: Videos on Data Structures and Algorithms Given a list of rules in...
  8. Teaching Kids Programming – Max Profit of Rod Cutting (Unbounded Knapsack) via Bottom Up Dynamic Programming Algorithm Teaching Kids Programming: Videos on Data Structures and Algorithms You are given a list of...

Leave a Reply