Task Order with Smallest Ready Task First
Updated
Problem statement
You have n tasks numbered from 0 to n - 1 and a list of rules edges. A rule [a, b] means task a must be done before task b. The rules never form a cycle, so all tasks can be done.
Return an order of all n tasks that follows every rule. A task is ready when every task it must wait for is already in the order. Whenever more than one task is ready, take the ready task with the smallest number first. With this tie rule there is exactly one correct answer.
Function
topologicalOrder(n: int, edges: int[][]) → int[]Examples
Example 1
n = 5edges = [[3,1],[1,0],[4,2]]return = [3,1,0,4,2]At the start, tasks 3 and 4 have no prerequisites, so we take 3, the smaller. Now task 1 is ready too; the ready tasks are 1 and 4, so we take 1. That makes task 0 ready; the ready tasks are 0 and 4, so we take 0. Then 4, and finally 2, which waited for 4.
Example 2
n = 3edges = []return = [0,1,2]There are no rules, so every task is ready from the start and we take them from smallest to largest.
Example 3
n = 4edges = [[2,0],[2,1],[3,0]]return = [2,1,3,0]Tasks 2 and 3 are ready, so we take 2. That frees task 1 (task 0 still waits for 3), so the ready tasks are 1 and 3, and we take 1. Then 3, which frees 0. A plain first-in, first-out queue would give [2, 3, 1, 0], which follows the rules but takes 3 while the smaller task 1 is ready.
Constraints
1 <= n <= 20000 <= edges.length <= 5000edges[i].length == 2- For every rule
[a, b]:0 <= a, b < nanda != b. - No rule appears twice.
- The rules never form a cycle.
More Expedia Onsite Interview questions
- Scramble StringONSITE INTERVIEW · Seen Sep 2026
- Smallest Sufficient TeamONSITE INTERVIEW · Seen Sep 2026
- Check Anagram Pairs Index by IndexONSITE INTERVIEW · Seen Oct 2025
- Fresh Oranges Left After Rotting StopsONSITE INTERVIEW · Seen Oct 2025
- Longest Increasing SubsequenceONSITE INTERVIEW · Seen Oct 2025
- Lowest Common Ancestor with Repeated and Missing ValuesONSITE INTERVIEW · Seen Oct 2025
- Shortest Substring with Exactly K OnesONSITE INTERVIEW · Seen Oct 2025
- Middle Element of a Linked ListONSITE INTERVIEW · Seen Nov 2024
- Minimum in a Rotated Sorted ArrayONSITE INTERVIEW · Seen Sep 2024
- Mirror Image Binary TreesONSITE INTERVIEW · Seen Sep 2024
Similar questions at other companies
- Course Schedule IIAmazon · PHONE SCREEN · ONSITE INTERVIEW
- 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
- Lexicographically Smallest Course OrderLinkedIn · ONSITE INTERVIEWLinkedIn interview questions
- ETL Pipeline SchedulerUnity · ONSITE INTERVIEW
- Microservice Deployment OrderGoldman Sachs · ONSITE INTERVIEWGoldman Sachs interview questions
- Course Schedule IIWalmart · ONSITE INTERVIEWWalmart interview questions
- Task Order With PrerequisitesDoorDash · PHONE SCREEN · ONSITE INTERVIEWDoorDash interview questions
- Course Schedule IIBloomberg LP · ONSITE INTERVIEWBloomberg LP interview questions
Expedia interview experiences
- Expedia Intern Final Round in 2021: 28 Experiences (Part 4 of 6)
- Expedia Intern Finals Before 2020: 14 Experiences (Part 6 of 6)
- Expedia Intern Final Round in 2020: 24 Experiences (Part 5 of 6)
- Expedia Intern Final Round in 2022: 15 Experiences (Part 3 of 6)
- Expedia Intern Final Round in 2023: 17 Experiences (Part 2 of 6)
- Expedia SWE Intern Final Round: 126 Experiences (Part 1 of 6)