Graph Traversal for Dependency Trees

MediumPython00:00

Practice interviewer

In session

5 left

00:00

Your question is Graph Traversal for Dependency Trees. Start with the requirements on the right.

Run and submit as often as you like. When you're ready, talk me through your approach or go straight to the code.

You need to log in / sign up to run or submit.

Problem

Airbus Skywise services are assembled from modules that may depend on other modules. Given each module and its direct dependencies, return a valid build order that places every dependency before the modules requiring it.

If multiple valid orders exist, return the lexicographically smallest one. If the dependency graph contains a cycle, return an empty list because no valid build can be produced.

Formal Specification

Implement resolve_dependencies(dependencies).

dependencies is a dictionary mapping a module name to a list of its direct dependency names.
Every dependency name also appears as a key in dependencies.
Return a list of module names containing every module exactly once, in build order.
Return [] if the graph contains a cycle.

A dependency edge A -> B means A must be built before B.

Constraints

1 <= len(dependencies) <= 10^5
The total number of dependency references is at most 2 * 10^5
Module names are unique non-empty strings of length at most 100
Every dependency name appears as a key in dependencies
A module may depend on zero or more other modules

Function Signature

def resolve_dependencies(dependencies):

Your solutionPython 3

You need to log in / sign up to run or submit.

Run your code to see test output