Kill Process

Medium

Asked by:

16 views

Topics:

ArraysGraphsTrees

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 i^th process and ppid[i] is the ID of the i^th process's parent.

Each process has only one parent but may have zero or more children. The process with pid[i] == 0 is the root process.

You are also given an integer kill representing the ID of a process to kill.

You should kill the given process and all of its children. 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 form the following tree:
      3
    /   \
  1      5
        / 
       10
Kill 5 and also kill its only child 10.

Example 2:

Input: pid = [1], ppid = [0], kill = 1
Output: [1]
Explanation: The root process is killed.

Constraints:

n == pid.length
n == ppid.length
1 <= n <= 5 * 10⁴
0 <= pid[i] <= 5 * 10⁴
0 <= ppid[i] <= 5 * 10⁴
Only one process has ppid[i] == 0.
All the values of pid are unique.
kill is guaranteed to be in pid.

Try coding it in LeetCode

Kill Process

Medium

Asked by:

16 views

Topics:

ArraysGraphsTrees

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 i^th process and ppid[i] is the ID of the i^th process's parent.

Each process has only one parent but may have zero or more children. The process with pid[i] == 0 is the root process.

You are also given an integer kill representing the ID of a process to kill.

You should kill the given process and all of its children. 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 form the following tree:
      3
    /   \
  1      5
        / 
       10
Kill 5 and also kill its only child 10.

Example 2:

Input: pid = [1], ppid = [0], kill = 1
Output: [1]
Explanation: The root process is killed.

Constraints:

n == pid.length
n == ppid.length
1 <= n <= 5 * 10⁴
0 <= pid[i] <= 5 * 10⁴
0 <= ppid[i] <= 5 * 10⁴
Only one process has ppid[i] == 0.
All the values of pid are unique.
kill is guaranteed to be in pid.

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

Can you clarify the data types and ranges for the process IDs and their parent IDs? Are they always positive integers?
Is it guaranteed that the process to kill (the 'kill' ID) will always be present in the process ID list?
Could there be cycles in the parent-child relationships, and if so, how should I handle them?
If a process has multiple children, is the order in which I add their IDs to the result important?
What should I return if the input lists are empty or null?

Brute Force Solution

Approach

Imagine a family tree where each person has a unique ID. We want to eliminate a specific person and all their descendants. The brute force approach involves manually checking each person and their relationships to find everyone who needs to be eliminated.

Here's how the algorithm would work step-by-step:

Start with the person we want to eliminate (the 'kill' target).
Look at the family tree and find all the children of that person.
Add those children to the list of people to be eliminated.
For each of those children, find their children, and add them to the list too.
Keep repeating this process of finding children and adding them to the list, until there are no more new children to add.
The final list contains the original target and everyone who descends from them, and these are the processes to be killed.

Code Implementation

def kill_process_brute_force(process_ids, parent_process_ids, kill_id):
    processes_to_kill = [kill_id]
    processes_to_check = [kill_id]

    # Iterate as long as there are processes to check for children
    while processes_to_check:
        current_process_id = processes_to_check.pop(0)

        # Find children of the current process
        for i in range(len(parent_process_ids)):
            if parent_process_ids[i] == current_process_id:
                child_process_id = process_ids[i]

                # Add children to kill list and check list
                processes_to_kill.append(child_process_id)
                processes_to_check.append(child_process_id)

    # This list contains all processes that need to be killed
    return processes_to_kill

Big(O) Analysis

Time Complexity

O(n) – The algorithm visits each process in the tree at most once to determine if it is a descendant of the kill process. In the worst-case scenario, the kill target is the root of the tree, which means every process will be visited and added to the kill list. The number of processes visited is proportional to the total number of processes, n. Therefore, the time complexity is O(n).

Space Complexity

O(N) – The algorithm uses a queue (implicit in steps 2-5 as the 'list of people to be eliminated') to store the IDs of processes to kill, and in the worst case, all processes might be descendants of the initial kill target. Therefore, the queue could potentially hold all N process IDs where N is the total number of processes in the family tree. Also, each node can be visited once and stored for processing. Consequently, the auxiliary space is proportional to the number of nodes, thus the space complexity is O(N).

Optimal Solution

Approach

The most efficient way to solve this problem is to think about which processes are directly controlled by the process we want to eliminate. We can find these 'child' processes and then continue to find their 'children', and so on, until we have identified all processes that will be terminated as a result of killing the initial process.

