這題是 Robinhood phone screen 非常典型的「商業語義 + 圖建模」題。
你會拿到兩組陣列：
rh_users[i]：第i次邀請中的邀請人new_users[i]：第i次邀請中的新使用者
每筆資料代表一條有向邊：rh_users[i] -> new_users[i]。
關鍵定義是：一位使用者不只推薦了直推對象，也推薦了邀請鏈下游所有人。
例如：
A -> B -> C -> D
- A 推薦 3 人（B, C, D）
- B 推薦 2 人（C, D）
- C 推薦 1 人（D）
目標是輸出推薦榜 Top 3。
規則拆解
Referral Rules
- 每位使用者只能被邀請一次。
- 使用者加入後不能再次被邀請。
- 輸入順序即邀請發生順序。
因此結構可視為 有向森林（無環、每個節點入度 <= 1）。
Leaderboard Rules
- 只保留推薦人數 >= 1 的使用者。
- 最多回傳 3 位。
- 先按推薦人數降序。
- 同分按使用者名稱字母序升序。
範例
輸入：
rh_users = ["A", "B", "C"]
new_users = ["B", "C", "D"]
圖結構：
A -> B -> C -> D
輸出：
["A 3", "B 2", "C 1"]
建模思路
每個人的分數其實是：
- 該節點子樹中的後代節點數（不含自己）
所以做法是：
- 建立鄰接表
parent -> children - 用 DFS 後序計算每個節點後代數
- 用 memo 避免重複計算
- 依規則排序並取前 3
核心計算可線性完成。
Python 解法（Phone Screen 可直接講）
from collections import defaultdict
def top3_referral_leaderboard(rh_users, new_users):
# 1) Build graph
graph = defaultdict(list)
all_users = set(rh_users) | set(new_users)
for u, v in zip(rh_users, new_users):
graph[u].append(v)
# 2) DFS + memo: descendants count (excluding self)
memo = {}
def dfs(user):
if user in memo:
return memo[user]
total = 0
for child in graph[user]:
total += 1 + dfs(child)
memo[user] = total
return total
# 3) Gather candidates (must be >= 1)
candidates = []
for user in all_users:
cnt = dfs(user)
if cnt >= 1:
candidates.append((cnt, user))
# 4) Sort by count desc, then username asc
candidates.sort(key=lambda x: (-x[0], x[1]))
# 5) Top 3 and format
return [f"{user} {cnt}" for cnt, user in candidates[:3]]
if __name__ == "__main__":
rh_users = ["A", "B", "C"]
new_users = ["B", "C", "D"]
print(top3_referral_leaderboard(rh_users, new_users))
# ['A 3', 'B 2', 'C 1']
複雜度分析
設邀請邊數為 n：
- 建圖：
O(n) - DFS + 記憶化：
O(n) - 排序
m位候選：O(m log m)，且m <= n + 1
總計：O(n + m log m)。
面試怎麼講更加分
- 先明確「間接推薦」= 所有後代。
- 說清楚結構性質：每個新使用者只出現一次，入度 <= 1。
- 反證暴力重掃最壞
O(n^2)。 - 給出 DFS 後序 + memo，每個節點只算一次。
- 補上排序鍵
(-count, username)與 top-3。
這套回答能同時覆蓋建模能力、複雜度意識、實作落地。
20 秒英文版本（可直接背）
I model referrals as a directed forest and define each user’s score as descendant count. I build adjacency lists in O(n), compute descendant counts with DFS + memoization so each node is processed once, then sort users by (-count, username) and return top 3 with count >= 1.
需要 Robinhood / Stripe / TikTok 社招面試輔導？
- 微信：Coding0201
- Telegram：@OAVOProxy
- Email：[email protected]