Validate a training courses catalog

Q: Validate a training courses catalog

This is a Coding & Algorithms interview question from Amazon for Software Engineer roles. View the full question and solution on PracHub.

Q: How do I approach Coding & Algorithms interview questions?

Coding & Algorithms questions require understanding of core concepts and practice. PracHub provides solutions with explanations to help you master coding & algorithms interviews.

Question

Loading...

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:

Every prerequisite referenced by a course exists in the catalog.
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

Validate a training courses catalog

Comments (0)