Count Referral Descendants
Problem Description
You are tasked with building a referral analytics feature.
Each referral relationship is defined as a directed pair (referrer, referredUser), indicating that referrer directly invited referredUser. A user can directly refer multiple other users, but crucially, each user has at most one direct referrer. It is guaranteed that the referral graph is acyclic, meaning it forms one or more rooted trees.
Given a list of such referral pairs, your goal is to compute, for every user, the total number of users within their referral network. This includes both direct and indirect referrals, effectively meaning you need to return the number of descendants reachable from each user in the referral graph.
Example:
referrals = [
("A", "B"),
("A", "C"),
("B", "D"),
("B", "E"),
("C", "F")
]
Expected Result:
A -> 5
B -> 2
C -> 1
D -> 0
E -> 0
F -> 0
Requirements
- Return a mapping from every user appearing in the input to their total referral count.
- Explain the time and space complexity of your solution.
- Discuss how you would efficiently find the top 3 users by referral count.
- Discuss strategies to avoid recursion-depth issues for very deep referral chains.
Follow-up: Incremental Updates
Suppose this is an online production system where referral relationships are continuously added. The referral graph is very large, and recomputing all counts after every new insertion is prohibitively expensive. Design an approach to support incremental updates when a new referral edge is added.
AI interview prep
Core dilemma
Efficiently calculating descendant counts in a potentially large, dynamic, tree-like graph, balancing initial computation with the need for incremental updates and handling scale challenges like recursion depth.
3 tradeoffs and 3 stress tests locked
Interview prep
Unlock the interviewer X-Ray rubric, tradeoff matrix, stress tests, clarifying questions, and key concepts.
Count Referral Descendants
Problem Description
You are tasked with building a referral analytics feature.
Each referral relationship is defined as a directed pair (referrer, referredUser), indicating that referrer directly invited referredUser. A user can directly refer multiple other users, but crucially, each user has at most one direct referrer. It is guaranteed that the referral graph is acyclic, meaning it forms one or more rooted trees.
Given a list of such referral pairs, your goal is to compute, for every user, the total number of users within their referral network. This includes both direct and indirect referrals, effectively meaning you need to return the number of descendants reachable from each user in the referral graph.
Example:
referrals = [
("A", "B"),
("A", "C"),
("B", "D"),
("B", "E"),
("C", "F")
]
Expected Result:
A -> 5
B -> 2
C -> 1
D -> 0
E -> 0
F -> 0
Requirements
- Return a mapping from every user appearing in the input to their total referral count.
- Explain the time and space complexity of your solution.
- Discuss how you would efficiently find the top 3 users by referral count.
- Discuss strategies to avoid recursion-depth issues for very deep referral chains.
Follow-up: Incremental Updates
Suppose this is an online production system where referral relationships are continuously added. The referral graph is very large, and recomputing all counts after every new insertion is prohibitively expensive. Design an approach to support incremental updates when a new referral edge is added.