Task Dependency Execution Order and Rerunning Tasks After File Changes

Quick Overview

A two-part coding question on task dependencies: return every task needed by a set of requested tasks in a valid execution order, then use the files each task reads to find which tasks must rerun after some files change. It tests graph traversal direction, ordering dependencies before dependents and linear-time solutions.

Task Dependency Execution Order and Rerunning Tasks After File Changes

Company: Vanta

Role: Software Engineer

Category: Software Engineering Fundamentals

Difficulty: medium

Interview Round: Technical Screen

You are given a set of tasks. Each task has a list of the tasks it depends on, and a task can run only after every task it depends on has run. The screen was an hour of pure coding, and the code had to run and produce correct results. Both parts use the same input format: ```python dependencies = { "task1": ["task2", "task3"], "task2": ["task3"], "task3": [], } ``` A task that does not appear as a key has no dependencies. You may assume the dependencies contain no cycles. ### Clarifying Questions - Should each task appear only once in the output, even when several requested tasks share it? - When several orders are valid, is any of them accepted, or is a particular order expected? - Can a dependency name a task that has no entry of its own, and should it then be treated as a task with no dependencies? - The prompt says to assume there are no cycles. Should the code still detect one rather than recurse forever or return a wrong order? - How large can the graph be, and can a dependency chain be deep enough to hit a recursion limit? ### Part 1 — Execution order for the requested tasks Given `dependencies` and a list of requested tasks, return every task that must run (the requested tasks and everything they depend on, directly or indirectly) in an order in which each task comes after all of its dependencies. ```python def execution_order(dependencies: dict[str, list[str]], requested: list[str]) -> list[str]: ``` For example, with the mapping above, `execution_order(dependencies, ["task1"])` returns `["task3", "task2", "task1"]`: both other tasks need task3, and task1 needs task2. ```hint Test the walk by hand Run a breadth-first walk on a graph where one task is reached both directly and through a longer chain, and see where its order goes wrong. Then ask what must already be in the output before a task may be appended to it. ``` #### What This Part Should Cover - Restricting the output to tasks reachable from the requested ones, each listed once - A traversal that places every task after all of its dependencies, and why a plain breadth-first order does not - Running time linear in the tasks and dependency edges visited, and behavior on deep chains ### Part 2 — Tasks to rerun after files change Each task now also lists the files it uses. Given a list of changed files, return the tasks that need to rerun: a task reruns if it uses a changed file, or if it depends, directly or indirectly, on a task that reruns. ```python def tasks_to_rerun(dependencies: dict[str, list[str]], files: dict[str, list[str]], changed_files: list[str]) -> list[str]: ``` For example: ```python dependencies = {"task1": ["task2", "task3"], "task2": ["task3"], "task3": [], "task4": ["task3"]} files = {"task1": ["main.py"], "task2": ["util.py"], "task3": ["config.yaml"], "task4": ["util.py", "report.py"]} ``` If `util.py` changes, task2 and task4 use it and task1 depends on task2, so task1, task2 and task4 rerun while task3 does not. If `config.yaml` changes, all four tasks rerun. ```hint Which way a change travels The dependency lists point from a task to what it needs, but a change spreads the other way. Think about which lookups you would build once before walking. ``` #### Clarifying Questions for this Part - Should the tasks to rerun come back in an order in which they can run, or is the set enough? - Can one file be used by several tasks, and can a changed file be used by no task at all? #### What This Part Should Cover - Reverse lookups from a task to the tasks that depend on it and from a file to the tasks that use it - Propagating a change to every direct and indirect dependent exactly once - Reusing the Part 1 ordering when the reruns must come back in runnable order ### What a Strong Answer Covers - Runnable code for both parts, checked against the examples - The correct edge direction in each part - Each task visited and output once, in time linear in the part of the graph touched - Tasks with no entry, shared dependencies, empty inputs and deep chains handled - A clear choice about what happens if the no-cycle assumption is broken ### Follow-up Questions - If cycles were possible, how would you report one, naming the tasks involved? - Tasks that do not depend on each other could run at the same time. How would you group the Part 1 output into stages that can run in parallel? - Part 2 is called after every commit on a large graph. What would you precompute so each call is fast? - A rerun task produced exactly the same output as before. How could you avoid rerunning the tasks that depend on it?

