This was the first-round phone screen at Vanta. It was 60 minutes of pure coding, and you have to actually run your code and get results.
part 1
Given some tasks, each with a list of the tasks it depends on, and given a list of tasks, output all the tasks that need to be executed, in the correct order.
For example, task1 depends on task2 and task3, and task1 depends on task3. Given task1, you need to output [task3, task2, task1] in order. You can assume there are no cycles.
At first I wanted to do it with BFS, but when I walked through it I saw it could not output the correct order, so I switched to DFS.
part 2
Now each task also comes with a set of files, and the question is: given some changed files, which tasks need to be rerun?
You need to build a reversed adjacency list, from each task to the tasks that depend on it, plus a map from each file to the tasks that depend on that file, and then reuse the DFS solution from the previous part. BFS would actually work for this one too, but to save time I just used the DFS function from above.
Discussion
Loading comments…