Google·Software Engineer·Technical Phone Screen·Intermediate

Intermediate

Jun 2026

Summary

Google SWE coding round, 30 minutes, graph problem. The interviewer pushed me toward DFS even though Union-Find felt like the cleaner fit, which I wasn't fully ready for.

Questions Asked (1)

Solve a graph connectivity problem (e.g. detecting a redundant edge, counting connected components, or validating a tree structure) and walk through both Union-Find and DFS approaches including complexity and trade-offs.

Algorithms & Data StructuresTechnical Trade-offs

Author's notes

My instinct was Union-Find and I think it was the right call, but the interviewer kept nudging me toward DFS.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Start by clarifying the problem and choosing a concrete example, such as detecting a redundant edge in an undirected graph. Then explain both Union-Find and DFS approaches, including their time and space complexities, and discuss trade-offs based on graph size, density, and whether the graph is static or dynamic. Finally, walk through the code or pseudocode for one approach and mention how you would test it.

Pro tip: Demonstrate awareness of practical constraints: for example, Union-Find with path compression and union by rank is often preferred for dynamic connectivity, but DFS is simpler and more memory-efficient for static graphs. Also, mention that Google values clean, bug-free code and clear communication, so practice explaining your thought process while coding.

1. Clarify the problem and constraints

Ask clarifying questions to understand the graph type (directed/undirected), input size, and whether edges are added dynamically. Confirm the exact output required, such as returning the redundant edge or the number of connected components.

2. Outline Union-Find approach

Explain how Union-Find works: initialize each node as its own parent, then for each edge, check if the endpoints are in the same set; if so, the edge is redundant. Otherwise, union the sets. Mention optimizations like path compression and union by rank to achieve near O(1) amortized time per operation.

3. Outline DFS approach

Describe how to use DFS to detect cycles or count components: traverse the graph, marking visited nodes, and if you encounter a visited node that is not the parent, a cycle exists. For counting components, run DFS from each unvisited node. Complexity is O(V+E) time and O(V) space.

4. Compare trade-offs

Discuss when to use each: Union-Find is better for dynamic graphs with incremental edge additions, while DFS is simpler and more memory-efficient for static graphs. Mention that Union-Find has slightly higher constant factors but near-constant time per operation, whereas DFS requires storing the entire graph.

5. Code and test

Write clean pseudocode or actual code for one approach, explaining each step. Then suggest test cases: a graph with no cycle, a graph with one cycle, a disconnected graph, and edge cases like a single node or empty graph.

Key Points to Mention

Union-Find optimizations: path compression and union by rank/size, leading to O(α(n)) amortized time per operation.
DFS time complexity O(V+E) and space complexity O(V) for recursion stack and visited set.
Trade-offs: Union-Find excels for dynamic connectivity and is easy to implement iteratively; DFS is straightforward for static graphs and can be more memory-efficient if the graph is sparse.
Handling disconnected graphs: for counting components, iterate over all nodes and start DFS/Union-Find from unvisited ones.
Edge cases: self-loops, parallel edges, and graphs with multiple components.
Real-world applications: network redundancy detection, Kruskal's algorithm for MST, and social network friend circles.

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