在技術面試中，社交網絡圖相關的問題經常被用來考察候選人的演算法設計和圖論知識。今天，我們通過 Google 面試中的一道實際問題，展示如何高效解決圖連通性問題，並展示 oavoservice 在面試中的輔助價值。
📋 題目原文
給定一系列好友關係的日誌，每條日誌包含時間戳和兩個用戶的關係變化。你需要找到最早的時間點，使得通過好友關係網絡，所有用戶之間都可以互相到達。
輸入：
users: 用戶列表logs: 好友關係日誌，每條包含[timestamp, user1, user2]
輸出：
- 返回網絡完全連通的最早時間戳
- 如果無法完全連通，返回
-1
約束條件：
- 好友關係是雙向的
- 日誌已按時間排序
- 可以忽略重複的好友關係
🎯 核心考點分析
這道題主要考察：
- 並查集（Union-Find）資料結構 - 動態連通性問題的最佳解決方案
- 圖論思維 - 理解連通分量的概念
- 時間複雜度優化 - 路徑壓縮和按秩合併
- 邊界處理 - 處理無法連通的情況
💡 解題思路（oavoservice 實戰指導）
方法：並查集（Union-Find）
為什麼選擇並查集？
oavoservice 建議：並查集特別適合這種問題，因為它可以：
- 高效判斷兩個用戶是否屬於同一個連通分量
- 支援快速合併操作
- 通過路徑壓縮和按秩合併，時間複雜度接近 O(1)
實作步驟
class UnionFind:
def __init__(self, n):
self.parent = list(range(n))
self.rank = [0] * n
self.components = n
def find(self, x):
# 路徑壓縮
if self.parent[x] != x:
self.parent[x] = self.find(self.parent[x])
return self.parent[x]
def union(self, x, y):
root_x, root_y = self.find(x), self.find(y)
if root_x == root_y:
return False
# 按秩合併
if self.rank[root_x] < self.rank[root_y]:
self.parent[root_x] = root_y
elif self.rank[root_x] > self.rank[root_y]:
self.parent[root_y] = root_x
else:
self.parent[root_y] = root_x
self.rank[root_x] += 1
self.components -= 1
return True
def is_connected(self):
return self.components == 1
def earliest_connection_time(users, logs):
n = len(users)
user_index = {user: i for i, user in enumerate(users)}
uf = UnionFind(n)
for timestamp, user1, user2 in logs:
idx1, idx2 = user_index[user1], user_index[user2]
uf.union(idx1, idx2)
# 檢查是否完全連通
if uf.is_connected():
return timestamp
return -1
📊 複雜度分析
時間複雜度： O(n × α(n))
- n 是日誌條目數
- α 是反 Ackermann 函數，可視為常數
- 總體接近 O(n)
空間複雜度： O(u)
- u 是用戶總數
- 需要存儲每個用戶的父節點和秩
🚀 優化策略（oavoservice 高級指導）
1. 批量處理優化
對於超大規模日誌（數百萬條），可以：
- 批量處理日誌，減少檢查頻率
- 只在必要時檢查連通性
2. 早期終止
# 如果已經連通，立即返回，不再處理後續日誌
if uf.is_connected():
return timestamp
3. 預處理優化
- 可以預先過濾掉重複的關係
- 對用戶進行索引映射，提高查找效率
🎤 面試中的關鍵問題
Q1: 如果日誌非常大怎麼辦？
oavoservice 建議：
- 使用批量處理減少檢查次數
- 考慮分佈式處理方案
- 可以使用採樣策略估算連通時間
Q2: 如何處理動態刪除好友關係？
oavoservice 建議：
- 並查集不支援高效刪除
- 需要考慮其他資料結構，如動態圖
- 或者重新構建並查集
Q3: 能否用 BFS/DFS 解決？
oavoservice 建議：
- 可以，但效率較低
- 每次添加關係後都需要遍歷整個圖
- 時間複雜度會達到 O(n × (V + E))
💼 oavoservice 如何助力面試成功
在真實面試中，oavoservice 提供：
即時思路引導 - 幫你快速選擇最優演算法 程式碼實作輔助 - 確保程式碼邏輯清晰正確 追問應對策略 - 提前準備面試官的深度追問 複雜度分析 - 準確分析時間和空間複雜度 優化方案討論 - 展現工程實踐能力
想在 Google、Meta、Amazon 等頂級公司的面試中脫穎而出？
聯繫 oavoservice，我們提供專業的 OA/VO 面試輔助服務，助你順利拿到 Dream Offer。
標籤： #Google #圖論 #並查集 #UnionFind #社交網絡 #面試輔助 #VO輔助 #演算法面試 #一畝三分地
需要面試真題？ 立刻聯繫微信 Coding0201，獲得真題。