FastPrepTask Build Order and File-Change Reruns

Task Build Order and File-Change Reruns

Vanta logoVanta● MediumFULLTIMEPHONE SCREEN

Updated

Problem statement

A build system has n tasks. Task tasks[i] can run only after every task listed in dependencies[i] has run, and it reads the files listed in files[i]. There are no circular dependencies.

Part 1: build order. Given the task names in targets, list every task that must run so that all targets can run, each exactly once, in an order where each task comes after all of its prerequisites. Use this rule so that the answer is unique: process the targets in the given order; to visit a task that is not yet listed, first visit each of its prerequisites in the order they appear in dependencies[i], then append the task.

Part 2: reruns. Some files changed; their names are in changedFiles. A task must rerun if it reads a changed file, or if any of its prerequisites must rerun. List all such tasks, across all n tasks and not only the targets' tasks, in the full order: the order Part 1's rule produces when every task is a target, taken in the order of tasks.

Return [buildOrder, reruns].

Function

planTasks(tasks: String[], dependencies: String[][], files: String[][], targets: String[], changedFiles: String[]) → List<List<String>>

Examples

Example 1

tasks = ["task1","task2","task3"]dependencies = [["task2","task3"],["task3"],[]]files = [["main.py"],["lib.py"],["config.yml"]]targets = ["task1"]changedFiles = ["lib.py"]return = [["task3","task2","task1"],["task2","task1"]]
  • Part 1: task1 needs task2 and task3, and task2 needs task3. Visiting task2 first adds task3, then task2; task3 is already added, so task1 comes last: ["task3", "task2", "task1"].
  • Part 2: only task2 reads lib.py, and task1 depends on task2, so both rerun. task3 does not.

Example 2

tasks = ["lint","compile","test","package","docs"]dependencies = [[],["lint"],["compile"],["compile","test"],[]]files = [["src/a.ts",".eslintrc"],["src/a.ts","src/b.ts"],["test/a.spec.ts"],["package.json"],["readme.md"]]targets = ["test","docs"]changedFiles = [".eslintrc","notes.txt"]return = [["lint","compile","test","docs"],["lint","compile","test","package"]]
  • Part 1: test needs compile, which needs lint; docs has no prerequisites. package is not needed by any target, so it is not in the order.
  • Part 2: lint reads .eslintrc; compile, test and package depend on it directly or indirectly. No task reads notes.txt. The reruns are listed in the full-order rule: ["lint", "compile", "test", "package"].

Constraints

  • 1 <= n == tasks.length == dependencies.length == files.length <= 1000
  • Task names are distinct and match [a-z0-9_]{1,20}.
  • dependencies[i] lists distinct task names other than tasks[i]; the total number of listed dependencies is at most 5000, and the dependencies form no cycle.
  • 0 <= files[i].length <= 10; the names in one list are distinct.
  • 1 <= targets.length <= n; targets are distinct task names.
  • 0 <= changedFiles.length <= 2000; changed file names are distinct and may include files that no task reads.
  • File names match [a-z0-9_./-]{1,30}.

More Vanta interview questions

Similar questions at other companies

Interview reports that mention this question

See Vanta hiring insights
Saved
class Solution {
    public List<List<String>> planTasks(String[] tasks, String[][] dependencies, String[][] files, String[] targets, String[] changedFiles) {
        // Write your code here.
    }
}
Checking account…