Lexicographic Dependency Order
Updated
Problem statement
You are given n tasks numbered from 0 to n - 1 and a directed dependency list dependencies. Each pair [u, v] requires task u to appear before task v.
Return the lexicographically smallest ordering containing every task exactly once and satisfying every dependency. Compare two orderings at their first differing position; the ordering with the smaller task number there is smaller. If no valid ordering exists because of a directed cycle, return an empty array.
Tasks without dependencies must still appear in the result. An empty dependency list allows all tasks in increasing order.
Function
dependencyOrder(n: int, dependencies: int[][]) → int[]Examples
Example 1
n = 4dependencies = [[0,2],[1,2],[1,3]]return = [0,1,2,3]Initially tasks 0 and 1 are available. Choosing the smallest available task at every step produces [0,1,2,3].
Example 2
n = 4dependencies = [[2,0],[2,1]]return = [2,0,1,3]Tasks 2 and 3 are initially available. After choosing 2, newly available tasks 0 and 1 come before 3.
Example 3
n = 3dependencies = [[0,1],[1,2],[2,0]]return = []The dependencies form a cycle, so no ordering can satisfy them all.
Constraints
1 <= n <= 10000.0 <= dependencies.length <= 20000.- Each dependency contains exactly two integers
uandv, with0 <= u, v < n. - All dependency pairs are distinct. A self-dependency is permitted and forms a cycle.
More Illumio interview questions
Similar questions at other companies
- Task Scheduler with Prerequisites and Execution PathsBrex · PHONE SCREEN
- Course Schedule IIAmazon · PHONE SCREEN · ONSITE INTERVIEW
- Dependency-Aware Task SchedulerRippling · PHONE SCREENRippling interview questions
- Lexicographically Smallest Topological OrderByteDance · PHONE SCREEN · ONSITE INTERVIEWByteDance interview questions
- Merge Subsequences Into a Consistent Total OrderGoogle · PHONE SCREEN · ONSITE INTERVIEWGoogle interview questions
- Topological Sort with Secondary OrderingRoblox · PHONE SCREEN · ONSITE INTERVIEWRoblox interview questions
- Order Sources by Their DependenciesRetool · PHONE SCREENRetool interview questions
- Dependency-Aware Agent Task SchedulerOpenAI · PHONE SCREENOpenAI interview questions
- Lexicographically Smallest Dependency OrderOkta · PHONE SCREENOkta interview questions
- Course Completion OrderIndeed · PHONE SCREENIndeed interview questions