Topological Ordering for Dependencies

MediumPython00:00

Practice interviewer

In session

5 left

00:00

Your question is Topological Ordering for Dependencies. 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

An AMD ROCm build pipeline contains tasks such as kernel compilation, linking, testing, and packaging. Each dependency is given as [prerequisite, task], meaning the prerequisite must be completed before the task.

Implement dependency_order(tasks, dependencies) to return the lexicographically smallest valid completion order. If the dependency graph contains a cycle, return an empty list because no valid order exists. Tasks with no dependencies must still appear in the result. Duplicate dependency pairs should be treated as one dependency.

Formal Specification

Input tasks: a list of unique strings representing all tasks.
Input dependencies: a list of two-element lists [prerequisite, task].
Output: a list containing every task exactly once in valid dependency order, or [] if a cycle exists.
The lexicographically smallest order is required when multiple valid orders exist.

Constraints

1 <= len(tasks) <= 2 * 10^5
0 <= len(dependencies) <= 4 * 10^5
Task names are unique non-empty strings of length at most 50
Every dependency references tasks in tasks
Duplicate dependency pairs may occur

Function Signature

def dependency_order(tasks, dependencies):

Your solutionPython 3

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

Run your code to see test output