Count Referral Descendants
Company: Robinhood
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
You are building a referral analytics feature.
Each referral relationship is represented as a directed pair `(referrer, referredUser)`, meaning `referrer` directly invited `referredUser`. A user may directly refer many users, but each user has at most one direct referrer. Assume the referral graph is acyclic, so it forms one or more rooted trees.
Given a list of referral pairs, compute for every user the total number of users in their referral network, including both direct and indirect referrals. In other words, for each user, return the number of descendants reachable from that user.
Example:
```text
referrals = [
("A", "B"),
("A", "C"),
("B", "D"),
("B", "E"),
("C", "F")
]
```
Expected result:
```text
A -> 5
B -> 2
C -> 1
D -> 0
E -> 0
F -> 0
```
Requirements:
1. Return a mapping from every user appearing in the input to their total referral count.
2. Explain the time and space complexity.
3. Discuss how you would find the top 3 users by referral count efficiently.
4. Discuss how you would avoid recursion-depth issues for very deep referral chains.
5. Follow-up: suppose this is an online production system where referral relationships are continuously added. The graph is very large, and recomputing all counts after every insertion is too expensive. Design an approach to support incremental updates when a new referral edge is added.
Quick Answer: This question evaluates graph and tree reasoning, algorithmic aggregation for computing descendant counts, and system-level thinking for incremental updates and recursion-depth mitigation.