Bird
Raised Fist0

Given the following partial state of the indegree array during BFS topological sort for n=4 courses: [0, 0, 1, 0, 1] (1-based indexing), and the queue contains courses [1, 4], which prerequisite relation is missing from the input?

hard🔄 Reverse Engineer Q9 of Q15
Topological Sort - Parallel Courses (Minimum Semesters)
Given the following partial state of the indegree array during BFS topological sort for n=4 courses: [0, 0, 1, 0, 1] (1-based indexing), and the queue contains courses [1, 4], which prerequisite relation is missing from the input?
ACourse 2 depends on course 3
BCourse 3 depends on course 2
CCourse 4 depends on course 3
DCourse 1 depends on course 2
Step-by-Step Solution
Solution:
  1. Step 1: Analyze indegree array

    Indegree[3] = 1 means course 3 has one prerequisite not yet processed.
  2. Step 2: Analyze queue contents

    Courses 1 and 4 have indegree 0, so their prerequisites are satisfied.
  3. Step 3: Identify missing prerequisite

    Since course 3 has indegree 1, it must depend on course 2 (which is not in queue), so course 3 depends on course 2.
  4. Final Answer:

    Option B -> Option B
  5. Quick Check:

    Indegree and queue states imply course 3 depends on course 2 [OK]
Quick Trick: Indegree > 0 means unmet prerequisite; queue has zero indegree courses [OK]
Common Mistakes:
MISTAKES
  • Confusing direction of dependency
  • Ignoring queue contents
Trap Explanation:
PITFALL
  • Candidates often reverse dependency direction or ignore queue state when reasoning backwards.
Interviewer Note:
CONTEXT
  • Tests ability to reverse engineer input from intermediate BFS state.
Master "Parallel Courses (Minimum Semesters)" in Topological Sort

3 interactive learning modes - each teaches the same concept differently

Want More Practice?

15+ quiz questions · All difficulty levels · Free

Free Signup - Practice All Questions
More Topological Sort Quizzes