Robinhood Must-Read | Referral Leaderboard: Chain Referral & DFS

Intro: Robinhood's core growth engine is its Referral Program. This question is classic because it perfectly maps business logic (viral growth) to an algorithmic model (tree/forest subtree statistics).

Many students get stuck on the definition of "indirect referral" or write an $O(N^2)$ brute force solution during OA or VO. Today, oavoservice breaks down the O(N) optimal solution for this Top 3 Leaderboard problem.

Problem Review: Referral Leaderboard

Business Scenario

You need to build a dashboard to track the referral influence of users. The logic isn't just "who I invited", but "how many people entered the chain because of me".

If A refers B, B refers C, C refers D: A → B → C → D

In this model:

• A's credit: B, C, D (Total 3)
• B's credit: C, D (Total 2)
• C's credit: D (Total 1)

Core Requirement

Given two arrays rh_users (referrers) and new_users (referees), output the Top 3 Referral Leaderboard.

Rules Details (Pitfalls):

1. One-time Rule: Each user can only be referred once (implies the structure is a Tree or Forest, no cycles, no multiple parents).
2. Sorting Rules:
   • Priority: Total Referrals descending.
   • Tie-break: Username Alphabetical ascending.
3. Threshold: Only users who referred at least 1 person are eligible.

Algorithm Breakthrough: From Brute Force to Elegant

❌ Trap: Brute Force Simulation

The most intuitive approach is to loop while down the chain for every user to count heads.

• Issue: If the chain is extremely long (degrades to a linked list) or data is large, this $O(N^2)$ approach will likely timeout in CodeSignal or VO.

✅ Solution: DFS + Memoization (Post-order Traversal)

This is essentially a "Count Subtree Size in Multi-way Tree" problem. A node's (user's) total referrals = Sum of all children's (direct referees) contributions + Number of children themselves.

Steps:

1. Build Graph: Use a Hash Map (Adjacency List) to build referrer -> [referees] mapping.
2. Memoization Search: Define dfs(user) to return the total number of people under their "chain".
   • count = 0
   • for child in children: count += 1 + dfs(child)
   • Store in memo to avoid re-calculation.
3. Sort & Output: Use Python's Tuple sorting feature (-count, username) to perfectly solve the Tie-break problem.

Python Full Score Code Template

from collections import defaultdict

def top_3_referrals(rh_users, new_users):
    # 1. Build Graph: Adjacency List (Directed Tree/Forest)
    graph = defaultdict(list)
    # Use set to collect all users to ensure no potential Referrer is missed
    all_users = set(rh_users) | set(new_users)
    
    for r, n in zip(rh_users, new_users):
        graph[r].append(n)
    
    # 2. Memoization Search (DFS)
    memo = {}

    def get_referral_count(node):
        if node in memo:
            return memo[node]
        
        total_descendants = 0
        for child in graph[node]:
            # Contribution = Child itself(1) + People child brought in(get_referral_count(child))
            total_descendants += 1 + get_referral_count(child)
            
        memo[node] = total_descendants
        return total_descendants

    # 3. Calculate Contribution for All
    candidates = []
    for user in all_users:
        count = get_referral_count(user)
        if count > 0:
            candidates.append((count, user))
            
    # 4. Sort: Count Descending (-count), Alphabetical Ascending (user)
    # sort is ascending by default, so use negative count for descending
    candidates.sort(key=lambda x: (-x[0], x[1]))
    
    # 5. Format Output Top 3
    result = []
    for count, user in candidates[:3]:
        result.append(f"{user} {count}")
        
    return result

# Test Case
if __name__ == "__main__":
    rh = ["A", "B", "C"]
    new = ["B", "C", "D"]
    print(top_3_referrals(rh, new)) 
    # Output: ['A 3', 'B 2', 'C 1'] 

Need real interview questions? Contact WeChat Coding0201 immediately to get real questions.