← Notion Interview Insights

Notion·Software Engineer·Technical Phone Screen·Intermediate

Intermediate
May 2026

Summary

Notion Data Engineer interview, first part of a three-part coding problem centered on building a DAG class from scratch. Pretty approachable as a standalone problem but they made clear there were more parts coming, so you can't just slap something together and call it done.

Questions Asked (1)

Q1

Implement a DAG class with at minimum add_node and add_edge methods, where add_edge must reject any edge that would introduce a cycle. What data structure do you use internally, and how does your cycle detection work on insert?

Algorithms & Data StructuresTechnical Trade-offsSystem Design
Author's notes

I went with an adjacency list and DFS-based cycle detection on every add_edge call.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Start by clarifying requirements and then propose an adjacency list representation with a topological ordering (e.g., Kahn's algorithm) to detect cycles on edge insertion. Explain that adding an edge (u, v) is safe only if u is not reachable from v; otherwise, it would create a cycle. Walk through the algorithm step-by-step, analyze time/space complexity, and discuss trade-offs with alternative approaches like DFS-based detection.

Pro tip: Mention that you can maintain a topological order incrementally and only recompute when necessary, or use a dynamic topological sort algorithm to achieve better than O(V+E) per edge in practice. This shows you think about performance beyond the naive solution.

1. Clarify requirements and constraints

Ask about expected graph size, frequency of operations, and whether nodes/edges can be removed. This determines the best data structure and algorithm.

2. Choose internal data structure

Propose an adjacency list (e.g., HashMap<Node, List<Node>>) for sparse graphs, and mention that you also maintain in-degree counts or a topological order for cycle detection.

3. Explain cycle detection on insert

Describe that before adding edge (u, v), you check if v can reach u. If yes, reject; otherwise, add the edge and update the topological order or in-degrees.

4. Detail the algorithm (e.g., Kahn's or DFS)

Walk through Kahn's algorithm: compute in-degrees, perform BFS, and if all nodes are visited, no cycle. For incremental, maintain a topological order and update it when adding edges.

5. Analyze complexity and trade-offs

State that naive cycle detection is O(V+E) per edge insertion. Discuss alternatives like dynamic topological sort (O(sqrt(V)) per edge) or DFS with coloring, and their trade-offs.

Key Points to Mention

  • Adjacency list representation for efficient edge storage and traversal.
  • Cycle detection using topological sorting (Kahn's algorithm) or DFS with recursion stack.
  • Incremental maintenance of topological order to avoid full recomputation.
  • Time complexity: O(V+E) per edge insertion for naive approach, and possible optimizations.
  • Handling of duplicate edges and self-loops (self-loop is a cycle).
  • Trade-offs between different data structures (e.g., adjacency matrix vs. list) based on graph density.

AI-generated suggestions, not part of the candidate's original notes. May be inaccurate — verify before relying on them.