Package Build Order and Cycle Resolverhard

Package Build Order and Cycle Resolver

hard Python for AI 20–25 min

NumPy allowed · plain Python earns 10 bonus points

Compute package compilation ordering and identify cyclic dependencies across software build graphs.

Related Skills

Task

Implement resolve_build_order(dependencies): given a dictionary where keys are packages and values are lists of required prerequisites, determine a valid build sequence. Return {"has_cycle": bool, "build_order": list[str]}. If a cycle exists, build_order must be []. Break ties among available packages alphabetically.

Function Signature

resolve_build_order(dependencies: dict[str, list[str]]) -> dict

Examples

Example 1: Diamond Build Dependencies
Input: dependencies = {'A': ['B', 'C'], 'B': ['D'], 'C': ['D'], 'D': []}
Output: {'has_cycle': False, 'build_order': ['D', 'B', 'C', 'A']}

Example 2: Direct Circular Dependency
Input: dependencies = {'A': ['B'], 'B': ['A']}
Output: {'has_cycle': True, 'build_order': []}

Example 3: Implicit Prerequisite Nodes
Input: dependencies = {'A': ['B']}
Output: {'has_cycle': False, 'build_order': ['B', 'A']}

Constraints

Libraries are allowed; a plain-Python solution earns 10 bonus points.
Package dependencies can reference packages not explicitly present as keys.
Deterministic alphabetical tie-breaking on ready nodes.

Python3Saved ✓

def resolve_build_order(dependencies: dict[str, list[str]]) -> dict:

"""Resolve build order for packages where dependencies maps pkg -> list of prerequisites.

Return {'has_cycle': bool, 'build_order': list[str]}.

If has_cycle is True, build_order is []. Break ready-task ties alphabetically."""

# Your implementation here

pass

Case 1: Diamond Build Dependencies

Input: dependencies = {'A': ['B', 'C'], 'B': ['D'], 'C': ['D'], 'D': []}

Expected: {'has_cycle': False, 'build_order': ['D', 'B', 'C', 'A']}

Case 2: Direct Circular Dependency

Input: dependencies = {'A': ['B'], 'B': ['A']}

Expected: {'has_cycle': True, 'build_order': []}

Case 3: Implicit Prerequisite Nodes

Input: dependencies = {'A': ['B']}

Expected: {'has_cycle': False, 'build_order': ['B', 'A']}