Design a referral leaderboard with chain-based counts
Company: Robinhood
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
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.
Quick Answer: 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.
You are given two equal-length arrays rh_users and new_users. For each index i, rh_users[i] referred new_users[i], and the pairs appear in the order they were created. The input is guaranteed to be valid: a user is referred at most once, and once a user is already on the platform, they are not referred again later. A user's referral count is the number of all downstream users in their referral tree (all descendants), not just direct referrals. For example, in A -> B -> C -> D, A has count 3, B has count 2, and C has count 1. Return a leaderboard containing only users with count at least 1, sorted by descending referral count and then by username in ascending lexicographic order. Return at most the top 3 entries, each formatted as '<user> <count>'.
Constraints
- 0 <= len(rh_users) == len(new_users) <= 200000
- The referral pairs form a valid forest: each user in new_users appears exactly once and has exactly one referrer
- Usernames are non-empty strings and are compared using standard lexicographic order
Examples
Input: (["A", "B", "C"], ["B", "C", "D"])
Expected Output: ["A 3", "B 2", "C 1"]
Explanation: A gets credit for B, C, and D. B gets credit for C and D. C gets credit for D.
Input: (["A", "A", "B", "C", "D"], ["B", "C", "E", "F", "G"])
Expected Output: ["A 4", "B 1", "C 1"]
Explanation: A has descendants B, C, E, and F. B, C, and D each have count 1, but only the lexicographically smallest two ties fit after A in the top 3.
Hints
- Model the referral history as a forest of trees. A user's chain-based referral count is the number of descendants in that user's subtree.
- Build child lists first, then compute counts bottom-up with a post-order traversal instead of walking up the ancestor chain for every referral.