Task Build Order and File-Change Reruns
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:
task1needstask2andtask3, andtask2needstask3. Visitingtask2first addstask3, thentask2;task3is already added, sotask1comes last:["task3", "task2", "task1"]. - Part 2: only
task2readslib.py, andtask1depends ontask2, so both rerun.task3does 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:
testneedscompile, which needslint;docshas no prerequisites.packageis not needed by any target, so it is not in the order. - Part 2:
lintreads.eslintrc;compile,testandpackagedepend on it directly or indirectly. No task readsnotes.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 thantasks[i]; the total number of listed dependencies is at most5000, 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
- All Halfway Courses Across Course TracksCrunchyroll · PHONE SCREENCrunchyroll interview questions
- Course ScheduleAmazon · PHONE SCREEN · ONSITE INTERVIEW
- Course Schedule Cycle DetectionGoogle · PHONE SCREEN · ONSITE INTERVIEWGoogle interview questions
- Resolve Variable Equations with Dependency ErrorsApplied Intuition · PHONE SCREENApplied Intuition interview questions
- Nested Substitutions with Cycle DetectionKikoff · PHONE SCREENKikoff interview questions
- Validate and Resolve Evaluation ChainsPlaid · PHONE SCREEN · ONSITE INTERVIEWPlaid interview questions
- Topological Sort with Secondary OrderingRoblox · PHONE SCREEN · ONSITE INTERVIEWRoblox interview questions
- Evaluate Formulas with Cycle DetectionInstacart · PHONE SCREEN · ONSITE INTERVIEWInstacart interview questions
- Route Graph Reachability with a Broken LinkFigma · PHONE SCREENFigma interview questions
- Root of the Largest TreeGoldman Sachs · PHONE SCREEN · ONSITE INTERVIEWGoldman Sachs interview questions