582. Kill Process
Model: qwen3.5:9b
Topics: Tree,Queue
FAANG asked: 0
Acceptance rate: 63.9%
Problem Breakdown
We are given a tree structure of processes where each node represents a process ID (pid) and its parent’s ID (ppid). The input consists of two arrays: pid containing the current process IDs and ppid containing their respective parents. We need to identify all descendants (including children, grandchildren, etc.) that will be terminated if we kill a specific target process given by kill.
Key Inputs:
- Two integer lists
pidandppidof length . - An integer
killrepresenting the root node ID for our traversal.
Outputs:
- A list of integers containing all killed processes (the subtree rooted at
kill). Order is irrelevant.
Constraints & Edge Cases:
- Scale: up to 50,000. This rules out any nested loops or repeated linear scans (). We need an efficient graph traversal approach.
- Structure: It’s a tree (single parent per node except the root where
ppidis 0). No cycles exist. - IDs: Process IDs are not necessarily contiguous integers, so we cannot use array indexing for direct lookup; hash maps/dictionaries are required.
Intuition
If I were to solve this naively without preprocessing, finding all children of a process would require iterating through the entire pid list every time to find nodes whose parent matches the current node. If the tree is deep or wide, doing this repeatedly results in complexity, which will Time Out (TLE) given the constraints ().
The core insight here is that we are dealing with a tree traversal problem. To traverse efficiently from one node to its descendants, I need fast access to “who are my children?”. Since ppid gives us parent-to-child relationships implicitly (by saying process has parent , it implies is a child of ), we should invert this relationship upfront.
I will build an adjacency list where the key is the Parent ID and the value is a list of Child IDs. Once I have this map, finding all descendants becomes a simple Breadth-First Search (BFS) or Depth-First Search (DFS). Since Python’s recursion limit might be hit with deep trees (), an iterative stack-based DFS is safer and just as efficient.
Approach
- Build the Graph: Iterate through
pidandppid. For each pair(child, parent), addchildto a list associated withparentin a hash map (dictionary). This takes time. Note: We ignore entries whereparent == 0because we only care about traversing from the specifickillnode downwards; however, storing them doesn’t hurt logic-wise as long as we don’t try to traverse from 0 unless it’s our target (which won’t happen based on constraints). - Traverse: Initialize a result list and a stack/queue with the starting process ID (
kill). - Iterate: While the traversal structure is not empty:
- Pop the current node from the stack.
- Add it to our results (it’s being killed).
- Look up its children in our adjacency map and push them onto the stack/queue if they exist.
- Return: Return the collected list of IDs.
Complexity Analysis
- Time Complexity: . We iterate through
pidonce to build the graph ( operations). Then we traverse each node exactly once during BFS/DFS. Total time is linear with respect to input size. - Space Complexity: . The adjacency map stores every edge in the tree, which requires space proportional to . Additionally, the stack and result list store up to elements in worst-case scenarios (e.g., a line graph).
Solution
from collections import defaultdict
from typing import List
def killProcess(pid: List[int], ppid: List[int], kill: int) -> List[int]:
# Build adjacency map: Parent ID -> [List of Child IDs]
children_map = defaultdict(list)
for child, parent in zip(pid, ppid):
if parent != 0:
children_map[parent].append(child)
killed_processes = []
stack = [kill]
while stack:
current_pid = stack.pop()
killed_processes.append(current_pid)
# If this process has children, add them to the traversal queue/stack
if current_pid in children_map:
for child_id in children_map[current_pid]:
stack.append(child_id)
return killed_processes
Edge Cases Handled
- Single Process: If
pidhas length 1 and it matcheskill, the loop runs once, returns[kill]. Correctly handled by initialization of stack withkill. - Kill Root Node (Global): The root is defined as having no parent (
ppid=0). Our map logic ignores entries whereparent == 0to save space. If we kill the node that hasppid=0, it will be added to results, and since its children are stored under their respective keys in the map (populated when processing those specific child nodes), traversal continues correctly from there. - Deep Tree: Using an iterative stack avoids Python’s default recursion limit (1000 frames) which would crash on a skewed tree of depth > 1000 with recursive DFS.