Problem
A computer process has a process Id (PID) and a parent process Id (PPID). Only the root process has PPID 0. We use 2 arrays to match the PID to PPID:
PID {6, 2, 8, 5, 3, 7, 1, 9, 4, 10}
PPID {9, 7, 4, 7, 10, 0, 2, 0, 9, 9}
Given a PID, find all process rooted at this process.
For example, given PID 7, the output should be 7, 5, 2, 1
7
/ \
5 2
/
1
Solution
We can build an adjacency set from the PID and PPID arrays, then start at the given node PID, do a dfs or bfs traversal in order to find all the PIDs rooted at that node.
Build the adjacency list costs O(N), bfs or dfs cost O(V + E) is also O(N). We need extra space O(V+E) ~ O(N) to store the adjacency list and marked set.
import java.util.*;
class ChildrenProcess {
public Map<Integer, Set<Integer>> buildDigraph(int[] pids, int[] ppids) {
Map<Integer, Set<Integer>> adjs = new HashMap<>();
for(int i = 0; i < pids.length; i++) {
int parent = ppids[i]; //7
int child = pids[i]; //5
Set<Integer> adj = adjs.get(parent);
if(adj == null) {
adj = new HashSet<>();
adj.add(child); //{6}
adjs.put(parent, adj); //{9, {6}}, {7, {2, 5}},...
} else {
adj.add(child);
}
}
return adjs;
}
public Set<Integer> getChildren(int[] pids, int[] ppids, int root) {
return bfs(buildDigraph(pids, ppids), root);
}
public static void main(String...args) {
ChildrenProcess cp = new ChildrenProcess();
int[] pids = new int[] {6, 2, 8, 5, 3, 7, 1, 9, 4, 10};
int[] ppids = new int[] {9, 7, 4, 7, 10, 0, 2, 0, 9, 9};
Set<Integer> childrens = cp.bfs(cp.buildDigraph(pids, ppids), 7);
childrens.stream().forEach(System.out::println);
}
//7
private Set<Integer> bfs(Map<Integer, Set<Integer>> adjs, int s) {
Set<Integer> marked = new HashSet<>();
Queue<Integer> queue = new LinkedList<>();
marked.add(s);
queue.add(s);
while(!queue.isEmpty()) {
Integer v = queue.poll();
if(adjs.get(v) == null)
continue;
for(int w : adjs.get(v)) {
if(!marked.contains(w)) {
marked.add(w);
queue.add(w);
}
}
}
return marked;
}
}
class ChildrenProcess {
public Map<Integer, Set<Integer>> buildDigraph(int[] pids, int[] ppids) {
Map<Integer, Set<Integer>> adjs = new HashMap<>();
for(int i = 0; i < pids.length; i++) {
int parent = ppids[i]; //7
int child = pids[i]; //5
Set<Integer> adj = adjs.get(parent);
if(adj == null) {
adj = new HashSet<>();
adj.add(child); //{6}
adjs.put(parent, adj); //{9, {6}}, {7, {2, 5}},...
} else {
adj.add(child);
}
}
return adjs;
}
public Set<Integer> getChildren(int[] pids, int[] ppids, int root) {
return bfs(buildDigraph(pids, ppids), root);
}
public static void main(String...args) {
ChildrenProcess cp = new ChildrenProcess();
int[] pids = new int[] {6, 2, 8, 5, 3, 7, 1, 9, 4, 10};
int[] ppids = new int[] {9, 7, 4, 7, 10, 0, 2, 0, 9, 9};
Set<Integer> childrens = cp.bfs(cp.buildDigraph(pids, ppids), 7);
childrens.stream().forEach(System.out::println);
}
//7
private Set<Integer> bfs(Map<Integer, Set<Integer>> adjs, int s) {
Set<Integer> marked = new HashSet<>();
Queue<Integer> queue = new LinkedList<>();
marked.add(s);
queue.add(s);
while(!queue.isEmpty()) {
Integer v = queue.poll();
if(adjs.get(v) == null)
continue;
for(int w : adjs.get(v)) {
if(!marked.contains(w)) {
marked.add(w);
queue.add(w);
}
}
}
return marked;
}
}
Time cost O(N) and space cost O(N).
