Robinhood 上岸必刷｜Referral Leaderboard：当“链式推荐”遇上 DFS

导读：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 = 0
- for 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，获得真题。

Robinhood 上岸必刷｜Referral Leaderboard 推荐链算法详解