Problem statement There are a total of \$n\$ courses you have to take, labeled from  \$0\$ to \$n - 1\$.Some courses may have prerequisites, for example to take course \$0\$  you have to first take course \$1\$, which is expressed as a pair:  \$[0,1]\$Given the total number of courses and a list of prerequisite  pairs, return the ordering of courses you should take to finish all courses.There may be multiple correct orders, you just need to return one of  them. If it is impossible to finish all courses, return an empty  array.For example:\$2, [[1,0]]\$There are a total of \$2\$ courses to take. To take course \$1\$ you  should have finished course 0. So the correct course order is  \$[0,1]\$\$4, [[1,0],[2,0],[3,1],[3,2]]\$There are a total of \$4\$ courses to take. To take course \$3\$ you  should have finished both courses \$1\$ and \$2\$. Both courses \$1\$  and \$2\$ should be taken after you finished course \$0\$. So one  correct course order is \$[0,1,2,3]\$. Another correct ordering is  \$[0,2,1,3]\$.My introduction of algorithm:The algorithm is one of topological sorting algorithms. I spent over 5 hours to practice in 2016, and then based on the last practice, I reviewed the practice today less than 2 hour. I put together the C# solution for code review. Highlights of changes:Add two test cases, work on the second test case with 4 possible solutions.For each course, there are dependent courses, assuming that course Id is from 0 to numCourses - 1. I declare a local variable dependents this practice.var dependents = new Stack<int>[numCourses];My last practice in 2016, I used List<List<int>> dpList. Two obvious issues: the name is not meaningful one, and List<List<int>> is hard to tell what two lists are stored.The C# code passes all test cases on leetcode online judge. using System;using System.Collections.Generic;using System.Diagnostics;using System.Linq;using System.Text;using System.Threading.Tasks;namespace _210CourseProject{  public class Solution  {    /*     * Leetcode 210: course schedule II     * https://leetcode.com/submissions/detail/91139534/     */    static void Main(string[] args)    {        //RunSampleTestcase();        //RunSampleTestcase1();        RunSampleTestcase2();     }     /* [[1,0]]     *     * There are a total of 2 courses to take. To take course 1      * you should have finished course 0. So the correct course      * order is [0,1]     */    public static void RunSampleTestcase1()    {        int[,] prerequisites = new int[,] { { 1, 0 } };        var coursesInOrder = FindOrder(2, prerequisites);        string concatenatedCourses = string.Join(,, coursesInOrder);        Debug.Assert(concatenatedCourses.CompareTo(0,1) == 0             );    }    /*     *  int[,] prerequisite     *             *      *  4, [[1,0],[2,0],[3,1],[3,2]]     *  There are a total of 4 courses to take. To take course 3      *  you should have finished both courses 1 and 2. Both courses      *  1 and 2 should be taken after you finished course 0. So      *  there are 4 possible orderings.       *  [4,0,1,2,3]     *  [4,0,2,1,3]     *  [0,4,2,1,3]     *  [0,4,1,2,3]     */    public static void RunSampleTestcase2()    {        int[,] prerequisites = new int[,]{{1,0},{2,0},{3,1},{3,2}};         var coursesInOrder = FindOrder(5, prerequisites);        string concatenatedCourses = string.Join(,, coursesInOrder);        Debug.Assert(concatenatedCourses.CompareTo(4,0,1,2,3) == 0 ||                     concatenatedCourses.CompareTo(4,0,2,1,3) == 0 ||                     concatenatedCourses.CompareTo(0,4,2,1,3) == 0 ||                     concatenatedCourses.CompareTo(0,4,1,2,3) == 0            );     }    /*     * 1. Take prerequisites first     * 2. There may be multiple correct orders, you just need to return one of them.     * 3. If it is impossible to finish all courses, return an empty array     * Using topological sort, find all courses without prerequisites,      * put into the queue,      * and then dequeue one by one.      */    public static int[] FindOrder(int numCourses, int[,] prerequisites)    {        var dependents = new Stack<int>[numCourses];        for (int i = 0; i < numCourses; ++i)        {            dependents[i] = new Stack<int>();          }        // build dependency list for each prerequisite course,         // and set up indegree variable for each courses matching         // with prerequisite courses' number.        int[] indegree = new int[numCourses];        for (int i = 0; i < prerequisites.GetLength(0); ++i)        {            int takeFirst = prerequisites[i, 1];            int takeAfter = prerequisites[i, 0];            dependents[takeFirst].Push(takeAfter);             ++indegree[takeAfter];                     }        // add those courses with 0 indegree to the queue        Queue<int> queue = new Queue<int>();        for (int courseId = 0; courseId < numCourses; ++courseId)        {            if (indegree[courseId] == 0)            {                queue.Enqueue(courseId);            }        }        // take courses with indgree zero only        var coursesByTakingOrder = new int[numCourses];        int count = 0;        while (queue.Count > 0)        {                               int readyToTake = queue.Dequeue();            coursesByTakingOrder[count++] = readyToTake;               foreach (int courseId in dependents[readyToTake])            {                // decrement value of indegree by 1                 indegree[courseId]--;                // add to the queue if there is no prerequisite left                if (indegree[courseId] == 0)                   {                    queue.Enqueue(courseId);                }            }        }        if (count != numCourses)        {               return new int[]{};         }        return coursesByTakingOrder;    }  }}
Leetcode 210. Course Schedule II
c#;algorithm;programming challenge;sorting;graph
In a real life scenario I personally would take an object oriented approach instead of this algorithmic one to be able to verify invalid inputs (what about if there are indirect circular dependencies in the database?), have self-speaking code and debug hints etc.Here my suggestion:Solution.csusing System;using System.Collections.Generic;using System.Diagnostics;using System.Linq;namespace _210CourseProject {    public class Solution {        /*         * Leetcode 210: course schedule II         * https://leetcode.com/submissions/detail/91139534/         */        static void Main(string[] args) {            //Common variables            Int32[,] myTestData;            Course[] myCourses;            String[] myCourseIDs;            //Test case 1            myTestData = new Int32[,] { { 1, 0 } };            myCourses = GetCourses(null, myTestData);            myCourseIDs = (from e in myCourses select e.CourseID.ToString()).ToArray();            Console.WriteLine(String.Join(, , myCourseIDs));            //Test case 2            myTestData = new Int32[,] { { 1, 0 }, { 2, 0 }, { 3, 1 }, { 3, 2 }, { 2, 4 } };            myCourses = GetCourses(null, myTestData);            myCourseIDs = (from e in myCourses select e.CourseID.ToString()).ToArray();            Console.WriteLine(String.Join(, , myCourseIDs));            //Test case 3 (invalid indirect circular-dependency)            myTestData = new Int32[,] { { 1, 0 }, { 0, 2 }, { 2, 1 }, { 3, 2 }, { 2, 4 } };            try {                myCourses = GetCourses(null, myTestData);                Debug.Assert(false, An ArgumentException should have been thrown!);            } catch (ArgumentException ex) {                Console.WriteLine(ex.Message);            } catch (Exception ex) {                Debug.Assert(false, $An exception of type {typeof(ArgumentException).Name } expected, not of type {ex.GetType().Name }!);            }        }        private static Course[] GetCourses(Int32[] courseList, Int32[,] courseDependencies) {            Dictionary<Int32, Course> myDict = new Dictionary<Int32, Course>();            //Needed for courses without any dependencies (usually they won't appear in a m:n table)            if (courseList != null) {                Array.ForEach(courseList, (Int32 x) => {                    if (myDict.ContainsKey(x)) return;                    myDict.Add(x, new Course(x));                });            }            //Create courses and add dependency            if (courseDependencies != null) {                IEnumerable<CourseDependency> myDependencies = ConvertDependencies(courseDependencies);                foreach (var myDependency in myDependencies) {                    //Check arg                    Debug.Assert(myDependency != null, The dependency is never null.);                    //Create courses if needed                    Int32 myCourseID = myDependency.CourseID;                    Int32 myDependsOnCourseID = myDependency.DependsOn;                    Course myCourse = null;                    Course myDependsOnCourse = null;                    if (!myDict.TryGetValue(myCourseID, out myCourse)) {                        //Add course                        myCourse = new Course(myCourseID);                        myDict.Add(myCourseID, myCourse);                    }                    if (!myDict.TryGetValue(myDependsOnCourseID, out myDependsOnCourse)) {                        //Add course this one is depending on                        myDependsOnCourse = new Course(myDependsOnCourseID);                        myDict.Add(myDependsOnCourseID, myDependsOnCourse);                    }                    //Add dependency to course                    myCourse.AddDependency(myDependsOnCourse);                }            }            //Convert the result to an array and sort it            Course[] myResult = myDict.Values.ToArray();            Array.Sort(myResult);            //Return the result            return myResult;        }        private static IEnumerable<CourseDependency> ConvertDependencies(Int32[,] courseDependencies) {            //Check args            Debug.Assert(courseDependencies != null, The course dependency is never null!);            //Convert array elements            CourseDependency myDependency;            for (var i = 0; i < courseDependencies.Length / 2; i++) {                //Try to get values                try {                    Int32 myCourseID = courseDependencies[i, 0];                    Int32 myDependsOn = courseDependencies[i, 1];                    myDependency = new CourseDependency(myCourseID, myDependsOn);                } catch (Exception ex) {                    Debug.Assert(false, $An exception of type {ex.GetType().Name} was thrown!\r\n{ex});                    continue;                }                //Yield dependency                yield return myDependency;            }        }        //***********************************************************************************************        // INNER CLASS: CourseDependency        //***********************************************************************************************        private class CourseDependency {            //Constructors            public CourseDependency(Int32 courseID, Int32 dependsOn) {                //Check args                if (courseID == dependsOn) throw new ArgumentException($The course cannot depend on itself! (courseID = {courseID}));                //Assign values                CourseID = courseID;                DependsOn = dependsOn;            }            //Public Properties            public Int32 CourseID { get; }            public Int32 DependsOn { get; }            //Public Methods            public override String ToString() {                return ${CourseID} needs {DependsOn};            }        }    }}Course.cs:using System;using System.Collections.Generic;using System.Diagnostics;namespace _210CourseProject {    public class Course : IComparable<Course> {        //Private Fields        private Dictionary<Int32, Course> _DependencyDict;        private Dictionary<Int32, Course> _DependencyDictRecursive;        //Constructors        public Course(Int32 id) {            CourseID = id;        }        //Public Properties        public Int32 CourseID { get; }        //Public Methods        public void AddDependency(Course course) {            //Check arg            if (course == null) {                Debug.Assert(false, The course is never null.);                return; //Ignore in production            }            //Check whether the dependency is already assigned            var myDict = _DependencyDict;            if (myDict != null) {                Course myCourse = null;                if (myDict.TryGetValue(course.CourseID, out myCourse)) {                    //If it's the same reference, ignore it                    if (Object.ReferenceEquals(myCourse, course)) {                        Debug.Assert(false, Dependency was added multiple times!);                        return; //Ignore in production                    }                    //Otherwise throw an exception                    throw new ArgumentException($An other instance of course {course.CourseID} was already added as dependency!, nameof(course));                }            }            //Check self-dependency            if (course.CourseID == this.CourseID) {                Debug.Assert(false, $The course (ID={course.CourseID}) cannot depend on itself!);                return; //Ignore in production            }            //Check whether given course depends on us            if (course.DependsOn(this, true)) {                if (course.DependsOn(this, false)) {                    throw new ArgumentException($Course {course.CourseID} depends on course {this.CourseID} and therefore cannot be assigned as dependency., nameof(course));                }                throw new ArgumentException($Course {course.CourseID} indirectly depends on course {this.CourseID} and therefore cannot be assigned as dependency., nameof(course));            }            //Add dependency            DependencyDict.Add(course.CourseID, course);            _DependencyDictRecursive = null;        }        public Boolean DependsOn(Course otherCourse, Boolean recursive) {            //Check arg            if (otherCourse == null) {                Debug.Assert(false, The given course is never null.);                return false; //Ignore in production            }            //Get direct/indirect dependencies            var dict = recursive ? DependencyDictRecursively : _DependencyDict;            if (dict == null) return false;            //Return result            var result = dict.ContainsKey(otherCourse.CourseID);            return result;        }        public override String ToString() {            return $Course {CourseID};        }        //Private Properties        private Dictionary<Int32, Course> DependencyDict {            get {                var result = _DependencyDict;                if (result == null) {                    result = new Dictionary<Int32, Course>(3);                    _DependencyDict = result;                }                return result;            }        }        /// <summary>Gets the dependency dictionary containing direct and indirect dependencies. Watch out: The dictionary is null        /// if there are no direct dependencies.</summary>        private Dictionary<Int32, Course> DependencyDictRecursively {            get {                var result = _DependencyDictRecursive;                if (result == null) {                    var myDirectDict = _DependencyDict;                    if (myDirectDict == null) return null;                    result = GetRecursiveDependency(myDirectDict);                    _DependencyDictRecursive = result;                }                return result;            }        }        //Private Methods        private static Dictionary<Int32, Course> GetRecursiveDependency(Dictionary<Int32, Course> directDependencies) {            //Return null if null            if (directDependencies == null) return null;            //Get dependencies recursively            var myResult = new Dictionary<Int32, Course>();            foreach (Course myCourse in directDependencies.Values) {                AddRecursiveDependency(myResult, myCourse);            }            //Return the result            return myResult;        }        private static void AddRecursiveDependency(Dictionary<Int32, Course> resultDict, Course dependency) {            //If already added, return            if (resultDict.ContainsKey(dependency.CourseID)) return;            //Add this dependencies            resultDict.Add(dependency.CourseID, dependency);            //Add child dependencies            Dictionary<Int32, Course> myChildDict = dependency._DependencyDict;            if (myChildDict == null) return;            foreach (Course myChild in myChildDict.Values) {                AddRecursiveDependency(resultDict, myChild);            }        }        //Interface Implementation        Int32 IComparable<Course>.CompareTo(Course other) {            //Check arg            if (other == null) {                Debug.Assert(false, The other is never null.);                return 1; //Ignore in production            }            //Check dependencies            if (this.CourseID == other.CourseID) return 0;            if (this.DependsOn(other, true)) return 1;            if (other.DependsOn(this, true)) return -1;            if (this.CourseID > other.CourseID) return 1;            if (this.CourseID < other.CourseID) return -1;            return 0;        }    }}