Robinhood is famous for its referral program. It’s exciting to see 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 the referral chain:
A → B → C → D
Thus, A“referred”B, C, and D; B“referred”C and D; C“referred”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 a user joins the RH platform, he/she cannot be referred again.
- Example: If A refers B, no one else can refer A or B.
- Referrals in the input appear in the order they were made.
✅ Leaderboard Rules:
- A user must have at least 1 referral to appear on the leaderboard.
- The leaderboard contains at most 3 users.
- Sort the list by referral count (descending).
- If users have the same referral count, sort by username alphabetical order.
✅ Input Example
rh_users = ["A", "B", "C"]
new_users = ["B", "C", "D"]
This means:
- A → B
- B → C
- C → D
✅ Output Example
["A 3", "B 2", "C 1"]
Because:
- A referred B, C, D → 3
- B referred C, D → 2
- C referred D → 1
这个题把 Robinhood 的邀请关系建模成一个“单链图”，每次新用户加入，会形成一条 A→B→C→D 的推荐链。
每个人都能“间接推荐”链上自己后面的所有人，因此需要计算每个节点的 后缀长度 。
最终输出邀请人数最多的前三名，排序规则：
- 按推荐人数降序
- 相同人数按字母顺序
- 只保留至少推荐 1 人的用户
本质是一个 有向链结构的累计后缀计数问题 ，可以 O(n) 完成。
