Order Dependent Tasks and Identify Work to Rerun

Company: Amazon

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Onsite

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 ```text 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? ### What a Strong Answer Covers A consistent graph representation, correct ordering and cycle detection, the transitive impact set, and an explanation of why the rerun order respects dependencies without waiting for unaffected prerequisites. ### Follow-up Questions How would you avoid revisiting shared dependents? How do duplicate edges affect indegrees? What changes if some unaffected tasks have not completed or if task definitions also alter the dependency graph? ```hint Reuse dependency information carefully Prerequisite-to-dependent edges tell you both which work becomes ready and which work may be invalidated by a change. Preserve that direction throughout the solution. ```

Overview: Return any valid dependency order, detect cycles, and identify transitive reruns with a complete topological and reachability solution and order-independent validation.

Community answers

Answer by janaki9sravya

def task_execution_orders(tasks, dependencies, changed): adjList = {} result =[] for t in tasks: adjList[t]=[] for dep in dependencies: adjList[dep[1]].append(dep[0]) states = {task:0 for task in tasks} #0 not visited, 1 in path , 2 completed def dfs(task): nonlocal result if states[task]==1: return False elif states[task]==2: return True states[task]=1 for t in adjList[task]: if not dfs(t): return False states[task]=2 result.append(task) return True for task in tasks: if len(adjList[task])>0: if not dfs(task): return [["CYCLE"],[]] for task in tasks: if states[task]==0: dfs(task) order = result[::-1] change_result =set() states = {task:0 for task in tasks} for c_task in set(changed): result =[] dfs(c_task) change_result.update(result) return [order,list(change_result)] tasks = ["build","test","package","docs"] dependencies = [["test","build"],["package","test"]] changed = ["test"] result = task_execution_orders(tasks, dependencies, changed) print(result)

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 Guidance

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?

What a Strong Answer Covers Guidance

A consistent graph representation, correct ordering and cycle detection, the transitive impact set, and an explanation of why the rerun order respects dependencies without waiting for unaffected prerequisites.

Follow-up Questions Guidance

How would you avoid revisiting shared dependents? How do duplicate edges affect indegrees? What changes if some unaffected tasks have not completed or if task definitions also alter the dependency graph?