Find Earliest Fully Connected Time
Company: Google
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
You are given `n` people labeled `0` to `n - 1` and a list of friendship logs. Each log has the form `(timestamp, personA, personB, action)`, where `action` is either `"friend"` or `"unfriend"`. Friendship is undirected.
Process the logs in chronological order. After each event, consider the current friendship graph. Return the earliest timestamp at which all `n` people belong to a single connected component. If that never happens, return `-1`.
Notes:
- Logs may not be sorted.
- If multiple logs have the same timestamp, process them in input order.
- Because edges can be both added and removed, the problem requires handling dynamic connectivity rather than only incremental unions.
Quick Answer: This question evaluates a candidate's understanding of dynamic graph connectivity, time-ordered event processing, and state maintenance in graphs, including handling both edge insertions and deletions.
You are given `n` people labeled from `0` to `n - 1` and a list of friendship logs. Each log is a tuple `(timestamp, action, u, v)` where `action` is either `'FRIEND'` or `'UNFRIEND'`.
A `'FRIEND'` log means an undirected friendship edge between `u` and `v` becomes active. An `'UNFRIEND'` log means that edge is removed. After each log is applied, consider the current friendship graph.
Return the earliest timestamp at which the graph becomes fully connected, meaning every person can reach every other person through some chain of friendships. If this never happens, return `-1`.
Special case: if `n <= 1`, return `0` because a single person is already connected.
The input logs may be unsorted. Process them in increasing timestamp order. If multiple logs have the same timestamp, process them in their original input order.
Constraints
- 1 <= n <= 2 * 10^5
- 0 <= len(logs) <= 2 * 10^5
- Each log is `(timestamp, action, u, v)` where `action` is `'FRIEND'` or `'UNFRIEND'`
- 0 <= u, v < n and u != v
- Logs are valid: a `'FRIEND'` event only appears when that pair is currently not friends, and an `'UNFRIEND'` event only appears when that pair is currently friends
Examples
Input: (4, [(3, 'FRIEND', 1, 2), (1, 'FRIEND', 0, 1), (2, 'FRIEND', 2, 3), (4, 'FRIEND', 0, 3)])
Expected Output: 3
Explanation: After sorting by time, the edges are added as 0-1, 2-3, then 1-2. At timestamp 3, all 4 people become connected for the first time.
Input: (4, [(1, 'FRIEND', 0, 1), (2, 'FRIEND', 2, 3), (3, 'FRIEND', 1, 2), (4, 'UNFRIEND', 1, 2), (5, 'FRIEND', 0, 2)])