Kill Process LeetCode Solution

Difficulty Level Medium
Frequently asked in Amazon Bloomberg Google Microsoft SalesforceViews 2415

Problem Statement

Kill Process LeetCode Solution – 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.

Kill Process LeetCode Solution

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.

Explanation

we can use a hashmap that stores a particular process value and the list of its direct children.
And then treat it as a tree traversal problem. (BFS/DFS)

or

Construct an adjacency list that maintains the child process linked to that process. Run BFS by starting with the process to be killed. Store all the processes that are killed

Code

C++ Code for Kill Process

class Solution {
public:
    vector<int> killProcess(vector<int>& pid, vector<int>& ppid, int kill) {
        vector<int> killed;
        map<int, set<int>> children;
        for (int i = 0; i < pid.size(); i++) {
            children[ppid[i]].insert(pid[i]);
        }
        killAll(kill, children, killed);
        return killed;
    }

private:
    void killAll(int pid, map<int, set<int>>& children, vector<int>& killed) {
        killed.push_back(pid);
        for (int child : children[pid]) {
            killAll(child, children, killed);
        }
    }
};

Java Code for Kill Process

public class Solution {
    public List<Integer> killProcess(List<Integer> pid, List<Integer> ppid, int kill) {
        if (kill == 0) return pid;
        
        int n = pid.size();
        Map<Integer, Set<Integer>> tree = new HashMap<>();
        for (int i = 0; i < n; i++) {
            tree.put(pid.get(i), new HashSet<Integer>());
        }
        for (int i = 0; i < n; i++) {
            if (tree.containsKey(ppid.get(i))) {
                Set<Integer> children = tree.get(ppid.get(i));
                children.add(pid.get(i));
                tree.put(ppid.get(i), children);
            }
        }
        
        List<Integer> result = new ArrayList<>();
        traverse(tree, result, kill);
        
        return result;
    }
    
    private void traverse(Map<Integer, Set<Integer>> tree, List<Integer> result, int pid) {
        result.add(pid);
        
        Set<Integer> children = tree.get(pid);
        for (Integer child : children) {
            traverse(tree, result, child);
        }
    }
}

Python Code for Kill Process

class Solution(object):
    def killProcess(self, pid, ppid, kill):
        """
        :type pid: List[int]
        :type ppid: List[int]
        :type kill: int
        :rtype: List[int]
        """
        myTree = dict()
        for i, parent in enumerate(ppid):
            myTree[parent] =  myTree.get(parent,[])
            myTree[parent].append(pid[i])
        
        res = []
        stack = [kill]
        while stack:
            cur = stack.pop()
            res.append(cur)
            stack.extend(myTree.get(cur,[]))
            
        return res

Complexity Analysis for Kill Process LeetCode Solution

Time Complexity

O(n+e) since we are doing a bfs traversal.

Space Complexity

O(n) since we store the nodes in a stack/ array.

Reference: https://en.wikipedia.org/wiki/Tree_traversal

Translate »