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.

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

Read the full Google Software Engineer interview experience this question came from

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...