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.
