Mark As Completed Discussion

Good evening! Here's our prompt for today.

Here's a classic challenge that comes up in real-life interviews surprisingly often. Interviewers like it as a way to assess your ability to find the right data structure for a non-obvious and non-trivial use case.

Description

The prompt is as follows: you're a university student currently trying to plan their schedule for the following semester. There is n number of courses that you'll need to take to stay on track for graduation.

Description

Of the n courses, several have prerequisite courses that you'll need to take beforehand. This requirement is defined using an array with two elements. A prerequisite pair in the form [course, prerequisite] such as [4, 3] means that you need to take course 3 before course 4.

SNIPPET
1n = 3
2preReqs = [[1, 0], [2, 1]]
3// You need to take course 0 before 1, and 1 before 2, 
4// but that is an appropriate order.
5// Running areAllCoursesPossible(n, preReqs) would return true.

However, sometimes the prerequisite pairings are not possible-- this will prevent you from staying on track! As an example, if we add an additional prerequisite requirement that you need to finish 2 before 0, it wouldn't work:

SNIPPET
1n = 3
2preReqs = [[1, 0], [2, 1], [0, 2]]
3// This is impossible because you can't finish 2 before 0,
4// since you need to finish 1 before 2, and 0 before 1.

In the above, an order of 0 -> 1 -> 2 or 2 -> 1 -> 0 would not fulfill the requirements, so areAllCoursesPossible(n, preReqs) would return false.

Given n and a list of prerequisite pairs, can you write a method to determine if it is possible to take all the courses? Hint: what are the conditions under which a prerequisite setup is impossible?

Constraints

  • Number of possible courses <= 100000
  • Number of prerequisites <= 100000
  • The prerequisites array will always contain the value >= 0
  • Expected time complexity : O(V+E) , where V are the courses and E are the prerequisites
  • Expected space complexity : O(V)

Try to solve this here or in Interactive Mode.

How do I practice this challenge?

JAVASCRIPT
OUTPUT
:001 > Cmd/Ctrl-Enter to run, Cmd/Ctrl-/ to comment

We'll now take you through what you need to know.

How do I use this guide?

Access all course materials today

The rest of this tutorial's contents are only available for premium members. Please explore your options at the link below.

Returning members can login to stop seeing this.