Kill Process

Medium

Amazon

1 view

Topics:

ArraysGraphsTrees

You are given two integer arrays pid and ppid, where pid[i] is the process ID of the i-th process and ppid[i] is the parent process ID of the i-th process. Each process has only one parent process but may have multiple children processes. Only one process has ppid[i] = 0, which means this is the root process.

Now, given an integer kill representing the process ID of a process to be killed, return a list of all process IDs that will be killed. You should also kill all of its child processes.

You should return the answer in any order.

For example:

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

In this case, process 5 and process 10 should be killed. So the answer should be [5, 10].

Here is another example:

pid = [1, 2, 3] ppid = [0, 1, 2] kill = 1

In this case, process 1, 2, and 3 should be killed. So the answer should be [1, 2, 3].

Can you provide an efficient algorithm for this problem, considering factors like time and space complexity?

Kill Process

Medium

Amazon

1 view

Topics:

ArraysGraphsTrees

Now, given an integer kill representing the process ID of a process to be killed, return a list of all process IDs that will be killed. You should also kill all of its child processes.

You should return the answer in any order.

For example:

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

In this case, process 5 and process 10 should be killed. So the answer should be [5, 10].

Here is another example:

pid = [1, 2, 3] ppid = [0, 1, 2] kill = 1

In this case, process 1, 2, and 3 should be killed. So the answer should be [1, 2, 3].

Can you provide an efficient algorithm for this problem, considering factors like time and space complexity?

Solution

Naive Solution

The naive approach would involve iterating through the pid list for each process to be killed, checking if its parent process ID (ppid) matches any of the killed processes. If it does, we add the process to a list of processes to kill, and repeat. This continues until no more processes can be killed. This approach is inefficient because it involves multiple iterations through the process list.

Optimal Solution

The optimal solution uses a graph representation of the process relationships. We construct a map where the key is the parent process ID and the value is a list of child process IDs. We then use a breadth-first search (BFS) to traverse the graph, starting from the initial kill process. During the BFS, we add each visited process to the list of killed processes.

Edge Cases

If the kill process ID is not in the pid list, we can return an empty list or handle it based on the specific requirements (e.g., log an error, throw an exception). The LeetCode problem assumes kill will be a valid process ID, but handling the case is good practice.
If the pid and ppid lists are empty, return an empty list.
If a process has no parent (its ppid is 0) this should be handled gracefully, typically by not including it in the children mapping.

Code

from collections import defaultdict, deque

def killProcess(pid: list[int], ppid: list[int], kill: int) -> list[int]:
    if not pid:
        return []

    children = defaultdict(list)
    for i in range(len(ppid)):
        children[ppid[i]].append(pid[i])

    killed = []
    queue = deque([kill])

    while queue:
        curr_pid = queue.popleft()
        killed.append(curr_pid)
        for child in children[curr_pid]:
            queue.append(child)

    return killed

Big O Analysis

Time Complexity: O(N), where N is the number of processes. This is because we iterate through the pid and ppid lists once to build the graph, and then we perform a BFS that visits each process at most once.
Space Complexity: O(N), where N is the number of processes. This is because we store the graph in a hash map, which can store up to N entries. The queue in the BFS can also hold up to N process IDs in the worst case (e.g. if all processes are children of the kill process).

Solution

Naive Solution

Optimal Solution

Edge Cases

If the kill process ID is not in the pid list, we can return an empty list or handle it based on the specific requirements (e.g., log an error, throw an exception). The LeetCode problem assumes kill will be a valid process ID, but handling the case is good practice.
If the pid and ppid lists are empty, return an empty list.
If a process has no parent (its ppid is 0) this should be handled gracefully, typically by not including it in the children mapping.

Code

from collections import defaultdict, deque

def killProcess(pid: list[int], ppid: list[int], kill: int) -> list[int]:
    if not pid:
        return []

    children = defaultdict(list)
    for i in range(len(ppid)):
        children[ppid[i]].append(pid[i])

    killed = []
    queue = deque([kill])

    while queue:
        curr_pid = queue.popleft()
        killed.append(curr_pid)
        for child in children[curr_pid]:
            queue.append(child)

    return killed

Big O Analysis

Time Complexity: O(N), where N is the number of processes. This is because we iterate through the pid and ppid lists once to build the graph, and then we perform a BFS that visits each process at most once.
Space Complexity: O(N), where N is the number of processes. This is because we store the graph in a hash map, which can store up to N entries. The queue in the BFS can also hold up to N process IDs in the worst case (e.g. if all processes are children of the kill process).