Quick Overview

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

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.

You are validating an e-learning course catalog. You are given: 1. `course_ids` — a list of distinct course identifiers (the catalog). 2. `prereqs` — a list of prerequisite pairs `(u, v)`, where each pair means "course `v` requires course `u`" (i.e. a directed edge `u -> v`, you must take `u` before `v`). Determine whether the catalog is valid. A catalog is **valid** when BOTH conditions hold: - **No missing references:** every course that appears in any prerequisite pair exists in `course_ids`. - **No cycles:** the dependency graph (over courses that exist in the catalog) is acyclic. Return a tuple `(valid, ordering, missing, cycle)`: - `valid` — `True` if and only if there are no missing references and no cycles. - `ordering` — a valid topological ordering of all catalog courses **only when `valid` is `True`**. When a cycle exists, `ordering` is `[]`. When the graph is acyclic but references are missing, `ordering` still holds a valid topological order of the existing courses (the graph itself is well-formed; only the references are dangling). - `missing` — the sorted list of distinct course IDs referenced by some prerequisite pair but absent from `course_ids` (empty list if none). - `cycle` — when a cycle exists, one concrete cycle as a list of course IDs where the first and last element are the same (e.g. `['A', 'B', 'C', 'A']`); otherwise `[]`. Resolve ties deterministically: when multiple courses are simultaneously available in the topological sort, emit them in ascending (lexicographic) order. State your algorithm and its time and space complexity.

Constraints

  • 0 <= number of courses <= 10^5
  • 0 <= number of prerequisite pairs <= 2 * 10^5
  • Course IDs are distinct strings within course_ids.
  • A prerequisite pair (u, v) may reference an ID not present in course_ids; such IDs must be reported in `missing`.
  • A pair (u, v) means u must be completed before v (directed edge u -> v).

Examples

Input: (['A', 'B', 'C'], [('A', 'B'), ('B', 'C')])

Expected Output: (True, ['A', 'B', 'C'], [], [])

Explanation: Linear chain A->B->C is acyclic with all references present, so it is valid and the unique topological order is [A, B, C].

Input: (['A', 'B', 'C'], [('A', 'B'), ('B', 'C'), ('C', 'A')])

Expected Output: (False, [], [], ['A', 'B', 'C', 'A'])

Explanation: A->B->C->A forms a cycle, so the catalog is invalid, no ordering is returned, and one detected cycle is A->B->C->A.

Hints

  1. Separate the two failure modes: a missing reference (an ID in some pair that is not in the catalog) and a cycle (a circular dependency). Scan all pairs once to collect missing IDs before touching the graph.
  2. Build the dependency graph only over courses that actually exist, with edge u -> v for each pair (u, v). Track in-degree per node.
  3. Use Kahn's algorithm (BFS on in-degree-zero nodes). If the produced ordering contains every catalog course, the graph is acyclic; if it is shorter, a cycle exists among the nodes that never reached in-degree zero.
  4. To report one concrete cycle, run a DFS restricted to the nodes that still have positive in-degree after Kahn's sort; the first gray (on-stack) node you revisit closes a cycle — slice it out of the current DFS path.
  5. For deterministic output, break ties in lexicographic order whenever multiple nodes are simultaneously ready.

Loading coding console...