Return valid task order from prerequisites

Q: Return valid task order from prerequisites

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

Q: How do I approach Coding & Algorithms interview questions?

Coding & Algorithms questions require understanding of core concepts and practice. PracHub provides solutions with explanations to help you master coding & algorithms interviews.

Question

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.

Return one valid execution order of all tasks that satisfies all dependencies.
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”).

Return valid task order from prerequisites

Quick Overview

Comments (0)