Kill Process

Hard

0/120

0 upvote

Problem statement

You are given n processes that form a rooted tree structure. Each process is identified by a unique positive integer ID. Every process has exactly one parent, except for the root process.

The process relationships are provided in two arrays:

pid: An array where pid[i] is the ID of the i-th process.

ppid: An array where ppid[i] is the ID of the parent of the i-th process.

The root process is identified by having a parent ID of 0.

A critical rule of this system is that when a process is killed, all of its descendant processes (its children, grandchildren, and so on) are also killed automatically.

Given an integer kill which is the ID of a process to be terminated, your task is to return a list containing the IDs of all processes that will be killed as a result.

Detailed explanation ( Input/output format, Notes, Images )

Input Format:

The first line contains a single integer N, the number of processes.

The second line contains N space-separated integers, representing the pid array.

The third line contains N space-separated integers, representing the ppid array.

The fourth line contains a single integer, kill, the ID of the process to terminate.

Output Format:

Print a single line containing all the killed process IDs, sorted in ascending order and separated by spaces.

Note:

The input arrays pid and ppid may not be in any particular order. The most efficient way to solve this is to first build a more usable tree structure (like an adjacency list) from the given arrays and then traverse the subtree of the process to be killed.

Sample Input 1:

Sample Output 1:

3 4

Explanation for Sample 1:

The process structure is a tree:
  Process 1 is the root (parent is 0).
  Processes 3 and 5 are children of process 1.
  Process 4 is a child of process 3.
When process 3 is killed, its entire subtree is also killed. This includes process 3 itself and its child, process 4.

Expected Time Complexity:

The expected time complexity is O(N).

Constraints:

1 <= N <= 5 * 10^4
All pid values are unique and positive.
ppid[i] is either 0 or a valid pid.
The kill ID is guaranteed to be a valid pid.

Time limit: 1 sec

Approaches (1)

Approach 1

Time Complexity

Space Complexity

(100% EXP penalty)

Kill Process

Console