Katkat
Back

Validate course catalog dependencies

GoogleSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

This question evaluates understanding of graph algorithms and data validation, specifically dependency analysis, cycle detection, and topological ordering.

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.