Course Schedule
1Try it yourself first
Think for 20-30 minutes before you open any hint. Being stuck is where the learning happens.
Only for you, saved in this browser. After you see the approach you will compare it with your idea.2What is being asked
You must take numCourses courses; each prerequisite pair [a, b] says you must take b before a. Can you finish all courses?
3Hint ladder
Take one rung at a time. Stop as soon as the idea clicks.
- Hint 1Which courses can you take right now?
- Hint 2When you take a course, whose waiting count goes down?
4The approach
Have you tried the hints? The approach is built as a path from the obvious way to the clever one.
A college timetable. Some courses have no prerequisite: take them first. Each course you finish unlocks others; when a course has no unmet requirement left, it joins the "ready" list. If at the end some courses are never ready, they are waiting on each other in a circle (A needs B and B needs A): impossible.
- The obvious way
Depth-first search with a path set to find a cycle works too; Kahn's is easier to reason about.
- The key insight
For every course count how many prerequisites it still waits for and note which courses it unlocks. Queue the courses waiting on nothing. Repeatedly take a course from the queue, count it as taken, and reduce the waiting count of the courses it unlocks, queueing any that reach zero. All courses taken means no cycle: True.
- The algorithm
- Count the unmet prerequisites; list who each course unlocks.
- Queue every course with zero.
- Take a course; reduce its dependants' counts; queue those that hit zero.
- True if all courses were taken.
Watch it run
ExamplenumCourses = 4, prerequisites = [[1,0],[2,1],[3,1],[3,2]]
Course 0 needs nothing: it is ready. Courses 1, 2, 3 wait for 1, 1, 2 courses.
ready: 0
Where people slip
- The pair is [course, needed]: the second one comes first.
- A course that depends on itself is a cycle: it never becomes ready.
How close was your idea?
You did not write an idea, and that is fine.
Be honest with yourself. This sets your revision list.
5Code
Try writing it yourself from the steps first. Then compare.
from collections import deque
def can_finish(num_courses, prerequisites):
waiting_on = [0] * num_courses # unmet prerequisites of each course
unlocks = [[] for _ in range(num_courses)] # courses unlocked by finishing this one
for course, needed in prerequisites:
unlocks[needed].append(course)
waiting_on[course] += 1
ready = deque(course for course in range(num_courses) if waiting_on[course] == 0)
taken = 0
while ready:
course = ready.popleft()
taken += 1
for next_course in unlocks[course]:
waiting_on[next_course] -= 1
if waiting_on[next_course] == 0:
ready.append(next_course) # nothing left to wait for
return taken == num_coursesNow close this and write it again from memory, in the language you will use in the interview. Reattempt after 1 day, 7 days and about 30 days.
6Still stuck? Watch a video
Seeing someone explain it out loud can make it click. Try the video after you have read the approach above.