Referral Network Data Structure and Algorithms

Question

Implement a referral network system (similar to a social network follower/followee graph) in three parts:

**Part 1:** Design and implement the core referral network data structure. Each user can be a referrer (who recommends others) and/or a referee (who was recommended). Support operations such as adding referral relationships.

**Part 2:** Built on Part 1, implement two ranking functions that return the top-K users by:
1. Total candidate count — the total number of users reachable from a given user, counting both direct and indirect referrals (i.e., the full descendant subtree/subgraph).
2. Flow centrality — the number of times a user appears on referral paths between other pairs of users in the network.

**Part 3:** Implement a function to estimate the expected total network size after N days, given: every referrer has probability p of making one successful referral each day, and each person can make at most 10 successful referrals over their lifetime.

No test cases are provided; candidates must write and run their own tests. LLMs are not allowed for Parts 1 & 2 (Google for syntax only); Part 3 is done live with the interviewer.

AceOffer · Accepted Answer

Implement a referral network system (similar to a social network follower/followee graph) in three parts:

**Part 1:** Design and implement the core referral network data structure. Each user can be a referrer (who recommends others) and/or a referee (who was recommended). Support operations such as adding referral relationships.

**Part 2:** Built on Part 1, implement two ranking functions that return the top-K users by:
1. Total candidate count — the total number of users reachable from a given user, counting both direct and indirect referrals (i.e., the full descendant subtree/subgraph).
2. Flow centrality — the number of times a user appears on referral paths between other pairs of users in the network.

**Part 3:** Implement a function to estimate the expected total network size after N days, given: every referrer has probability p of making one successful referral each day, and each person can make at most 10 successful referrals over their lifetime.

No test cases are provided; candidates must write and run their own tests. LLMs are not allowed for Parts 1 & 2 (Google for syntax only); Part 3 is done live with the interviewer.

Reported follow-ups:
1. Walk me through your data structure choice and how you handle cycles or duplicate referrals. (when: After candidate implements Part 1)
2. How does your flow centrality calculation work, and what is its time complexity? (when: After candidate implements Part 2 ranking functions)
3. How does the 10-referral lifetime cap affect your model, and how did you account for it? (when: After candidate implements Part 3 growth estimator)

**Alternative approaches:** Memoized DFS for descendant count (Caches subtree sizes to avoid recomputation across multiple top-K queries, but requires cache invalidation if the graph is mutable.); Monte Carlo simulation for Part 3 (Easier to implement and handles complex stochastic dependencies, but is approximate and slower than closed-form expected value computation.)

Referral Network Data Structure and Algorithms

Problem Overview

Follow-up Arc

Approach Trade-offs

Practice

Approach	Notes
Memoized DFS for descendant count	Caches subtree sizes to avoid recomputation across multiple top-K queries, but requires cache invalidation if the graph is mutable.
Monte Carlo simulation for Part 3	Easier to implement and handles complex stochastic dependencies, but is approximate and slower than closed-form expected value computation.