Robinhood: Design a referral leaderboard with chain-based counts

Quick 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.

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.

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.

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.

Approach

The referral graph is a forest: every user in new_users has exactly one referrer, so each node has at most one parent. A user's referral count is its total number of descendants, so we need a subtree-size-minus-one count for every node.

Build the tree. Iterating over the zip(rh_users, new_users) pairs, we populate a children adjacency list, collect every name into all_users, and record each referred name in referred. Any user in all_users but not in referred has in-degree 0 — these are the roots.

Count descendants via iterative post-order DFS. For each root we use an explicit stack of (user, processed) tuples. On the first pop (processed=False) we push the node back as processed=True, then push all its children. When we pop it again (processed=True), every child's count is already final, so we set

The 1 + counts the child itself; counts[child] adds the child's own descendants. Children-before-parent ordering guarantees correctness. The explicit stack matters here: a chain of up to 200k nodes would overflow Python's recursion limit, but the loop handles it safely.

Rank. We keep only count >= 1, sort by (-count, username) so ties break lexicographically ascending, slice the top 3, and format each as "<user> <count>". Empty input yields [], and a single referral yields one entry — both covered by tests.

Time complexity:

O(n + u log u), where n = number of referral pairs and u = number of distinct users. Tree construction and the post-order DFS each touch every node/edge a constant number of times (O(n + u) ≈ O(n)); the final sort over the filtered users dominates at O(u log u).

Space complexity:

O(u). The `children` map, `all_users`/`referred` sets, the `counts` dict, and the DFS stack are each bounded by the number of distinct users (with n edges stored in `children`, this is O(n + u) ≈ O(n)).