We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Kill Process

Number: 582

Difficulty: Medium

Paid? Yes

Companies: Bloomberg, Oracle, Amazon, Goldman Sachs

Problem Description

Given n processes with unique process IDs, construct a tree from two arrays: one for process IDs (pid) and one for parent process IDs (ppid), where a parent process ID of 0 indicates the root. When a specific process is killed, all its descendant processes are also killed. The task is to return a list of all the process IDs that will be terminated when a given process is killed.

Key Insights

  • Build a mapping (dictionary/hash table) from a parent process ID to its list of child process IDs.
  • Use Depth-First Search (DFS) or Breadth-First Search (BFS) starting from the kill process to traverse the tree and collect all descendant processes.
  • The problem requires handling a tree structure that may have multiple children per node.

Space and Time Complexity

Time Complexity: O(n), where n is the number of processes (both building the mapping and the tree traversal take linear time).
Space Complexity: O(n), for storing the mapping and the traversal queue/stack.

Solution

We first construct a mapping from each process's parent ID to its list of child IDs. This allows us to quickly access all children of any process. Once the mapping is built, we perform a tree traversal (either BFS or DFS) starting from the process to kill. During the traversal, we record every process encountered. This collected list represents all processes that will be terminated. The data structures used are a dictionary (for the mapping) and either a stack (for DFS) or a queue (for BFS), making the solution efficient and straightforward.

Code Solutions

# Python solution using BFS

from collections import deque

def killProcess(pid, ppid, kill):
    # Build a mapping from parent process id to list of child process ids
    tree = {}
    for child, parent in zip(pid, ppid):
        if parent not in tree:
            tree[parent] = []
        tree[parent].append(child)
    
    # Use a deque for BFS traversal
    result = []
    queue = deque([kill])
    
    while queue:
        current = queue.popleft()  # Get process from the left of the queue
        result.append(current)      # Add the current process to the result
        if current in tree:
            # Enqueue all children of the current process
            for child in tree[current]:
                queue.append(child)
    
    return result

# Example usage:
# pid = [1, 3, 10, 5]
# ppid = [3, 0, 5, 3]
# kill = 5
# Expected output: [5, 10]
← Back to All Questions