Medium

Google-styleLinkedIn-style

Determine a Valid Course Completion Order DSA Interview

Given a number of courses and a list of prerequisite pairs, determine a valid order to complete all courses, or report that no valid order exists.

Mock Interview with AI

1. Problem Statement

You are given a number of courses labeled 0 to n-1 and a list of prerequisite pairs [course, prereq] meaning prereq must be completed before course. Return a valid order to complete all courses, or an empty list if it is impossible.

2. Live Coding Format

Choose Python, JavaScript, Java, or C++, then solve while explaining your reasoning to the live interviewer.

Validation uses handwritten tests only. The MVP does not compile or run code, and it does not provide AI algorithm completion.

3. Key Focus Areas

1
Problem clarification and contract
2
Approach exploration and optimality
3
Think-aloud communication and pacing
4
Implementation correctness
5
Code quality and language fluency
6
Handwritten tests and dry run
7
Debugging and self-correction
8
Complexity analysis
9
Follow-up performance

4. What Strong Candidates Should Demonstrate

✓Clarify prerequisite direction, duplicate edges, and impossible-order behavior before coding.
✓Explain a naive repeated-scan baseline and improve to Kahn's algorithm or DFS-based topological sort.
✓Think aloud while implementing careful graph traversal and cycle detection.
✓Validate with explicit expected outputs and a top-to-bottom handwritten dry run.
✓Analyze time and space complexity and handle a bounded follow-up modification.

Evaluation Guide

This is an evaluation framework, not a single model answer. Strong designs may make different choices when their assumptions and trade-offs are explicit.

Problem clarification and contract

10%

Senior signals

✓Clarifies the direction of the prerequisite relationship, whether duplicate or redundant edges can appear, and what to return when a cycle makes completion impossible.
✓Confirms whether courses with no prerequisites and no dependents should still appear in the output.

Staff-level signals

◆Asks whether any valid order is acceptable or a specific tie-breaking order (e.g., lowest course number first) is required.

Common red flags

×Codes immediately while assuming the graph is guaranteed acyclic without confirming.

Approach exploration and optimality

20%

Senior signals

✓Explains a naive baseline that repeatedly rescans all courses looking for one with no remaining unmet prerequisites, identifies its repeated-scan bottleneck, and improves to Kahn's in-degree BFS algorithm or a DFS-based topological sort with cycle detection.
✓Explains how a cycle is detected: either the in-degree queue empties before all courses are placed, or a DFS revisits a node currently on the recursion stack.

Staff-level signals

◆Discusses how the approach would need to change for a very large or sparse prerequisite graph, or for incremental prerequisite additions.

Common red flags

×Starts implementation without explaining an approach even after one interviewer prompt.
×Proposes a DFS without any cycle-detection mechanism, risking infinite recursion.

Think-aloud communication and pacing

10%

Senior signals

✓Explains the plan before coding and narrates in-degree updates or DFS visitation states while implementing.
✓Paces the core solution to leave time for validation and the follow-up.

Common red flags

×Writes substantial code silently and cannot explain what the code is doing.

Implementation correctness

25%

Senior signals

✓Implements a correct topological sort (BFS in-degree queue or DFS with three-state visitation) that detects cycles and returns an empty result when completion is impossible.
✓Handles courses with no prerequisites, disconnected groups of courses, duplicate edges, and a cycle.
✓Provides a convincing invariant argument for why the produced order respects all prerequisite constraints.

Common red flags

×Produces an order that violates at least one prerequisite constraint, or fails to detect a cycle.
×Final code contains a material correctness bug that the candidate does not identify.

Code quality and language fluency

15%

Senior signals

✓Produces readable, language-appropriate code with a clear adjacency structure, in-degree array or visitation-state array, and a defined queue or stack.

Common red flags

×Contains adjacency-construction errors or syntax-level incoherence that prevents credible reasoning.

Handwritten validation, dry run, and debugging

10%

Senior signals

✓Provides explicit inputs and expected outputs before tracing the code from top to bottom, including a drawn dependency graph.
✓Covers no-prerequisite courses, disconnected components, duplicate edges, and a cycle.
✓Finds and fixes an error independently, then re-validates the affected path.

Common red flags

×Claims the code works without a representative trace.

Complexity analysis and follow-up

10%

Senior signals

✓States time complexity in terms of courses and prerequisite edges (O(V + E)) and auxiliary space for the adjacency structure and in-degree or visitation array, comparing it with the repeated-scan baseline.

Staff-level signals

◆Discusses how the approach would scale for a very large number of courses and edges.

Common red flags

×Cannot state the complexity of the implemented solution.
×Fails a reasonable follow-up despite having at least five minutes and receiving bounded clarification.

Trade-offs to articulate

Repeatedly rescanning for a course with no remaining prerequisites is simple but costs quadratic time in the number of courses.
Kahn's BFS in-degree algorithm achieves linear time in courses plus edges and naturally detects cycles when the queue empties early.
A DFS-based approach with three-state visitation achieves the same complexity but requires careful tracking of nodes currently on the recursion stack to detect cycles.

Practice follow-up questions

1.Coding follow-up: modify the solution to determine whether the valid course order is unique, i.e., whether there is exactly one valid completion order.
2.Verbal extension: how would the approach change if prerequisites could be added incrementally and you needed to answer 'is this still completable' after each addition?

Want interactive feedback?

Practice this problem in the live coding workspace while the interviewer probes your clarification, algorithm, implementation, complexity, and handwritten tests.

Start Interview

Core Concepts

GraphsTopological SortCycle DetectionComplexity Analysis