Overview: A two-part coding question on task dependencies: return every task needed by a set of requested tasks in a valid execution order, then use the files each task reads to find which tasks must rerun after some files change. It tests graph traversal direction, ordering dependencies before dependents and linear-time solutions.

Read the full Vanta Software Engineer interview experience this question came from

Vanta logo
Vanta
Nov 10, 2026
mediumSoftware EngineerTechnical ScreenSoftware Engineering Fundamentals
0
0

You are given a set of tasks. Each task has a list of the tasks it depends on, and a task can run only after every task it depends on has run. The screen was an hour of pure coding, and the code had to run and produce correct results. Both parts use the same input format:

dependencies = {
    "task1": ["task2", "task3"],
    "task2": ["task3"],
    "task3": [],
}

A task that does not appear as a key has no dependencies. You may assume the dependencies contain no cycles.

Clarifying Questions Guidance

  • Should each task appear only once in the output, even when several requested tasks share it?
  • When several orders are valid, is any of them accepted, or is a particular order expected?
  • Can a dependency name a task that has no entry of its own, and should it then be treated as a task with no dependencies?
  • The prompt says to assume there are no cycles. Should the code still detect one rather than recurse forever or return a wrong order?
  • How large can the graph be, and can a dependency chain be deep enough to hit a recursion limit?

Part 1 — Execution order for the requested tasks

Given dependencies and a list of requested tasks, return every task that must run (the requested tasks and everything they depend on, directly or indirectly) in an order in which each task comes after all of its dependencies.

def execution_order(dependencies: dict[str, list[str]], requested: list[str]) -> list[str]:

For example, with the mapping above, execution_order(dependencies, ["task1"]) returns ["task3", "task2", "task1"]: both other tasks need task3, and task1 needs task2.

What This Part Should Cover Guidance

  • Restricting the output to tasks reachable from the requested ones, each listed once
  • A traversal that places every task after all of its dependencies, and why a plain breadth-first order does not
  • Running time linear in the tasks and dependency edges visited, and behavior on deep chains

Part 2 — Tasks to rerun after files change

Each task now also lists the files it uses. Given a list of changed files, return the tasks that need to rerun: a task reruns if it uses a changed file, or if it depends, directly or indirectly, on a task that reruns.

def tasks_to_rerun(dependencies: dict[str, list[str]], files: dict[str, list[str]],
                   changed_files: list[str]) -> list[str]:

For example:

dependencies = {"task1": ["task2", "task3"], "task2": ["task3"], "task3": [], "task4": ["task3"]}
files = {"task1": ["main.py"], "task2": ["util.py"], "task3": ["config.yaml"],
         "task4": ["util.py", "report.py"]}

If util.py changes, task2 and task4 use it and task1 depends on task2, so task1, task2 and task4 rerun while task3 does not. If config.yaml changes, all four tasks rerun.

Clarifying Questions for this Part Guidance

  • Should the tasks to rerun come back in an order in which they can run, or is the set enough?
  • Can one file be used by several tasks, and can a changed file be used by no task at all?

What This Part Should Cover Guidance

  • Reverse lookups from a task to the tasks that depend on it and from a file to the tasks that use it
  • Propagating a change to every direct and indirect dependent exactly once
  • Reusing the Part 1 ordering when the reruns must come back in runnable order

What a Strong Answer Covers Guidance

  • Runnable code for both parts, checked against the examples
  • The correct edge direction in each part
  • Each task visited and output once, in time linear in the part of the graph touched
  • Tasks with no entry, shared dependencies, empty inputs and deep chains handled
  • A clear choice about what happens if the no-cycle assumption is broken

Follow-up Questions Guidance

  • If cycles were possible, how would you report one, naming the tasks involved?
  • Tasks that do not depend on each other could run at the same time. How would you group the Part 1 output into stages that can run in parallel?
  • Part 2 is called after every commit on a large graph. What would you precompute so each call is fast?
  • A rerun task produced exactly the same output as before. How could you avoid rerunning the tasks that depend on it?