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 Technical Screen rounds at Adobe.

What role is this question designed for?

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

Determine task order with prerequisites

Company: Adobe

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: Medium

Interview Round: Technical Screen

You are given n tasks labeled 0..n−1 and a list of prerequisite pairs (a, b) meaning task b must be completed before task a. Determine one valid order in which to complete all tasks, or report that it is impossible if dependencies contain a cycle. Describe the algorithm, data structures, and complexity, and explain how you would detect cycles and handle multiple valid orders.

Quick Answer: This question evaluates a candidate's proficiency with graph-theoretic concepts like dependency modeling and cycle detection, and their ability to produce valid task orderings under constraints within the Coding & Algorithms domain.

You are given an integer `n` representing tasks labeled `0` to `n-1`, and a list of prerequisite pairs `prerequisites` where each pair `[a, b]` means task `b` must be completed before task `a`. Return one valid order in which all tasks can be completed. If the dependencies contain a cycle (making a valid ordering impossible), return an empty list. This is a topological sort. When multiple valid orderings exist, return the one that is lexicographically smallest (always pick the smallest-labeled task among those whose prerequisites are all satisfied), so the answer is deterministic. Example: - `n = 4`, `prerequisites = [[1,0],[2,0],[3,1],[3,2]]` -> `[0, 1, 2, 3]` (task 0 first, then 1 and 2, then 3). - `n = 2`, `prerequisites = [[0,1],[1,0]]` -> `[]` (cycle: 0 needs 1 and 1 needs 0).

Constraints

0 <= n <= 10^5
0 <= prerequisites.length <= 10^5
prerequisites[i] = [a, b] with 0 <= a, b < n
A pair [a, b] means b must be completed before a
Return [] if the prerequisite graph contains a cycle

Examples

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

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

Explanation: Task 0 has no prerequisites, so it goes first. Tasks 1 and 2 both depend only on 0; the smaller label 1 comes before 2. Task 3 depends on both 1 and 2, so it goes last.

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

Expected Output: [0, 1]

Explanation: Task 1 requires task 0 first, giving the single valid order [0, 1].

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

Expected Output: []

Explanation: Task 0 needs 1 and task 1 needs 0 — a 2-node cycle, so no valid ordering exists.

Input: (1, [])

Expected Output: [0]

Explanation: A single task with no prerequisites is its own order.

Input: (0, [])

Expected Output: []

Explanation: Zero tasks: the empty order is the (trivially) valid answer.

Input: (3, [])

Expected Output: [0, 1, 2]

Explanation: No prerequisites means every task is immediately available; the min-heap emits them in ascending label order.

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

Expected Output: []

Explanation: Edges form the cycle 0 -> ... -> 0 (0 needs 1, 1 needs 2, 2 needs 0), so ordering is impossible.

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

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

Explanation: A linear dependency chain forces the unique order 0,1,2,3,4.

Hints

Model tasks as nodes in a directed graph. For each pair [a, b], task b must come before a, so add a directed edge b -> a and increment the in-degree of a.
Use Kahn's algorithm (BFS topological sort): repeatedly take a task whose in-degree is 0, append it to the order, and decrement the in-degree of its dependents, adding any that reach 0.
A cycle exists exactly when you cannot place all n tasks (the final order has fewer than n elements). In that case return an empty list.
To make the result deterministic among multiple valid orderings, pick the smallest available task each step using a min-heap (priority queue) instead of a plain queue.

Quick Overview

This question evaluates a candidate's proficiency with graph-theoretic concepts like dependency modeling and cycle detection, and their ability to produce valid task orderings under constraints within the Coding & Algorithms domain.