Quick Overview

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.

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.

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. A valid ordering must include every task exactly once.

Constraints

  • 0 <= n <= 10^5
  • 0 <= len(dependencies) <= 2 * 10^5
  • Each dependency is a pair [a, b] such that 0 <= a, b < n

Examples

Input: (4, [[1,0],[2,0],[3,1],[3,2]])

Expected Output: [0, 1, 2, 3]

Explanation: Task 0 must come before 1 and 2, and both 1 and 2 must come before 3. The reference solution processes available tasks in queue order and returns [0, 1, 2, 3].

Input: (5, [[1,0],[2,0],[4,3]])

Expected Output: [0, 3, 1, 2, 4]

Explanation: Tasks 0 and 3 have no prerequisites initially. Processing them in order yields [0, 3, 1, 2, 4], which satisfies all dependencies.

Hints

  1. Think about representing the tasks as a directed graph and tracking how many prerequisites each task still has.
  2. Start with every task that has no remaining prerequisites, process it, and update the tasks that depend on it.

Loading coding console...