How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a Medium difficulty Coding & Algorithms question, commonly asked during Onsite rounds at Robinhood.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Robinhood during technical interviews.

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.

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.

Input: ([], [])

Expected Output: []

Explanation: There are no referrals, so no user has a referral count of at least 1.

Input: (["alice"], ["bob"])

Expected Output: ["alice 1"]

Explanation: alice directly referred bob, so alice has one downstream user.

Input: (["zoe", "amy", "amy", "bob", "bob", "dave"], ["amy", "bob", "carl", "dave", "eric", "fay"])

Expected Output: ["zoe 6", "amy 5", "bob 3"]

Explanation: zoe gets credit for everyone below amy. amy gets credit for bob, carl, dave, eric, and fay. bob gets credit for dave, eric, and fay.

Solution

def solution(rh_users, new_users):
    from collections import defaultdict

    children = defaultdict(list)
    all_users = set()
    referred = set()

    for referrer, new_user in zip(rh_users, new_users):
        children[referrer].append(new_user)
        all_users.add(referrer)
        all_users.add(new_user)
        referred.add(new_user)

    roots = [user for user in all_users if user not in referred]
    counts = {user: 0 for user in all_users}

    for root in roots:
        stack = [(root, False)]
        while stack:
            user, processed = stack.pop()
            if processed:
                total = 0
                for child in children[user]:
                    total += 1 + counts[child]
                counts[user] = total
            else:
                stack.append((user, True))
                for child in children[user]:
                    stack.append((child, False))

    ranked = sorted(
        ((user, count) for user, count in counts.items() if count >= 1),
        key=lambda item: (-item[1], item[0])
    )[:3]

    return [f'{user} {count}' for user, count in ranked]

Time complexity: O(n + u log u), where n is the number of referral pairs and u is the number of distinct users. Space complexity: O(u).

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.

Quick Overview