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 Onsite rounds at Netflix.

What role is this question designed for?

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

Return valid task order from prerequisites

Company: Netflix

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Onsite

You are given **N** tasks labeled `0..N-1` and a list of directed dependency pairs `[(a,b), ...]` meaning **task `a` must be done before task `b`**. 1) Return **one valid execution order** of all tasks that satisfies all dependencies. 2) If it is **impossible** (the graph has a cycle), return an empty list. Follow-ups that may be asked: - If multiple valid orders exist, return the **lexicographically smallest** order. - Return **all** valid topological orders (if feasible for the input size). - State the **time and space complexity** of your approach. Constraints can be assumed typical for interview settings (e.g., up to 1e5 nodes/edges for part 1; much smaller for “all orders”).

Quick Answer: This question evaluates proficiency in graph algorithms, notably topological sorting and cycle detection, as well as algorithmic complexity analysis and handling of dependency constraints.

Part 1: Return one valid execution order of all tasks

You are given n tasks labeled 0 to n-1 and a list of dependency pairs (a, b), meaning task a must be completed before task b. For this problem, you may assume the dependency graph is acyclic. Return any valid execution order that includes every task exactly once and satisfies all dependencies. If n is 0, return an empty list.

Constraints

0 <= n <= 100000
0 <= len(dependencies) <= 200000
0 <= a, b < n for every dependency (a, b)
All dependency pairs are distinct
The dependency graph is guaranteed to be acyclic for this part

Examples

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

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

Explanation: There is only one valid order because each task depends on the previous one.

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

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

Explanation: Tasks 0 and 1 can swap places, but both must appear before 2, and 2 must appear before 3. This is one valid answer.

Input: (3, [])

Expected Output: [0, 1, 2]

Explanation: With no dependencies, any permutation is valid. This is one valid answer.

Input: (0, [])

Expected Output: []

Explanation: There are no tasks to schedule.

Hints

Count how many prerequisites each task has.
Start with every task whose prerequisite count is 0, and remove tasks layer by layer.

Part 2: Return an empty list if the dependency graph contains a cycle

You are given n tasks labeled 0 to n-1 and a list of dependency pairs (a, b), meaning task a must be completed before task b. Return one valid execution order of all tasks if such an order exists. If the dependency graph contains a cycle, it is impossible to finish every task, so return an empty list.

Constraints

0 <= n <= 100000
0 <= len(dependencies) <= 200000
0 <= a, b < n for every dependency (a, b)
All dependency pairs are distinct

Examples

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

Expected Output: [0, 1, 2]

Explanation: This graph is acyclic, so a full ordering exists.

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

Expected Output: []

Explanation: The dependencies form a cycle, so no valid ordering exists.

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

Expected Output: []

Explanation: A self-loop is also a cycle.

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

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

Explanation: The graph has two independent chains. This is one valid ordering.

Input: (0, [])

Expected Output: []

Explanation: There are no tasks, so the valid order is empty.

Hints

A topological ordering exists only if you can repeatedly remove a task with indegree 0.
After processing, compare how many tasks you placed in the order versus n.

Part 3: Return the lexicographically smallest valid execution order

You are given n tasks labeled 0 to n-1 and a list of dependency pairs (a, b), meaning task a must be completed before task b. Return the lexicographically smallest valid execution order among all possible topological orders. If the graph contains a cycle, return an empty list.

Constraints

0 <= n <= 100000
0 <= len(dependencies) <= 200000
0 <= a, b < n for every dependency (a, b)
All dependency pairs are distinct

Examples

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

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

Explanation: Initially tasks 0, 1, and 3 are available. Choosing the smallest available task each time gives the lexicographically smallest order.

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

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

Explanation: This is the smallest order that respects all three dependencies.

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

Expected Output: []

Explanation: The graph contains a cycle.

Input: (0, [])

Expected Output: []

Explanation: There are no tasks to schedule.

Input: (4, [])

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

Explanation: With no dependencies, the lexicographically smallest permutation is the sorted order.

Hints

When several tasks are ready at the same time, always choose the smallest label first.
A min-heap is a good way to repeatedly extract the smallest available task.

Part 4: Return all valid topological orders

You are given n tasks labeled 0 to n-1 and a list of dependency pairs (a, b), meaning task a must be completed before task b. Return all valid execution orders of the tasks. Because the number of valid orders can be exponential, assume n is small. Return the list of orders in lexicographic order. If the graph contains a cycle, return an empty list. If n is 0, return [[]], since there is exactly one ordering of zero tasks.

Constraints

0 <= n <= 10
0 <= len(dependencies) <= n * (n - 1) / 2
0 <= a, b < n for every dependency (a, b)
All dependency pairs are distinct

Examples

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

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

Explanation: Task 2 must be last. Tasks 0 and 1 can appear in either order.

Input: (3, [])

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

Explanation: With no dependencies, every permutation is valid.

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

Expected Output: []

Explanation: A cycle means there are no valid topological orders.

Input: (0, [])

Expected Output: [[]]

Explanation: There is exactly one ordering of zero tasks: the empty ordering.

Input: (1, [])

Expected Output: [[0]]

Explanation: A single task has exactly one valid order.

Hints

Use backtracking: at each step, try every currently available task with indegree 0.
After exploring one choice, undo the indegree updates before trying the next choice.

Quick Overview

This question evaluates proficiency in graph algorithms, notably topological sorting and cycle detection, as well as algorithmic complexity analysis and handling of dependency constraints.