Design a referral leaderboard with chain-based counts
Overview
This question evaluates a candidate's ability to model and compute transitive referral counts using graph-like structures and efficient data structures, testing skills in algorithm design, counting, and sorting within the Coding & Algorithms domain.
Robinhood
Aug 12, 2025, 12:00 AM
Software Engineer
Onsite
Coding & Algorithms
0
0
Design and implement a function that generates a referral leaderboard for a platform, given two equal-length arrays rh_users and new_users representing referrals in chronological order (rh_users[i] referred new_users[i]). A user is considered to have referred everyone downstream in their referral chain (e.g., for A -> B -> C -> D, A referred B, C, and D; B referred C and D; C referred D). Requirements:
-
Referral rules:
- A user can be referred at most once.
- Once a user is on the platform, they cannot be referred by others later.
- The input pairs appear in the order they were created.
-
Leaderboard rules:
- Include only users with referral count >= 1.
- Return at most the top 3 users.
- Sort by descending referral count; break ties by username in ascending lexicographic order.
-
Input:
- rh_users: string[] of referrers.
- new_users: string[] of referred users, aligned by index with rh_users.
-
Output:
- string[] of up to 3 entries in the form " <user> <count> ". Example:
- rh_users = ["A", "B", "C"], new_users = ["B", "C", "D"].
- Output: ["A 3", "B 2", "C 1"]. Discuss your data structures, time and space complexity, and provide runnable code in the language of your choice.