Skip to main content

Parallel Courses

Leetcode #1136, "Medium" Parallel Courses​

I'll use this Leetcode problem as an Example of how I approach setting up & debugging a Unit Test of a Leetcode Solution​

I am still a bit of a Python newb so please bear with me.​

How to set a Breakpoint & Debug, in VS Code​

In VS Code, Here's a basic example setting a Breakpoint on Line 7 of the testing file (test_parallelCourses1136.py), then activating the Debugger, and then stepping into the program as it runs the test code with the arguments we test against:

self.assertEqual(instance_Solution.minimumSemesters(3, [[1,3],[2,3]]), 2)

  • Function Argument inputs:
    • N = 3
    • relations = [[1,3],[2,3]]
  • Outputs returned from the solution (in the ideal case of a correct solution)
    • the target returned value = 2

Brief video guide on how to set a breakpoint & debug a python script​

...while unit testing, in the context of the following two example files: A unit test, and the script it tests

Note: This Embedded video may not work if you have enabled extensions such as PrivacyBadger, AdBlock, and others that interfere with Javascript.

Actually.. It looks like Google Drive might not like to have its videos embedded

The UnitTest testfile​


#Filename: test_parallelCourses1136.py

import unittest
from parallelCourses1136 import Solution
# If you notice "parallelCourses1136" above..
# parallelCourses1136 = filename of the Solution file (i.e. parallelCourses1136.py).  1136 refers to the Leetcode problem number: It's Leetcode Problem #1136.
class TestSolution(unittest.TestCase):

  # Note: in Python, at least with unittest, tests functions must begin with "test".  Often people use "test_someFunction" by convention.
  # Also be aware: Tests run in alphabetical order, so you may eventually need to name something test_a_someFn so that it runs betfore test_b_someFn.
  def test_minimumSemesters(self):
    instance_Solution = Solution()
    # **** Set the Breakpoint on this next line: ****
    self.assertEqual(instance_Solution.minimumSemesters(3, [[1,3],[2,3]]), 2)

if __name__ == '__main__':
  unittest.main()

The Solution file​

Source: Code from the Editorial section of Leetcode problem # 1136: "Parallel Courses",

It's a problem involving Graph Theory (Topological Ordering, Directed Acyclic graphs) and Binary Search Trees (Depth or Breadth First Search sorting algorithms)


# Filename: parallelCourses1136.py
# This is the solution from the Leetcode Editorial.
# I copied it in order to run the VS Code Debugger on it, via the unittest breakpoint above.  In this way, I could better understand how the arguments are acted upon by the program.  The program assembles various data structures (e.g. dictionaries & arrays) as it goes about calculating and organizing data into the solution.

class Solution:
    def minimumSemesters(self, N, relations):
        graph = {i: [] for i in range(1, N + 1)}
        in_count = {i: 0 for i in range(1, N + 1)}  # or in-degree
        for start_node, end_node in relations:
            graph[start_node].append(end_node)
            in_count[end_node] += 1

        queue = []
        # we use list here since we are not
        # poping from front the this code
        for node in graph:
            if in_count[node] == 0:
                queue.append(node)

        step = 0
        studied_count = 0
        # start learning with BFS
        while queue:
            # start new semester
            step += 1
            next_queue = []
            for node in queue:
                studied_count += 1
                end_nodes = graph[node]
                for end_node in end_nodes:
                    in_count[end_node] -= 1
                    # if all prerequisite courses learned
                    if in_count[end_node] == 0:
                        next_queue.append(end_node)
            queue = next_queue

        return step if studied_count == N else -1