Topological Task Dependency Graph | Dataford Interview Questions

Build a dependency graph for tasks (3-part OA; each part builds on the previous) - adjacency list + topological sort, with regular-expression/glob matching in the final part.

Asked in the Online assessment stage. Implement the combined function below. tasks is a list of unique task names. dependencies[task] lists prerequisite names or Unix glob patterns such as raw_*. Return [adjacency, order], where edges point from each prerequisite to the task that depends on it. Return an empty order if the graph contains a cycle.

Constraints

1 <= len(tasks) <= 10^4
Task names are unique, non-empty strings
Each dependency token is an exact task name or a valid Unix glob pattern
Every dependency token matches at least one task
A task does not depend on itself

Function Signature

def build_task_plan(tasks, dependencies):

Your question is Topological Task Dependency Graph. Start with the requirements in the Question tab.

Run and submit as often as you like. When you're ready, talk me through your approach or go straight to the code.

Problem

Build a dependency graph for tasks (3-part OA; each part builds on the previous) - adjacency list + topological sort, with regular-expression/glob matching in the final part.

Constraints

1 <= len(tasks) <= 10^4
Task names are unique, non-empty strings
Each dependency token is an exact task name or a valid Unix glob pattern
Every dependency token matches at least one task
A task does not depend on itself

Function Signature

def build_task_plan(tasks, dependencies):

Your question is Topological Task Dependency Graph. Start with the requirements in the Question tab.

Run and submit as often as you like. When you're ready, talk me through your approach or go straight to the code.