Skip to content
LakeBench
ProblemsCommunityPricing
Sign inStart practicing

Detect a cycle in a task dependency map

Python data engineering interview problem. Difficulty: advanced. Pattern: Recursion. About 20 minutes. Part of the Pro drill bank.

A task graph says which jobs depend on which. A cycle means the scheduler can never start. Detect that before launch.

Return whether a task dependency map contains a cycle.

Requirements

  • A cycle exists if following edges can return to a node already on the current path.
  • Disconnected nodes are fine.

Constraints

  • deps: adjacency map of task -> prerequisites or successors.
  • A node pointing at itself is a cycle.

Examples

Input: has_cycle({'a': ['b'], 'b': ['a']}) Output: True This input follows the stated rules and produces this output.

Topics: lakebench, python, graphs.

More Python interview questions · All interview problems · Learn data engineering

advanced

Detect a cycle in a task dependency map

Interview-style drill: Given a dict mapping each task to its prerequisites, determine whether the dependencies contain a cycle.

Return whether a task dependency map contains a cycle.