Kill Process

medium bfs graph

Problem

pid[i]'s parent is ppid[i]. Given the pid to kill, return every pid that is killed (the pid and all descendants).

Inputpid=[1,3,10,5] ppid=[3,0,5,3] kill=5

Output[5,10]

5's children = [10]; 10 has no children.

input

def kill_process(pid, ppid, kill):
    from collections import defaultdict, deque
    g = defaultdict(list)
    for p, pp in zip(pid, ppid): g[pp].append(p)
    out, q = [], deque([kill])
    while q:
        x = q.popleft(); out.append(x); q.extend(g[x])
    return out

function killProcess(pid, ppid, kill) {
  const g = new Map();
  for (let i = 0; i < pid.length; i++) (g.get(ppid[i]) ?? g.set(ppid[i], []).get(ppid[i])).push(pid[i]);
  const out = [], q = [kill];
  while (q.length) { const x = q.shift(); out.push(x); (g.get(x) || []).forEach(c => q.push(c)); }
  return out;
}

List killProcess(List pid, List ppid, int kill) {
    Map> g = new HashMap<>();
    for (int i = 0; i < pid.size(); i++) g.computeIfAbsent(ppid.get(i), k -> new ArrayList<>()).add(pid.get(i));
    List out = new ArrayList<>();
    Deque q = new ArrayDeque<>(); q.add(kill);
    while (!q.isEmpty()) {
        int x = q.poll(); out.add(x);
        if (g.containsKey(x)) q.addAll(g.get(x));
    }
    return out;
}

vector killProcess(vector& pid, vector& ppid, int kill) {
    unordered_map> g;
    for (int i = 0; i < (int)pid.size(); i++) g[ppid[i]].push_back(pid[i]);
    vector out; queue q; q.push(kill);
    while (!q.empty()) {
        int x = q.front(); q.pop(); out.push_back(x);
        for (int c : g[x]) q.push(c);
    }
    return out;
}

Explanation

Killing a process kills it and all of its descendants — its children, their children, and so on. So this is really "collect an entire subtree" in a process forest, which a simple BFS handles cleanly.

First we turn the flat pid/ppid lists into a parent → children map g. We pair each process with its parent and append the child under that parent's entry, so g[x] gives every direct child of x.

Then we BFS starting from the kill pid. We pop a process, add it to the output list, and push all of its children onto the queue. Repeating this collects the killed process plus everything beneath it.

Example: pid=[1,3,10,5], ppid=[3,0,5,3], kill=5. The map says 5's child is 10, and 10 has none. BFS visits 5 then 10, giving [5, 10].

Each process is enqueued and dequeued exactly once, so building the map and running the BFS together take time linear in the number of processes.

Time: O(n) Space: O(n)