Bird
Raised Fist0

Consider the optimal BFS topological sort code for minimum semesters. What is the output for n = 1 and relations = []?

medium🧾 Code Trace Q4 of Q15
Topological Sort - Parallel Courses (Minimum Semesters)
Consider the optimal BFS topological sort code for minimum semesters. What is the output for n = 1 and relations = []?
A1
B-1
C0
Dn (input size)
Step-by-Step Solution
Solution:
  1. Step 1: Initialize queue and indegree

    With no relations, indegree[1] = 0, so queue = [1].
  2. Step 2: Process the single course

    One iteration increments semester to 1, processes course 1, processed = 1.
  3. Final Answer:

    Option A -> Option A
  4. Quick Check:

    One course with no prerequisites takes one semester [OK]
Quick Trick: Single course with no prereqs -> 1 semester [OK]
Common Mistakes:
MISTAKES
  • Returning 0 semesters for single course
  • Returning -1 incorrectly
Trap Explanation:
PITFALL
  • Candidates may think no prerequisites means zero semesters, but at least one semester is needed.
Interviewer Note:
CONTEXT
  • Checks handling of minimal edge cases in BFS topological sort.
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