Google 面试题 #2：社交网络联通的最早时间（基于好友日志 – 面试辅助 – 一亩三分地 – 代面试

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.

给定所有用户名单与“成为好友”的 时间日志 ，求社交图 第一次变为全联通 （所有人两两可达）时的 最早时间戳。

若始终不联通，返回 -1/None。

典型做法：并查集（Union-Find）。按时间升序处理每条好友关系，合并连通块；当连通块数变为 1 的那一刻，即为答案。

VOprep 团队长期陪同学员实战各类大厂 OA 与 VO，包括 OpenAI、Google、Amazon、Citadel、SIG 等，提供实时语音助攻、远程陪练与面试节奏提醒，帮助大家在关键时刻不卡壳。
如果你也在准备 Stripe 或类似工程向公司，可以了解一下我们的定制助攻方案——从编程面到系统设计，全程护航上岸。