Snowflake·Data Scientist·Technical Phone Screen·Senior

SeniorPrefer not to say

May 2026Remote

Summary

Snowflake Data Scientist interview with a pretty deep algorithms question that felt more like a software engineering screen than anything data-related. One question, lots of moving parts, and they wanted both a recursive and iterative solution plus a full explanation of design choices.

Questions Asked (1)

Implement both a recursive and an iterative DFS on a directed graph that returns a topological order if the graph is a DAG, or detects and returns a cycle if not. Must also track discovery and finish timestamps for every node, handle disconnected graphs, self-loops, and parallel edges, all in O(N+M) time and space. Output as a dict with keys for is_dag, topo_order, cycle, discover, and finish.

Algorithms & Data StructuresTechnical Trade-offsSystem Design

Author's notes

This was a lot.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Start by clarifying the requirements and edge cases, then outline the recursive DFS with color marking (white/gray/black) to detect cycles and record timestamps, followed by an iterative version using an explicit stack that simulates the recursion. Emphasize that both must handle disconnected graphs by iterating over all nodes, and that parallel edges and self-loops are naturally handled by the adjacency list and color checks. Conclude by discussing time/space complexity and how the output dictionary is populated.

Pro tip: Mention that the iterative DFS must carefully manage the stack to replicate the exact discovery/finish order of recursion, and that using a stack of iterators or a state flag is key to avoiding subtle bugs. Also note that for a data science role at Snowflake, you might relate topological sorting to dependency resolution in data pipelines or query planning.

1. Clarify requirements and edge cases

Restate the problem: implement both recursive and iterative DFS to return topological order or cycle, with timestamps, handling disconnected graphs, self-loops, and parallel edges in O(N+M). Ask if any constraints (e.g., recursion depth) or output format details need clarification.

2. Design recursive DFS

Use color marking (white=unvisited, gray=in-progress, black=done) to detect cycles. Maintain global time, record discovery when first visiting a node and finish when all descendants are processed. For DAG, append node to topological order after finishing (post-order).

3. Design iterative DFS

Use an explicit stack to simulate recursion. Push nodes with a state flag (e.g., (node, processed)) or use an iterator stack. Ensure discovery/finish timestamps match recursive behavior. Detect cycles when encountering a gray node.

4. Handle disconnected graphs and edge cases

Loop over all nodes; if unvisited, start DFS. Self-loops are detected when a node points to itself (gray). Parallel edges are handled by adjacency list; they don't affect correctness but may increase M.

5. Assemble output and analyze complexity

Populate the result dict: is_dag, topo_order (if DAG), cycle (if not), discover and finish arrays. Explain O(N+M) time and space, noting that recursion may use O(N) stack space.

Key Points to Mention

Color marking (white/gray/black) for cycle detection and timestamp recording.
Post-order insertion for topological sort in DAG.
Iterative DFS using explicit stack with state to mimic recursion.
Handling disconnected components by iterating over all nodes.
Self-loops and parallel edges are naturally handled by adjacency list and color checks.
Time and space complexity: O(N+M) for both approaches, with recursion stack space O(N).

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