Topological build order for services

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

Services must build in an order that respects dependencies: a library before the app that imports it. Produce a valid topological order.

A build system must build services in an order where every dependency is built first. When several services are ready, the build should be predictable: pick the one that comes first alphabetically. deps maps each service to the services it needs first. Return a build order where every service comes after its dependencies. When several are ready, pick the alphabetically smallest. If there is a cycle, return []. Write build_order(deps). For {'app': ['lib'], 'lib': []} the answer is ['lib', 'app']. For {'a': ['b'], 'b': ['a']} there is a cycle, so the answer is []. The starter file already has the function name and its print lines. Keep them and fill in the body.

Requirements

• Build every dependency before the service that needs it.
• Include services that only appear in dependency lists.
• Choose the alphabetically smallest ready service next.
• Return [] when there is a cycle.

Constraints

• deps is a dictionary from service to a list of prerequisites.
• Names are strings.

Examples

Input: build_order({'app': ['lib'], 'lib': []}) Output: ['lib', 'app'] This input follows the stated rules and produces this output.

Topics: lakebench, python, graphs.

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