Is Kill Process easy or hard?

Kill Process is generally rated Medium difficulty. The main challenge is recognizing that the pid and ppid arrays describe a tree structure and converting them into an adjacency list before performing DFS or BFS.

Kill Process Python/Java solution

Most solutions build a dictionary or HashMap mapping parent IDs to child lists, then run DFS from the kill ID. The traversal collects each visited process into the result list. This implementation works consistently across Python, Java, C++, Go, TypeScript, and Rust.

How to solve Kill Process in O(n)?

First create a hash map mapping each parent process ID to a list of its child processes by iterating through the pid and ppid arrays once. Then run a DFS or BFS starting from the given kill process and collect every reachable node. Each node is processed once, giving O(n) total time.

What is the best approach for Kill Process?

The optimal approach builds a parent-to-children adjacency list and performs a DFS or BFS traversal starting from the process to kill. Each process is visited once, giving O(n) time complexity and O(n) space for the map and traversal structure.

Is Kill Process asked at Google/Amazon/Meta?

Kill Process is a common tree or graph traversal interview question seen in companies like Amazon and other large tech firms. It tests whether you can convert parent-child relationships into an adjacency structure and traverse it efficiently.

What data structure is used in Kill Process?

The main data structure is a hash map that stores a parent process ID mapped to a list of its child processes. After building this structure, a DFS recursion stack or BFS queue is used to traverse the process tree.

What is the time complexity of Kill Process?

The optimal solution runs in O(n) time because each process ID is inserted into a hash map once and visited once during the DFS or BFS traversal. Space complexity is also O(n) due to storing the adjacency list and the recursion stack or queue.

Description Solution Video 10:58

582. Kill Process

Medium70.4% acceptance4 companiesPremium elsewhere, free here

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 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.

Example 1:

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.

Example 2:

Input: pid = [1], ppid = [0], kill = 1
Output: [1]

Constraints:

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

Asked at 4 companies

Bloomberg Oracle Amazon Microsoft

Topics

10:58

Still stuck?Read the written solution, or watch a walkthrough.

Open solution

LanguageLoading editor…

1class Solution:
  def solve(self):
      pass


Starter codePython 3Spaces: 4

Examples

Case 1Case 2

Input

[1,3,10,5]
[3,0,5,3]
5

Input

[1]
[0]
1

Your code is saved on this device.Solution