|
| 1 | +# Time: O(n) |
| 2 | +# Space: O(n) |
| 3 | + |
| 4 | +# Given n processes, each process has a unique PID (process id) |
| 5 | +# and its PPID (parent process id). |
| 6 | +# |
| 7 | +# Each process only has one parent process, but may have one or more children processes. |
| 8 | +# This is just like a tree structure. Only one process has PPID that is 0, |
| 9 | +# which means this process has no parent process. All the PIDs will be distinct positive integers. |
| 10 | +# |
| 11 | +# We use two list of integers to represent a list of processes, |
| 12 | +# where the first list contains PID for each process |
| 13 | +# and the second list contains the corresponding PPID. |
| 14 | +# |
| 15 | +# Now given the two lists, and a PID representing a process you want to kill, |
| 16 | +# return a list of PIDs of processes that will be killed in the end. |
| 17 | +# You should assume that when a process is killed, |
| 18 | +# all its children processes will be killed. |
| 19 | +# No order is required for the final answer. |
| 20 | +# |
| 21 | +# Example 1: |
| 22 | +# Input: |
| 23 | +# pid = [1, 3, 10, 5] |
| 24 | +# ppid = [3, 0, 5, 3] |
| 25 | +# kill = 5 |
| 26 | +# Output: [5,10] |
| 27 | +# Explanation: |
| 28 | +# 3 |
| 29 | +# / \ |
| 30 | +# 1 5 |
| 31 | +# / |
| 32 | +# 10 |
| 33 | +# Kill 5 will also kill 10. |
| 34 | +# Note: |
| 35 | +# The given kill id is guaranteed to be one of the given PIDs. |
| 36 | +# n >= 1. |
| 37 | + |
| 38 | +# DFS solution. |
| 39 | +class Solution(object): |
| 40 | + def killProcess(self, pid, ppid, kill): |
| 41 | + """ |
| 42 | + :type pid: List[int] |
| 43 | + :type ppid: List[int] |
| 44 | + :type kill: int |
| 45 | + :rtype: List[int] |
| 46 | + """ |
| 47 | + def killAll(pid, children, killed): |
| 48 | + killed.append(pid) |
| 49 | + for child in children[pid]: |
| 50 | + killAll(child, children, killed) |
| 51 | + |
| 52 | + result = [] |
| 53 | + children = collections.defaultdict(set) |
| 54 | + for i in xrange(len(pid)): |
| 55 | + children[ppid[i]].add(pid[i]) |
| 56 | + killAll(kill, children, result) |
| 57 | + return result |
| 58 | + |
| 59 | + |
| 60 | +# Time: O(n) |
| 61 | +# Space: O(n) |
| 62 | +# BFS solution. |
| 63 | +class Solution2(object): |
| 64 | + def killProcess(self, pid, ppid, kill): |
| 65 | + """ |
| 66 | + :type pid: List[int] |
| 67 | + :type ppid: List[int] |
| 68 | + :type kill: int |
| 69 | + :rtype: List[int] |
| 70 | + """ |
| 71 | + def killAll(pid, children, killed): |
| 72 | + killed.append(pid) |
| 73 | + for child in children[pid]: |
| 74 | + killAll(child, children, killed) |
| 75 | + |
| 76 | + result = [] |
| 77 | + children = collections.defaultdict(set) |
| 78 | + for i in xrange(len(pid)): |
| 79 | + children[ppid[i]].add(pid[i]) |
| 80 | + q = collections.deque() |
| 81 | + q.append(kill) |
| 82 | + while q: |
| 83 | + p = q.popleft() |
| 84 | + result.append(p); |
| 85 | + for child in children[p]: |
| 86 | + q.append(child) |
| 87 | + return result |
0 commit comments