Katkat
Back

Validate a training courses catalog

AmazonSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

This problem tests your ability to model prerequisites as a directed graph and detect circular dependencies using cycle detection algorithms (Kahn's or DFS).

Validate Course Prerequisites

You are given a list of courses, where each course has a unique ID, and a list of dependency pairs where [A, B] means course A is a prerequisite for course B. A valid curriculum must not contain any circular dependencies (e.g., A requires B, B requires C, and C requires A).

Write a function is_valid_curriculum(num_courses, prerequisites) that returns True if all courses can be completed, and False otherwise.

Function Signature

def is_valid_curriculum(num_courses: int, prerequisites: List[List[int]]) -> bool

Input

  • num_courses: An integer representing the total number of courses (labeled 0 to num_courses - 1).
  • prerequisites: A list of lists where each sub-list contains two integers [pre, post].

Example 1

Input: num_courses = 2, prerequisites = [[1, 0]] Output: True Explanation: Course 1 is a prerequisite for 0. No cycles exist.

Example 2

Input: num_courses = 2, prerequisites = [[1, 0], [0, 1]] Output: False Explanation: Course 1 requires 0, and 0 requires 1. This is a circular dependency.

Constraints

  • 1 <= num_courses <= 2000
  • 0 <= len(prerequisites) <= 5000
  • All prerequisite pairs are unique.

Edge Cases

  • num_courses with no prerequisites should return True.
  • Disconnected graph components should be handled correctly.

Hints

Hint 1

Represent the courses as nodes in a directed graph where an edge from U to V means U must be taken before V.

Hint 2

A graph has a valid ordering if and only if it is a Directed Acyclic Graph (DAG).

Hint 3

Consider using Kahn's algorithm (Topological Sort) by tracking the in-degree of each node or using Depth-First Search with a recursion stack tracking visited nodes.

Follow-up questions

  • If the curriculum is valid, can you return an actual sequence of courses that a student could follow to complete their degree?
  • How would you modify your solution if a student is allowed to take at most two courses simultaneously?
  • What are the time and space complexity of your solution in terms of V (courses) and E (prerequisites)?