How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a medium difficulty Coding & Algorithms question, commonly asked during Take-home Project rounds at Amazon.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Amazon during technical interviews.

Find a valid dependency order | Amazon Coding Question

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.

medium
Amazon
Coding & Algorithms
Software Engineer

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.

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

Expected Output: []

Explanation: Task 0 depends on 1 and task 1 depends on 0, forming a cycle. No valid ordering exists.

Input: (3, [])

Expected Output: [0, 1, 2]

Explanation: There are no dependencies, so any ordering is valid. The reference solution returns tasks in increasing order.

Input: (0, [])

Expected Output: []

Explanation: With no tasks, the valid ordering is the empty list.

Loading coding console...

Quick Overview

Find a valid dependency order

Constraints

Examples

Hints