The Process Killing Algorithms using Depth First Search or Bread

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

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

推荐阅读：
最终得到的一位数是多少？　 怎样才能全部过河？　 最多多少页？最少多少页？　 欧拉公式F+V-E=2　 Ｘ侦探和万能公式　 音乐数3、4、6　 试管中的所有空间被细胞占满　 走马灯数　 求往返的平均速度　 SEO网站做关键词上首页需要多长时间?　
评论列表
添加评论