Validate course catalog dependencies
Company: Google
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: Medium
Interview Round: Technical Screen
Design a function to validate an e-learning course catalog. You are given:
(
1) a set of course IDs, and
(
2) a list of prerequisite pairs (u, v) meaning course v requires course u. Determine if the catalog is valid: no prerequisite references a non-existent course, and there are no cycles in the dependency graph. If valid, return true and a possible ordering of courses; otherwise return false and report the set of missing course references and at least one cycle you detect. Specify your algorithm, time and space complexity.
Quick Answer: This question evaluates understanding of graph algorithms and data validation, specifically dependency analysis, cycle detection, and topological ordering.