Google Interview Problem #2: Earliest Time the Social Graph Becomes Fully Connected

Here we have an event log file produced by a Friends service, e.g.:

1648385616 Alice and Bob become friends
1648305678 Charlie and Dan become friends
1648366171 Bob and Charlie become friends
1648366237 Alice and Erin become friends
...

Given a list of all users and the logs above, implement a function that returns the earliest timestamp at which every user became reachable from every other user via friendship connections (i.e., when the social graph first became fully connected).
If the graph never becomes fully connected, return an appropriate sentinel (e.g., None / -1).

You may assume a helper that parses the log:

def log_parser(log_file: str) -> Generator[tuple[int, str, str, str], None, None]:
    with open(log_file, 'r') as f:
        for line in f:
            columns = line.split(' ')
            timestamp = int(columns[0])
            src = columns[1]
            dst = columns[3]
            event = columns[4]         # e.g., "friends"
            yield (timestamp, src, dst, event)

Constraints / notes:

• Each line indicates an undirected friendship between two users at the given timestamp.
• Timestamps may be out of order in the file; your algorithm should use chronological order.
• Input includes the full set of users (some may appear only in the users list before any edges).
• Return a single integer timestamp (or sentinel), not the sequence of edges.

• From friendship logs, find the earliest timestamp when the undirected graph over all users becomes connected.
• If it never becomes connected, return a sentinel.
• Use Union-Find: sort edges by timestamp, union endpoints, track component count; when it hits 1, return that timestamp.

The VOprep team has long accompanied candidates through various major company OAs and VOs, including OpenAI, Google, Amazon, Citadel, SIG, providing real-time voice assistance, remote practice, and interview pacing reminders to help you stay smooth during critical moments. If you are preparing for Stripe or similar engineering-focused companies, you can check out our customized support plans—from coding interviews to system design, we offer full guidance to help you succeed.