Skip to content

Instantly share code, notes, and snippets.

@jianminchen
Created May 19, 2017 23:59
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save jianminchen/8906ca50779127ad74ae6c04b2f4e48f to your computer and use it in GitHub Desktop.
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.
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