c# solution - seek advice to shorten time


  • 1

    Still work on the problem solving basics, run-time error on null pointer, need to use DFS/ BFS to get all children, timeout issue to avoid using hashtable.

    Work on coding styles, avoid bugs in writing.

    using System;
    using System.Collections.Generic;
    using System.Linq;
    using System.Text;
    using System.Threading.Tasks;
    
    namespace Leetcode582_KillProcess
    {
        /// <summary>
        /// problem statement: 
        /// https://leetcode.com/problems/kill-process/#/description
        /// </summary>
        class Program
        {
            internal class Node
            {
                public int Id { get; set; }
                public int ParentId { get; set; }
                public HashSet<int> Children { get; set; }
    
                public Node(int id)
                {
                    Id = id; 
                }
    
                public void AddChild(int id)
                {
                    if (Children == null)
                    {
                        Children = new HashSet<int>(); 
                    }
    
                    Children.Add(id); 
                }
            }
    
            static void Main(string[] args)
            {
                RunTestcase(); 
            }
    
            public static void RunTestcase()
            {
                IList<int> pid = new List<int>() { 1, 3, 10, 5 };
                IList<int> ppid = new List<int>() { 3, 0, 5, 3};
    
                var result = KillProcess(pid, ppid, 5); 
            }
    
            public static void RunTestcase2()
            {
                IList<int> pid = new List<int>() { 1, 2, 3 };
                IList<int> ppid = new List<int>() { 0, 1, 2 };
    
                var result = KillProcess(pid, ppid, 1);
            }
    
            public static IList<int> KillProcess(IList<int> pid, IList<int> ppid, int kill)
            {
                IList<int> children = new List<int>();            
    
                // create nodes in the tree one by one
                IList<Node> nodes = new List<Node>(); 
                foreach (var item in pid)
                {
                    var current = new Node(item);
                    nodes.Add(current); 
                }
    
                var lookup = getHashSet(pid); 
    
                // build the tree's children and parent node info, get root node info            
                for (int i = 0; i < ppid.Count; i++)
                {
                    var parentId = ppid[i];
                    var id = nodes[i].Id; 
    
                    nodes[i].ParentId = ppid[i];
    
                    if (parentId == 0)
                    {
                        continue;
                    }
    
                    // add child node to node with id 
                    int index = lookup[parentId];
                    nodes[index].AddChild(id); 
                }
    
                // find kill Id's children
                return getKillChildren(lookup, nodes, kill);            
            }
    
            /// <summary>
            /// Dictionary is important to avoid timeout, Array.IndexOf does not work. 
            /// </summary>
            /// <param name="ids"></param>
            /// <returns></returns>
            private static Dictionary<int, int> getHashSet(IList<int> ids)
            {
                var lookup = new Dictionary<int, int>();
                for (int i = 0; i < ids.Count; i++)
                {
                    lookup.Add(ids[i], i); 
                }
    
                return lookup; 
            }
            /// <summary>
            /// BFS search 
            /// </summary>
            /// <param name="lookup"></param>
            /// <param name="nodes"></param>
            /// <param name="kill"></param>
            /// <returns></returns>
            private static IList<int> getKillChildren(Dictionary<int,int> lookup, IList<Node> nodes, int kill)
            {
                IList<int> children = new List<int>();
    
                int index = lookup[kill];
                int id = nodes[index].Id; 
    
                var queue = new Queue<int>();
                queue.Enqueue(id); 
    
                while (queue.Count > 0 )
                {
                    int visitId = queue.Dequeue();                              
    
                    children.Add(visitId);
    
                    index = lookup[visitId];
                    var visitNode = nodes[index]; 
    
                    var childrenNodes = visitNode.Children;
    
                    if (childrenNodes != null)   // need more attention here!
                    {
                        foreach (var item in childrenNodes)
                        {
                            queue.Enqueue(item);
                        }
                    }
                }
    
                var array = children.ToArray();
                Array.Sort(array); 
    
                return array.ToList(); 
            }      
        }
    }

  • 1

    Below is my solution in C#. 34 lines and easy to understand. Hope it helps.

        public static IList<int> KillProcess(IList<int> pid, IList<int> ppid, int kill)
        {
            if (kill == 0)
                return pid;
    
            Dictionary<int, HashSet<int>> dict = new Dictionary<int, HashSet<int>>();
            // initial the dict
            for (int i = 0; i < pid.Count; i++)
            {
                dict.Add(pid[i], new HashSet<int>());
            }
            // fill the dict with a children set
            for (int i = 0; i < pid.Count; i++)
            {
                int parent = ppid[i];   //current(pid[i])'s parent
                if (dict.ContainsKey(parent)    //if parent exist in dict's keys
                {
                    HashSet<int> children = dict[parent];   //retrive its children's set
                    children.Add(pid[i]);                             //add into set
                    dict[parent] = children;                        //update hash table
                }
            }
    
            List<int> res = new List<int>();
            dfs(dict, res, kill);
            return res;
        }
    
        private static void dfs(Dictionary<int, HashSet<int>> dict, List<int> res, int start)
        {
            res.Add(start);
            var childSet = dict[start];
            foreach (var next in childSet)
            {
                dfs(dict,res,next);
            }
        }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.