Referral Chain Leaderboard
MediumGraphs ยท Robinhood
Given two parallel lists, referrers and referred, where referrers[i] referred referred[i] and pairs are in time order, rank users by how many referrals sit below them.
A referral is valid only if referrers[i] != referred[i] and referred[i] has not yet appeared in any earlier valid referral, as either member of the pair. An invalid referral is ignored and changes nothing. A user's score is the number of users below them in the referral tree, direct and indirect.
Return up to three strings "name score" for users with score at least 1, ordered by score descending, then name ascending.
Example 1
- Input:
- referrers = ["amy", "amy", "ben", "cal", "dee"], referred = ["ben", "cal", "dee", "eli", "ben"]
- Output:
- ["amy 4", "ben 1", "cal 1"]
- Explanation
- The last referral is ignored because
benalready appeared. Four users sit belowamy:ben,cal,deeandeli.
Example 2
- Input:
- referrers = ["x", "x"], referred = ["y", "z"]
- Output:
- ["x 2"]
Example 3
- Input:
- referrers = ["a", "b", "c"], referred = ["b", "a", "a"]
- Output:
- ["a 1"]
- Explanation
- After
arefersb, both later referrals namea, who has already appeared, so they are ignored.
Constraints
0 <= referrers.length <= 10^5- Each name is 1 to 10 lowercase letters or digits; names compare as plain strings
referrersandreferredhave the same length