Snapchat·Software Engineer·Technical Phone Screen·Intermediate

IntermediatePrefer not to say

May 2026Remote

Summary

Snapchat coding round, graph theory question that sounds easy until you realize they want you to know two separate algorithms cold. Not a vibe check, they actually wanted implementation details.

Questions Asked (1)

Given a directed graph representing task or course dependencies, return a valid topological ordering of all nodes. If a cycle exists, return an indication that no ordering is possible. Be prepared to walk through both a BFS approach using in-degree tracking and a DFS approach using post-order traversal.

Algorithms & Data Structures

Author's notes

I started with Kahn's algorithm because the queue-based approach feels more intuitive to explain out loud.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Start by clarifying the problem constraints and edge cases, then explain Kahn's algorithm (BFS with in-degree) and DFS with post-order, highlighting cycle detection. Walk through a small example for each, and discuss time/space complexity and trade-offs.

Pro tip: Emphasize that Kahn's algorithm naturally detects cycles when the result size is less than the number of nodes, while DFS uses a recursion stack to detect back edges. Mention that both are O(V+E) but BFS is often preferred for its simplicity and iterative nature.

1. Clarify requirements and edge cases

Ask about graph size, input format, and whether nodes are labeled 0 to n-1. Discuss edge cases like empty graph, single node, disconnected components, and self-loops.

2. Explain Kahn's algorithm (BFS)

Describe computing in-degrees, initializing a queue with zero in-degree nodes, and iteratively removing nodes and decrementing neighbors' in-degrees. If the result size is less than the number of nodes, a cycle exists.

3. Explain DFS with post-order

Describe performing DFS, tracking visited and recursion stack states, and adding nodes to the result in post-order. If a node is encountered in the recursion stack, a cycle exists.

4. Walk through examples

Choose a small DAG and a cyclic graph to demonstrate both approaches step-by-step, showing how cycle detection works.

5. Analyze complexity and trade-offs

State that both algorithms run in O(V+E) time and O(V+E) space. Compare BFS (iterative, easier to understand) vs DFS (recursive, may cause stack overflow for large graphs).

Key Points to Mention

Topological sort is only possible for Directed Acyclic Graphs (DAGs).
Kahn's algorithm uses in-degree tracking and a queue; if processed nodes < total nodes, a cycle exists.
DFS approach uses three states (unvisited, visiting, visited) to detect cycles via back edges.
Both algorithms have O(V+E) time complexity and O(V+E) space complexity.
For large graphs, iterative BFS avoids recursion depth issues.
Multiple valid topological orderings may exist; any valid one is acceptable.

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