Find a valid dependency order
Company: Amazon
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Take-home Project
You are given `n` tasks labeled from `0` to `n - 1` and a list of dependency pairs `dependencies`, where each pair `[a, b]` means task `b` must be completed before task `a`.
Return any valid ordering of all tasks that satisfies the dependencies. If no such ordering exists because the dependency graph contains a cycle, return an empty list.
Example:
- Input: `n = 4`, `dependencies = [[1,0],[2,0],[3,1],[3,2]]`
- Valid output: `[0,1,2,3]` or `[0,2,1,3]`
Discuss the time and space complexity of your approach.
Quick Answer: This question evaluates understanding of directed graphs, dependency resolution and cycle detection, and the ability to reason about valid ordering constraints within a graph representation.