Validate a training courses catalog
Company: Amazon
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
You are given a catalog of training courses. Each course has:
- a unique `course_id`
- a list of prerequisite course IDs `prereqs` (possibly empty)
Write a function `isValidCatalog(courses) -> bool` that validates the catalog.
A catalog is considered **valid** if:
1. Every prerequisite referenced by a course **exists** in the catalog.
2. The prerequisite relationships contain **no cycles** (a course cannot depend on itself directly or indirectly).
Follow-ups (discuss, no need to implement unless asked):
- How would you also return a valid course-taking order when it’s valid?
- Time and space complexity.
- Compare DFS vs BFS approaches for detecting cycles / producing a topological order.
Example:
- `A: [B, C]`, `B: [C]`, `C: []` -> valid
- `A: [B]`, `B: [A]` -> invalid (cycle)
- `A: [X]` where `X` not in catalog -> invalid
Quick Answer: This question evaluates understanding of directed graphs, cycle detection, dependency validation, and data consistency in the context of a training course catalog with prerequisites.
Return whether every prerequisite exists and the prerequisite graph is acyclic.
Constraints
- Inputs are Python literals matching the function signature.
- Return a deterministic exact-match value.
Examples
Input: ({'A':['B','C'], 'B':['C'], 'C':[]},)
Expected Output: True
Explanation: Valid DAG.
Input: ({'A':['B'], 'B':['A']},)
Expected Output: False
Explanation: Cycle.
Input: ({'A':['X']},)
Expected Output: False
Explanation: Missing prerequisite.
Hints
- Choose a representation that makes the requested operation direct.
- Handle empty inputs and boundary cases first.