Robinhood Phone Screen: Referral Chain Leaderboard (Top 3)


This is a very representative Robinhood-style phone screen question: business logic that maps cleanly to graph counting.

You are given two arrays:

• rh_users[i]: referrer in the i-th event
• new_users[i]: newly joined user in the i-th event

So each row defines a directed edge: rh_users[i] -> new_users[i].

The key business rule is: a user is considered to have referred everyone downstream in their referral chain, not just direct invitees.

For example: A -> B -> C -> D

• A referred 3 users (B, C, D)
• B referred 2 users (C, D)
• C referred 1 user (D)

Goal: output top 3 users by referral count.

---

Rules Breakdown

Referral Rules

1. A user can be referred only once.
2. Once a user joins, they cannot be referred again.
3. Input order is chronological referral order.

This implies the structure is a directed forest (acyclic, each node indegree <= 1).

Leaderboard Rules

1. Only include users with referral count >= 1.
2. Return at most 3 users.
3. Sort by referral count descending.
4. If tied, sort by username ascending.

---

Example

Input:

rh_users = ["A", "B", "C"]
new_users = ["B", "C", "D"]

Graph: A -> B -> C -> D

Output:

["A 3", "B 2", "C 1"]

---

Core Modeling

Each user’s score is the number of descendants in the referral graph subtree (excluding self).

So we can:

1. Build adjacency list parent -> children
2. Run DFS post-order to compute descendants
3. Use memoization so each node is computed once
4. Sort and take top 3

Main computation is linear.

---

Python Solution (Interview-ready)

from collections import defaultdict

def top3_referral_leaderboard(rh_users, new_users):
    # 1) Build graph
    graph = defaultdict(list)
    all_users = set(rh_users) | set(new_users)

    for u, v in zip(rh_users, new_users):
        graph[u].append(v)

    # 2) DFS + memo: descendants count (excluding self)
    memo = {}

    def dfs(user):
        if user in memo:
            return memo[user]

        total = 0
        for child in graph[user]:
            total += 1 + dfs(child)

        memo[user] = total
        return total

    # 3) Gather candidates (must be >= 1)
    candidates = []
    for user in all_users:
        cnt = dfs(user)
        if cnt >= 1:
            candidates.append((cnt, user))

    # 4) Sort by count desc, then username asc
    candidates.sort(key=lambda x: (-x[0], x[1]))

    # 5) Top 3 and format
    return [f"{user} {cnt}" for cnt, user in candidates[:3]]


if __name__ == "__main__":
    rh_users = ["A", "B", "C"]
    new_users = ["B", "C", "D"]
    print(top3_referral_leaderboard(rh_users, new_users))
    # ['A 3', 'B 2', 'C 1']

---

Complexity

Let n be number of referral edges:

• Build graph: O(n)
• DFS + memo: O(n)
• Sorting m candidates: O(m log m), where m <= n + 1

Total: O(n + m log m).

---

How to Explain in a Phone Screen (high signal)

1. Clarify indirect referral = all descendants.
2. State structural property: each new user appears once => indegree <= 1.
3. Reject brute force rescans (O(n^2) worst-case).
4. Present DFS + memo (compute each node once).
5. Finish with sorting key (-count, username) and top-3 slicing.

This hits modeling, complexity, and implementation clarity in one flow.

---

20-second version for interviewer

I model referrals as a directed forest and define each user’s score as descendant count. I build adjacency lists in O(n), compute descendant counts with DFS + memoization so each node is processed once, then sort users by (-count, username) and return top 3 with count >= 1.

---

Need Robinhood / Stripe / TikTok interview prep?

• WeChat: Coding0201
• Telegram: @OAVOProxy
• Email: [email protected]