導讀：Robinhood 的核心增長引擎是它的 Referral Program（推薦計劃）。這道題非常經典，因為它將業務邏輯（裂變拉新）完美映射到了演算法模型（樹/森林的子樹統計）。
很多同學在 OA 或 VO 遇到這題時，容易在「間接推薦」的定義上卡殼，或者寫出 $O(N^2)$ 的暴力解法。今天 oavoservice 帶你拆解這道 Top 3 Leaderboard 的 O(N) 最優解。
題目復盤：Referral Leaderboard
業務場景
你需要構建一個看板，追蹤用戶的推薦影響力。邏輯不僅僅是「我拉了誰」，而是「由於我，整個鏈條進來了多少人」。
如果 A 推薦了 B，B 推薦了 C，C 推薦了 D：
A → B → C → D
在這個模型下：
- A 的功勞：B、C、D（共 3 人）
- B 的功勞：C、D（共 2 人）
- C 的功勞：D（共 1 人）
核心需求
給定兩組陣列 rh_users（推薦人）和 new_users（被推薦人），輸出 推薦貢獻榜 Top 3。
規則細節（坑點）：
- 一次性原則：每個用戶只能被推薦一次（意味著結構是 樹 或 森林，不會有環，也不會有多個父節點）。
- 排序規則：
- 優先按 推薦總數 降序。
- 數量相同時，按 Username 字母序 升序。
- 門檻：只有推薦了至少 1 人的用戶才有資格上榜。
演算法破局：從暴力到優雅
❌ 陷阱：暴力模擬
最直覺的做法是：對於每一個用戶，順著鏈條往下 while 迴圈數人頭。
- 問題：如果鏈條極長（退化成鏈表），或者數據量大，這種 $O(N^2)$ 的做法在 CodeSignal 或 VO 中極易超時。
✅ 正解：DFS + Memoization（後序遍歷）
這本質上是一個 「計算多叉樹子樹大小」 的問題。 一個節點（用戶）的推薦總數 = 所有子節點（直推用戶）的貢獻之和 + 子節點本身的數量。
思路步驟：
- 建圖：使用雜湊表（Adjacency List）構建
referrer -> [referees]的映射。 - 記憶化搜尋：定義
dfs(user)返回該用戶「鏈條下」的總人數。count = 0for child in children: count += 1 + dfs(child)- 存入 memo，避免重複計算。
- 排序輸出：利用 Python 的 Tuple 排序特性
(-count, username)完美解決 Tie-break 問題。
Python 滿分程式碼模板
from collections import defaultdict
def top_3_referrals(rh_users, new_users):
# 1. 建圖：Adjacency List (Directed Tree/Forest)
graph = defaultdict(list)
# 使用集合收集所有出現過的人，確保沒有漏掉任何潛在的 Referrer
all_users = set(rh_users) | set(new_users)
for r, n in zip(rh_users, new_users):
graph[r].append(n)
# 2. 記憶化搜尋 (DFS)
memo = {}
def get_referral_count(node):
if node in memo:
return memo[node]
total_descendants = 0
for child in graph[node]:
# 貢獻 = 子節點本身(1) + 子節點拉來的人(get_referral_count(child))
total_descendants += 1 + get_referral_count(child)
memo[node] = total_descendants
return total_descendants
# 3. 計算所有人的貢獻
candidates = []
for user in all_users:
count = get_referral_count(user)
if count > 0:
candidates.append((count, user))
# 4. 排序：數量降序(-count)，字母升序(user)
# sort 默認是升序，所以數量取負值來實現降序
candidates.sort(key=lambda x: (-x[0], x[1]))
# 5. 格式化輸出 Top 3
result = []
for count, user in candidates[:3]:
result.append(f"{user} {count}")
return result
# Test Case
if __name__ == "__main__":
rh = ["A", "B", "C"]
new = ["B", "C", "D"]
print(top_3_referrals(rh, new))
# Output: ['A 3', 'B 2', 'C 1']
需要面試真題？ 立刻聯繫微信 Coding0201，獲得真題。