How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a medium difficulty Coding & Algorithms question, commonly asked during Onsite rounds at Notion.

What role is this question designed for?

This question is commonly asked for Data Engineer candidates at Notion during technical interviews.

Implement a DAG task graph | Notion Coding Question

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.

Input: [("add_task", "b"), ("add_task", "a"), ("add_task", "c"), ("add_dependency", "a", "c"), ("get_execution_order",)]

Expected Output: [['a', 'b', 'c']]

Explanation: Tasks `a` and `b` are both initially ready. Lexicographic tie-breaking chooses `a` first, then `b`, then `c`.

Input: [("add_task", "a"), ("add_task", "a"), ("add_task", "b"), ("add_dependency", "a", "b"), ("add_dependency", "a", "b"), ("get_execution_order",), ("add_task", "c"), ("get_execution_order",)]

Expected Output: [['a', 'b'], ['a', 'b', 'c']]

Explanation: Duplicate task and duplicate edge do nothing. After adding isolated task `c`, it is included in the next execution order.

Input: [("get_execution_order",)]

Expected Output: [[]]

Explanation: An empty graph has an empty valid execution order.

Input: []

Expected Output: []

Explanation: If there are no operations, there are no execution-order queries to answer.

Hints

A topological ordering can be built using Kahn's algorithm by tracking the indegree of each task.
Use a min-heap (priority queue) for currently available tasks so the returned order is deterministic and lexicographically smallest.

Quick Overview

This question evaluates competency with directed acyclic graphs, graph algorithms (topological sorting), dependency modeling, and implementing data structures to represent task graphs.