Implement a DAG task graph
Company: Notion
Role: Data Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
Quick Answer: This question evaluates competency with directed acyclic graphs, graph algorithms (topological sorting), dependency modeling, and implementing data structures to represent task graphs.
Constraints
- 0 <= number of operations <= 10^4
- There are at most 10^4 distinct tasks
- Each task ID is a lowercase string of length 1 to 20
- Any `add_dependency` operation in the input keeps the graph acyclic
Examples
Input: [("add_task", "build"), ("add_task", "test"), ("add_task", "deploy"), ("add_dependency", "build", "test"), ("add_dependency", "test", "deploy"), ("get_execution_order",)]
Expected Output: [['build', 'test', 'deploy']]
Explanation: This is a simple chain: build must happen before test, and test before deploy.