Implement a DAG task graph
Company: Notion
Role: Data Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
Implement a class `TaskGraph` to represent a directed acyclic graph of tasks.
Support these operations:
1. `add_task(task_id: str) -> None`: Add a task if it does not already exist.
2. `add_dependency(before: str, after: str) -> None`: Add a directed edge `before -> after`, meaning `before` must run before `after`. Assume valid input will not introduce a cycle.
3. `get_execution_order() -> list[str]`: Return any valid topological ordering of all tasks. If there are multiple valid answers, any one is acceptable.
Also write a few simple test cases to validate your implementation.
Follow-up discussion:
- How would you detect and reject a cycle when adding an edge?
- How would you handle duplicate edges and isolated nodes?
- What are the time and space complexities of your approach?
Quick Answer: This question evaluates competency with directed acyclic graphs, graph algorithms (topological sorting), dependency modeling, and implementing data structures to represent task graphs.
Implement a task graph for a directed acyclic graph (DAG) of tasks. Since this platform evaluates a single function, you will receive a list of operations that should be applied to an internal `TaskGraph`.
Each operation is one of:
- `("add_task", task_id)`
- `("add_dependency", before, after)` meaning `before -> after`
- `("get_execution_order",)`
Rules:
- `add_task` adds the task only if it does not already exist.
- `add_dependency` adds a directed edge. Duplicate edges should be ignored.
- Isolated tasks must still appear in the execution order.
- Input is guaranteed not to introduce a cycle.
For this problem, return the result of every `get_execution_order` call in order. To make the output deterministic for testing, if multiple tasks are ready at the same time, always choose the lexicographically smallest task ID first.
Follow-up discussion: How would you detect and reject a cycle when adding an edge? How would you handle duplicate edges and isolated nodes? What are the time and space complexities of your approach?
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.