The Process Killing Algorithms using Depth First Search or Bread

  • 时间：2020-09-24 11:41:27
  • 分类：网络文摘
  • 阅读：109 次

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

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;
    }
};

–EOF (The Ultimate Computing & Technology Blog) —

推荐阅读：
French Blogger Embarks On ‘Zero Waste’ World Tour　 30 Incredibly Useful Tools You Need to Grow Your Blog　 What You Need to Know Before Becoming an Internet Entrepreneur　 Teen Horror Blogger Speaks Out About Killing Her Parents　 SEO for 2017: Post Penguin 4.0 and How to Take a Publisher’s App　 Trick Or Treat: How Businesses Are Cashing In On Halloween　 Man Steals ‘Six Figures’ Worth Of Bitcoins From Dark Web Users　 The Git Pre-Commit Hook to Avoid Pushing Only Unit Tests In Node　 How to Find the Most Common Word in a String with a Banned List?　 How to Construct Minimum Spanning Tree using Kruskal or Breadth 　
评论列表
添加评论