Google·Software Engineer·Technical Phone Screen·Intermediate

Intermediate

Jun 2026

Summary

Google SWE interview with a graph connectivity problem that looks like a Union-Find warmup until unfriend events show up and suddenly you're having a very different conversation.

Questions Asked (1)

Given N people (IDs 0 to N-1) and a list of timestamped logs where each log records a 'friend' or 'unfriend' action between two people, find the earliest timestamp at which all N people are connected in a single group transitively. Return -1 if they never all connect.

Algorithms & Data StructuresTechnical Trade-offs

Author's notes

Started with Union-Find, felt good about it, then they asked about the unfriend events and I kind of froze.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Model the problem as dynamic connectivity with edge additions and deletions, and binary search on the timestamp to find the earliest time when all N people are connected. For each candidate time, process only the logs up to that time and check if the resulting graph is connected using union-find, which handles additions efficiently but requires care with deletions.

Pro tip: Mention that offline processing with divide-and-conquer on time (segment tree over time) can handle both additions and deletions in O((N + M) log M α(N)) time, which is optimal and demonstrates advanced algorithmic knowledge.

1. Clarify and Model

Confirm that logs are given in chronological order, actions are between two distinct people, and connectivity is transitive. Model people as nodes and friend actions as undirected edges.

2. Identify Core Challenge

Recognize that unfriend actions remove edges, making standard union-find insufficient for dynamic updates. The goal is to find the earliest time when the graph becomes connected.

3. Choose Strategy

Propose binary search on the timestamp combined with a connectivity check. For each mid time, build the graph from logs up to that time and run BFS/DFS or union-find to test if all nodes are in one component.

4. Optimize with Offline Techniques

If deletions are frequent, suggest offline divide-and-conquer over time (segment tree on time) with rollback union-find to efficiently process all timestamps and find the earliest connected time.

5. Analyze Complexity and Edge Cases

Discuss time and space complexity, and handle edge cases: N=1 (already connected at time 0), no logs, duplicate logs, and self-friend actions (if allowed).

Key Points to Mention

Union-Find (Disjoint Set Union) with path compression and union by rank for efficient connectivity checks.
Binary search on the timestamp to reduce the number of connectivity checks from O(M) to O(log M).
Handling edge deletions: either rebuild the graph for each check or use offline divide-and-conquer with rollback.
Time complexity analysis: O((N + M) log M α(N)) with optimal approach, or O(M log M * (N + M)) with naive binary search.
Edge cases: N=1, no logs, logs with unfriend before friend, and ensuring all people are considered even if not in logs.
Trade-offs between online and offline approaches, and why offline is preferred for this problem.

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