Task Dependency Ordering
Learn this problem
CitadelFULLTIMEPHONE SCREENProblem statement
You are given two parallel arrays that serialize a task-to-prerequisites map:
tasks[i]is a unique task identifier.prerequisites[i]contains the direct prerequisites oftasks[i].
Return a topological order containing every task exactly once, with every prerequisite before the task that depends on it.
Use a stable first-in, first-out ready queue. Add initially ready tasks in their order in tasks. After processing a task, examine its dependents in tasks order and append each dependent when its final prerequisite has been processed.
If the dependency graph contains a cycle, return an empty array. Therefore, the workflow can be completed exactly when the returned array has the same length as tasks.
Function
findTaskOrder(tasks: String[], prerequisites: String[][]) → String[]Examples
Example 1
tasks = ["Task0","Task2","Task1","Task3"]prerequisites = [[],["Task0"],["Task0"],["Task0","Task1","Task2"]]return = ["Task0","Task2","Task1","Task3"]Task0 is initially ready. Processing it makes Task2 and Task1 ready in input order. Task3 becomes ready only after both have been processed.
The order ["Task0","Task1","Task3","Task2"] is invalid because it places Task3 before its prerequisite Task2.
Example 2
tasks = ["A","B","C"]prerequisites = [["C"],["A"],["B"]]return = []The dependencies form the cycle A -> B -> C -> A, so no complete topological order exists.
Constraints
1 <= tasks.length <= 10^5.prerequisites.length == tasks.length.- Every task identifier is non-empty and appears exactly once in
tasks. - Every prerequisite names a task in
tasks. - Each prerequisite appears at most once for a given task.
- The total number of prerequisite entries is at most
2 * 10^5.