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.

A pipeline config says which tasks depend on which. A cycle (a depends on b, b depends on a) means it can never run. deps maps each task to the list of tasks it depends on. Return True if the dependencies contain a cycle, otherwise False. Tasks that only appear in dependency lists must also be checked. Write has_cycle(deps). {'a': ['b'], 'b': ['a']} has a cycle (a needs b, b needs a), so the answer is True. {'a': ['b'], 'b': []} has none, so False. The starter file already has the function name and its print lines. Keep them and fill in the body.

Requirements

• Detect any cycle in the dependency map.
• Include tasks that only appear as dependencies.
• Return True for a cycle, False otherwise.
• A task that depends on itself is a cycle.

Constraints

• deps is a dictionary from task to a list of tasks.
• Tasks can be missing as keys if they only appear in lists.

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