Google·Software Engineer·Onsite - Coding / Algorithms·Senior

SeniorPrefer not to say

May 2026

Summary

Google SWE interview that went deep into graph theory territory. The core problem was a follow-up on a classic connectivity question, but with deletions thrown in, which completely changes the data structure story. Pretty brutal if you only prepped Union-Find.

Questions Asked (1)

You have a log of friendship events that includes both additions and removals. After each event, you might be asked if two people are connected, or if the whole graph is still a single connected component. How do you handle this efficiently?

Algorithms & Data StructuresTechnical Trade-offsSystem Design

Author's notes

This is the fully dynamic connectivity problem and the moment they said 'removals' I knew my Union-Find prep was not going to save me.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Start by clarifying the constraints: are the events known in advance (offline) or streaming (online)? For offline, process events in reverse using a union-find data structure to handle additions easily; for online, use a dynamic connectivity data structure like Euler Tour Trees or Link-Cut Trees. Then discuss trade-offs between simplicity and efficiency, and how to answer both pairwise connectivity and global connectivity queries.

Pro tip: Mention that for the global connectivity check, you can maintain a count of connected components and update it on each union; this avoids a separate traversal. Also, if the graph is small or queries are infrequent, a simpler BFS/DFS per query might be acceptable—show you can adapt to context.

1. Clarify the problem and constraints

Ask whether the sequence of events is known in advance (offline) or must be processed online, and what the expected scale is (number of nodes, events, queries). This determines the appropriate data structure.

2. Choose the right data structure

For offline processing, use union-find with reverse time. For online, consider Euler Tour Trees or Link-Cut Trees for dynamic connectivity. Mention that union-find alone cannot handle deletions efficiently.

3. Handle pairwise connectivity queries

For union-find, check if two nodes have the same root. For dynamic trees, use the find-root operation. Explain the time complexity (near O(1) amortized for union-find, O(log n) for dynamic trees).

4. Handle global connectivity queries

Maintain a count of connected components. On union, decrement if merging two different components; on deletion, increment if splitting. The graph is fully connected if the count is 1.

5. Discuss trade-offs and optimizations

Compare the simplicity of union-find (offline) versus the complexity of dynamic trees (online). Mention that if deletions are rare, a hybrid approach or periodic rebuilding might be practical.

Key Points to Mention

Union-Find (Disjoint Set Union) with path compression and union by rank for efficient additions.
Offline processing by reversing time to turn deletions into additions.
Dynamic connectivity data structures: Euler Tour Trees, Link-Cut Trees, or Holm-de Lichtenberg-Thorup algorithm.
Maintaining a component count for O(1) global connectivity checks.
Time complexity analysis: O(α(n)) per operation for union-find, O(log n) for dynamic trees.
Trade-offs between implementation complexity and performance, and when a simpler approach suffices.

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