05 August 2008
You have n processes forming a rooted tree structure. You are given two integer arrays pid and ppid, where pid[i] is the ID of the ith process and ppid[i] is the ID of the ith process’s parent process.
Each process has only one parent process but may have multiple children processes. Only one process has ppid[i] = 0, which means this process has no parent process (the root of the tree).
When a process is killed, all of its children processes will also be killed.
Given an integer kill representing the ID of a process you want to kill, return a list of the IDs of the processes that will be killed. You may return the answer in any order.
Example 1:
Input: pid = [1,3,10,5], ppid = [3,0,5,3], kill = 5 Output: [5,10] Explanation: The processes colored in red are the processes that should be killed. Example 2:
Input: pid = [1], ppid = [0], kill = 1 Output: [1]
Constraints:
1
2
3
4
5
6
7
8
n == pid.length
n == ppid.length
1 <= n <= 5 * 104
1 <= pid[i] <= 5 * 104
0 <= ppid[i] <= 5 * 104
Only one process has no parent.
All the values of pid are unique.
kill is guaranteed to be in pid.
DFS - O(n)
Step one: Build the Graph using HashMap data structure
Step two: DFS traverse starting from the kill node
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
public List<Integer> killProcess(List<Integer> pid, List<Integer> ppid, int kill) {
Map<Integer, List<Integer>> graph = buildGraph(pid, ppid);
List<Integer> res = new ArrayList<>();
dfs(graph, kill, res);
return res;
}
private void dfs(Map<Integer, List<Integer>> graph, int cur, List<Integer> res) {
res.add(cur);
if(graph.containsKey(cur)){
for(Integer next : graph.get(cur)) {
dfs(graph, next, res);
}
}
}
private Map<Integer, List<Integer>> buildGraph(List<Integer> pid, List<Integer> ppid) {
Map<Integer, List<Integer>> graph = new HashMap<>();
for(int i = 0; i < pid.size(); i++) {
graph.putIfAbsent(ppid.get(i), new LinkedList<Integer>());
graph.get(ppid.get(i)).add(pid.get(i));
}
return graph;
}
}
BFS - O(n)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
/**
* Base case: If the root process is killed, all the processes will be killed
* Build an adjacency list from the given lists.
* Starting with kill, do a BFS for all its neighbors and iterate till you run
* out of neighbors.
*
* @param pid list of processIds
* @param ppid list of parentProcessIds of processIds, matching the order
* @param kill id of process to be killed
* @return list of ids of the processes that will be killed
*/
public List<Integer> killProcess(List<Integer> pid, List<Integer> ppid, int kill) {
if (kill == 0)
return pid;
var adjList = new HashMap<Integer, Set<Integer>>();
for (var i = 0; i < ppid.size(); i++)
adjList.computeIfAbsent(ppid.get(i), j -> new HashSet<>()).add(pid.get(i));
var kills = new LinkedList<Integer>();
var q = new LinkedList<>(List.of(kill));
while (!q.isEmpty()) {
kills.add(q.poll());
q.addAll(adjList.getOrDefault(kills.peekLast(), Set.of()));
}
return kills;
}