这道题是 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 后序计算每个点的后代数
- 记忆化避免重复计算
- 统一排序取前三
时间复杂度可做到 O(n)（不算最终排序）或 O(n log n)（包含全量排序）。
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 + memo：每条边最多走一次，
O(n) - 排序：若候选用户数为
m，则O(m log m)，且m <= n + 1
总复杂度：O(n + m log m)，面试中可说“主计算是线性的，排序由题目输出要求决定”。
面试时怎么讲会加分
- 先明确“间接推荐”就是后代计数，不是只算直推。
- 明确结构性质：每个新用户只出现一次 => 入度 <= 1。
- 说明为何不能暴力从每个点往下扫（最坏
O(n^2)）。 - 给出 DFS 后序 + memo，强调“每个节点只算一次”。
- 最后补排序规则（
(-count, username)）和 Top3 截断。
这套表达非常符合 phone screen 的评分点：建模能力、复杂度意识、代码可落地。
你可以直接复述给面试官的 20 秒版本
I model the referral data as a directed forest, where each user’s score is the number of descendants in their subtree. I build adjacency lists in O(n), run DFS with memoization to compute each node once, then sort candidates by (-count, username) and return top 3. This handles indirect referrals naturally and avoids O(n²) rescans.
需要 Robinhood / Stripe / TikTok 社招面试辅导？
- 微信：Coding0201
- Telegram：@OAVOProxy
- Email：[email protected]