The Process Killing Algorithms using Depth First Search or Bread

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

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) —

推荐阅读：
难忘的中秋佳节作文　 2011国庆节作文100字　 关于元旦节的作文200字　 春节作文300字400字500字600字800字　 加权平均数是什么意思？　 四舍五入法怎么用　 多边形的内角和公式　 梯形上底的定义是什么　 用放大镜看角变大了吗　 四位一级和三位分节　
评论列表
添加评论