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
This problem models Robinhood’s referral network as a directed chain, where each referral adds edges A→B→C→….
Each user indirectly refers all nodes downstream in the chain.
We must compute how many users each person indirectly referred and return the top-3 ranked users using:
- descending referral count,
- alphabetical tiebreaks,
- and only users with ≥1 referral.
This becomes a graph problem where a single chain grows incrementally.
A reverse traversal or cumulative suffix counting solves the problem efficiently.
