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

Intermediate

May 2026

Summary

Google SWE coding round with a graph connectivity problem that has a twist: edges can be removed, not just added. The UNFRIEND operation is what makes this tricky and pretty much kills any naive Union-Find approach.

Questions Asked (1)

Given N people and a list of timestamped FRIEND and UNFRIEND events (not necessarily sorted), find the earliest timestamp at which all N people form a single connected component. Return -1 if it never happens.

Algorithms & Data StructuresTechnical Trade-offs

Author's notes

My first instinct was Union-Find and I started going down that road before realizing UNFRIEND completely breaks it.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Sort the events by timestamp, then process them in order using a Union-Find (Disjoint Set Union) data structure to maintain connected components. After each event, check if the number of components has reduced to 1; if so, return the current timestamp. If all events are processed and the graph is never fully connected, return -1.

Pro tip: Mention that you can optimize by tracking the number of components and only checking when a union occurs, and that you should handle duplicate timestamps carefully by processing all events at the same timestamp before checking connectivity.

1. Clarify and Validate Input

Confirm that events are not sorted, timestamps may have duplicates, and that FRIEND/UNFRIEND events can be interleaved. Ask if N is large and if events can be numerous.

2. Choose Data Structures

Select Union-Find with path compression and union by rank for efficient connectivity tracking. Use a list to store events and sort them by timestamp.

3. Process Events Chronologically

Sort events by timestamp. Iterate through events, applying FRIEND as union and UNFRIEND as a split (which may require rebuilding or using a dynamic connectivity structure if splits are frequent).

4. Check Connectivity Condition

After each timestamp (or after processing all events at the same timestamp), check if the number of connected components is 1. If so, return that timestamp.

5. Handle Edge Cases and Return

If no timestamp achieves full connectivity, return -1. Also consider cases where N=1 (already connected at time 0) or no events.

Key Points to Mention

Union-Find (Disjoint Set Union) with path compression and union by rank for near-constant time operations.
Sorting events by timestamp is crucial since they are not initially sorted.
Handling UNFRIEND events: if splits are allowed, a simple Union-Find is insufficient; consider offline processing or dynamic connectivity structures.
Tracking the number of connected components to quickly check if all N people are connected.
Processing all events at the same timestamp before checking connectivity to avoid premature returns.
Time complexity: O(E log E) for sorting plus O(E α(N)) for Union-Find operations, where E is number of events.

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