Robinhood OA 面试真题解析：Dashboard to Track the Status of the Program（Referral Leaderboard）

Robinhood is famous for its referral program. It’s exciting to see our users spreading the word across their friends and family. One thing that is interesting about the program is the network effect it creates. We would like to build a dashboard to track the status of the program. Specifically, we would like to learn about how people refer others through the chain of referral.

For the purpose of this question, we consider that a person refers all other people down the referral chain. For example, A refers B, C, and D in a referral chain of A -> B -> C -> D. Please build a leaderboard for the top 3 users who have the most referred users along with the referral count.

Referral rules:

• A user can only be referred once.
• Once the user is on the RH platform, he/she cannot be referred by other users. For example: if A refers B, no other user can refer A or B since both of them are on the RH platform.
• Referrals in the input will appear in the order they were made.

Leaderboard rules:

• The user must have at least 1 referral count to be on the leaderboard.
• The leaderboard contains at most 3 users.
• The list should be sorted by the referral count in descending order.
• If there are users with the same referral count, break the ties by the alphabetical order of the user name.

Input

rh_users = ["A", "B", "C"]
new_users = ["B", "C", "D"]

Output

["A 3", "B 2", "C 1"]

这道题的核心是根据按时间顺序给出的直接推荐关系，推导出“链式推荐”下每个用户的总推荐人数：如果 A 推荐了 B，而 B 又推荐了 C，那么 A 也要算上 C。可以把每次推荐看成一条边，并维护“谁在平台上”以及“谁的祖先链有哪些人”，这样才能保证后续用户不能再被重复推荐。实现时通常先建立父子关系，再通过 DFS/BFS 或从新用户向上回溯，把每个新用户对所有上游推荐人的贡献累计到计数表里。最后把所有计数大于 0 的用户按“推荐数降序、用户名升序”排序，取前 3 名即可。样例中 A 通过链 A->B->C->D 拿到 3，B 拿到 2，C 拿到 1。