Order Named Tasks by Dependencies, Choosing the Alphabetically Smallest Order
Company: ByteDance
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
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
```python
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**
```text
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**
```text
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**
```text
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.
Overview: 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, `tasks`, and a list of dependencies, `dependencies`. Each dependency is a pair `[before, after]` meaning task `before` must be done before task `after`. Return an order of all the tasks (a list of task names) 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.
**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`); for example `"ab" < "abc" < "b"`.
- 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.
**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.
**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`.
No numeric value is passed in or returned, so nothing here can exceed 2^31 - 1.
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.
- Each dependency is a pair [before, after]; a pair may repeat, and before may equal after (a self-dependency, which is a cycle).
Examples
Input: (['deploy', 'build', 'test', 'lint', 'fetch'], [['fetch', 'build'], ['build', 'test'], ['lint', 'test'], ['test', 'deploy']])
Expected Output: ['fetch', 'build', 'lint', 'test', 'deploy']
Explanation: Source example 1: fetch beats lint among the first ready tasks, then the newly unlocked build beats lint, test waits for both build and lint, and deploy waits for test.
Input: (['a', 'b', 'c'], [['a', 'b'], ['b', 'c'], ['c', 'b']])
Expected Output: []
Explanation: Source example 2: b and c wait for each other, so no complete order exists even though a could be done.
Hints
- A task can be placed only after every task it waits for has been placed. At any moment, which tasks are allowed to go next?
- Two orders are compared at the first position where they differ. What does that say about the best choice for the very next position, given what has already been placed?
- If tasks remain but none of them is allowed to go next, what does that tell you about the dependencies?