Katkat
Back

Order Named Tasks by Dependencies, Choosing the Alphabetically Smallest Order

ByteDanceSoftware Engineer · Onsite
MediumSoftware EngineerOnsiteCoding & Algorithms

Last updated

Given named tasks and before-and-after dependency pairs, return an order that satisfies every dependency, choosing the alphabetically smallest valid order, or an empty list when the dependencies contain a cycle. It tests topological sorting, cycle detection and deterministic tie-breaking.

You are given the names of a set of tasks and a list of dependencies, where a dependency [before, after] means task before must be done before task after. Return an order of all the tasks that satisfies every dependency. If the dependencies contain a cycle, so that no such order exists, return an empty list.

When more than one order is valid, return the alphabetically smallest one: compare two valid orders name by name, and at the first position where they differ, the order whose name comes first alphabetically is the smaller one.

Function Signature

def task_order(tasks: list[str], dependencies: list[list[str]]) -> list[str]:

Rules

  • Every task appears exactly once in the result, including tasks that have no dependencies.
  • Names are compared with ordinary string comparison (Python's < on str).
  • A dependency may be listed more than once; repeats mean the same as a single copy.
  • A task that depends on itself is a cycle. If any cycle exists anywhere, return [], even if some tasks could still be ordered.

Constraints

  • 1 <= len(tasks) <= 10^4
  • 0 <= len(dependencies) <= 5 * 10^4
  • task names are distinct and consist of 1 to 20 lowercase English letters
  • every name in dependencies appears in tasks

Examples

Example 1

Input: tasks = ["deploy", "build", "test", "lint", "fetch"]
 dependencies = [["fetch", "build"], ["build", "test"], ["lint", "test"], ["test", "deploy"]]
Output: ["fetch", "build", "lint", "test", "deploy"]

Only fetch and lint have no prerequisites, and fetch comes first alphabetically. After it, build is allowed and comes before lint. test waits for both build and lint, and deploy waits for test.

Example 2

Input: tasks = ["a", "b", "c"]
 dependencies = [["a", "b"], ["b", "c"], ["c", "b"]]
Output: []

b and c each wait for the other. Task a could be done, but no complete order exists.

Example 3

Input: tasks = ["zeta", "alpha", "mid"]
 dependencies = []
Output: ["alpha", "mid", "zeta"]

With no dependencies, the answer is simply alphabetical; the input order of tasks does not matter.