Created
May 19, 2017 23:59
-
-
Save jianminchen/8906ca50779127ad74ae6c04b2f4e48f to your computer and use it in GitHub Desktop.
Study code - https://www.youtube.com/watch?v=fKR1n35Sj8s&t=30s, write down C# code - good idea to follow.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
using System; | |
using System.Collections.Generic; | |
using System.Linq; | |
using System.Text; | |
using System.Threading.Tasks; | |
namespace KillProcess_YuZhou | |
{ | |
class Program | |
{ | |
static void Main(string[] args) | |
{ | |
} | |
/// <summary> | |
/// This solution is to copy the idea from the video shown here: | |
/// https://www.youtube.com/watch?v=fKR1n35Sj8s&t=30s | |
/// </summary> | |
/// <param name="pid"></param> | |
/// <param name="ppid"></param> | |
/// <param name="kill"></param> | |
/// <returns></returns> | |
public static IList<int> KillProcess(IList<int> pid, IList<int> ppid, int kill) | |
{ | |
var dictionary = buildDictionary(pid, ppid); | |
return getAllChildren(dictionary, kill); | |
} | |
/// <summary> | |
/// Find kill id in the pid and its children hashtable, do | |
/// a DFS/ BFS search | |
/// </summary> | |
/// <param name="dictionary"></param> | |
/// <param name="kill"></param> | |
/// <returns></returns> | |
private static IList<int> getAllChildren(IDictionary<int, HashSet<int>> dictionary, int kill) | |
{ | |
// Find kill id in the pid and its children hashtable, do | |
// a DFS/ BFS search | |
IList<int> result = new List<int>(); | |
var queue = new Queue<int>(); | |
queue.Enqueue(kill); | |
while (queue.Count > 0) | |
{ | |
var parent = queue.Dequeue(); | |
result.Add(parent); | |
if (dictionary.ContainsKey(parent)) | |
{ | |
var children = dictionary[parent]; | |
foreach (var item in children) | |
{ | |
queue.Enqueue(item); | |
} | |
} | |
} | |
return result; | |
} | |
/// <summary> | |
/// Go over each parent id in the array called ppid, add id and its child | |
/// to a hash table. | |
/// Go over the sample case, | |
/// 3 | |
/// / \ | |
/// 1 5 | |
/// / | |
/// 10 | |
/// pid = 3 has two children - 1, 5 | |
/// pid = 1 has no child. pid = 5 has one child 10. | |
/// </summary> | |
/// <param name="pid"></param> | |
/// <param name="ppid"></param> | |
/// <returns></returns> | |
private static IDictionary<int, HashSet<int>> buildDictionary(IList<int> pid, IList<int> ppid) | |
{ | |
var dictionary = new Dictionary<int, HashSet<int>>(); | |
for (int i = 0; i < ppid.Count; i++) | |
{ | |
var current = ppid[i]; | |
var child = pid[i]; | |
bool isInDict = dictionary.ContainsKey(current); | |
if (isInDict) | |
{ | |
dictionary[current].Add(child); | |
} | |
else | |
{ | |
var set = new HashSet<int>(); | |
set.Add(child); | |
dictionary.Add(current, set); | |
} | |
} | |
return dictionary; | |
} | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment