Katkat
Back

Design a referral leaderboard with chain-based counts

RobinhoodSoftware Engineer · Onsite
MediumSoftware EngineerOnsiteCoding & Algorithms

Last updated

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