Order Dependent Tasks and Identify Work to Rerun

Given tasks and their prerequisite relationships, return any valid execution order and detect circular dependencies. Then identify every task that must rerun after some tasks change, including indirectly affected tasks, and return those tasks in any valid order.

Constraints & Assumptions

• Use task_execution_orders(tasks, dependencies, changed) as a concrete practice interface. Tasks have unique nonempty names.
• Each dependency [task, prerequisite] means prerequisite must complete before task. All referenced names exist. Duplicate edges have no extra effect; a self-dependency is a cycle.
• Changed names are valid and may repeat. A changed task itself must rerun, as must every direct or indirect dependent.
• Unaffected prerequisites are assumed to have completed successfully and do not need to rerun.
• Return two lists: a valid order of all tasks, then a valid order of only the affected tasks. Multiple answers are accepted; there is no required alphabetical order or prescribed algorithm.
• If the full graph has a cycle, return an explicit cycle result instead of a partial successful order. The sample interface uses [["CYCLE"],[]] and reserves CYCLE from task names; another clear error representation can be agreed with the interviewer.
• For no tasks, return [[],[]]. Aim for time and space proportional to the graph size.

Example

tasks = ["build","test","package","docs"]
dependencies = [["test","build"],["package","test"]]
changed = ["test"]
one valid result = [["build","docs","test","package"],["test","package"]]

Placing docs at another position is also valid if build remains before test and test before package. The rerun list excludes build because its unchanged result is already available.

Clarifying Questions

Which direction does an edge encode? Must changed tasks themselves rerun? Are unaffected prerequisites already complete? Is any valid ordering acceptable? How should cycles be reported?