Leetcode 210. Course Schedule II

Question

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:

1. Add two test cases, work on the second test case with 4 possible solutions.

2. 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;
    }
  }
}

Answer 1

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.cs

using 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;
        }

    }

}