← 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 foundational stuff but they go deep on the design choices afterward.

Questions Asked (1)

Q1

Implement a DAG class from scratch with at least add_node and add_edge methods, where add_edge must reject any edge that would introduce a cycle.

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

The core implementation felt manageable but I underestimated how much they'd dig into the cycle detection piece.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Start by clarifying requirements and constraints, then design the DAG with adjacency lists and a cycle detection mechanism. Implement add_node and add_edge with cycle rejection using DFS or topological sort, and discuss trade-offs and optimizations.

Pro tip: Mention that cycle detection can be optimized by maintaining in-degrees or using union-find for incremental checks, and discuss how to handle concurrent modifications if needed.

1. Clarify Requirements

Ask about expected operations, performance needs, and whether nodes/edges have additional data. Confirm that add_edge should reject cycles and discuss error handling.

2. Design Data Structures

Choose adjacency list representation for nodes and edges. Consider maintaining in-degree counts or a visited set for cycle detection.

3. Implement add_node

Add a node to the graph, initializing its adjacency list and any metadata. Ensure idempotency or handle duplicates as per requirements.

4. Implement add_edge with Cycle Check

Before adding an edge, check if it creates a cycle using DFS from the target node to see if it can reach the source. If no cycle, add the edge and update in-degrees.

5. Discuss Trade-offs and Optimizations

Compare DFS vs. topological sort for cycle detection, and mention incremental algorithms. Discuss time/space complexity and potential improvements.

Key Points to Mention

  • Adjacency list representation for efficient edge storage and traversal
  • Cycle detection using DFS with recursion stack or topological sort (Kahn's algorithm)
  • Time complexity: O(V+E) for cycle check per edge addition, which can be optimized
  • Handling of duplicate edges and self-loops (self-loop is a cycle)
  • Error handling: return false, throw exception, or log as per API design
  • Potential optimizations: maintain in-degrees, use union-find for incremental cycle detection

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