Here's how the algorithm would work step-by-step:

First, create a way to easily find which processes are directly managed by each process. Think of it like creating a family tree where you can quickly see all the children of any given parent process.
Next, find all the processes that are directly managed by the process we are trying to kill. These are the first set of processes that will be terminated.
Then, for each of those processes, find *their* children, and add them to the list of processes to terminate.
Keep repeating this process, finding the children of the children, and so on, until you reach processes that have no children themselves. In other words, keep going until you have identified all processes that are indirectly or directly managed by the initial process.
Finally, you will have a complete list of all the processes that will be terminated. This method avoids wasting time checking processes that are completely unrelated to the one being killed.

Code Implementation

def kill_process(pid, parent_process_id, kill_id):
    process_children = {}

    # Build a dictionary to represent the process tree
    for i in range(len(parent_process_id)): 
        parent = parent_process_id[i]
        child = pid[i]
        if parent not in process_children:
            process_children[parent] = []
        process_children[parent].append(child)

    processes_to_kill = []

    # Initiate the kill list with the initial kill_id
    processes_to_kill.append(kill_id)

    def kill_recursive(process_id_to_kill):
        # Kill all the child processes recursively
        if process_id_to_kill in process_children:
            for child_process in process_children[process_id_to_kill]:
                processes_to_kill.append(child_process)
                kill_recursive(child_process)

    kill_recursive(kill_id)

    return processes_to_kill

Big(O) Analysis

Time Complexity

O(n) – Constructing the process tree (parent-child relationships) involves iterating through the pid and ppid arrays once, which takes O(n) time. The kill process function recursively traverses the process tree, visiting each node (process) at most once to identify all processes to be killed. The number of processes to be killed is bounded by n (the total number of processes), therefore the depth-first search takes O(n) time. Hence the overall complexity is O(n).

Space Complexity

O(N) – The primary space complexity arises from creating a hash map (or adjacency list) to represent the parent-child process relationships, where N is the number of processes. This hash map stores each process ID as a key and a list of its child process IDs as the value. In the worst-case scenario, each process has a unique parent, requiring storage for all N processes in the map. Additionally, a queue is used to store the processes to be killed, which in the worst-case, can hold all N processes simultaneously. Therefore, the auxiliary space used is proportional to the number of processes, resulting in O(N) space complexity.

Edge Cases

Case	How to Handle
Null or empty pid and ppid lists	Return an empty list since there are no processes to kill.
pid and ppid lists have different lengths	Throw an IllegalArgumentException or return an error code indicating invalid input.
kill process ID not found in pid list	Return an empty list since there's nothing to kill, or the caller may handle this scenario as an exception.
The kill process ID is the same as the root process ID (0)	Kill all processes since the root process is being terminated.
Duplicate process IDs in pid list	The tree structure is constructed using the first instance of each process ID, and the behavior will be based on that relationship.
A process ID has multiple parents (invalid tree structure)	The algorithm should still work, effectively killing all processes descended from all parents; log an error to indicate corrupted data.
Large input size leading to stack overflow during recursion	Convert the recursive DFS to an iterative DFS using a stack to prevent potential stack overflow errors.
Integer overflow if process IDs are large	Use long instead of int for storing process IDs if the problem statement allows it to avoid integer overflow.

Null or empty pid and ppid lists

How to Handle:

Return an empty list since there are no processes to kill.

pid and ppid lists have different lengths

How to Handle:

Throw an IllegalArgumentException or return an error code indicating invalid input.

kill process ID not found in pid list

How to Handle:

Return an empty list since there's nothing to kill, or the caller may handle this scenario as an exception.

The kill process ID is the same as the root process ID (0)

How to Handle:

Kill all processes since the root process is being terminated.

Duplicate process IDs in pid list

How to Handle:

The tree structure is constructed using the first instance of each process ID, and the behavior will be based on that relationship.

A process ID has multiple parents (invalid tree structure)

How to Handle:

The algorithm should still work, effectively killing all processes descended from all parents; log an error to indicate corrupted data.

Large input size leading to stack overflow during recursion

How to Handle:

Convert the recursive DFS to an iterative DFS using a stack to prevent potential stack overflow errors.

Integer overflow if process IDs are large

How to Handle:

Use long instead of int for storing process IDs if the problem statement allows it to avoid integer overflow.