Referral network: record referrals, measure reach, model growth

Implement a referral network. Users refer other users, and the network records who referred whom. Build the network, then answer questions about each user's reach, then reason about how the network grows over time.

Part 1: build the network

Unless you agree on a different interface with the interviewer, assume:

• add_referral(referrer: str, candidate: str) -> None records that referrer referred candidate. Reject it (raise ValueError) if it is a self-referral, if candidate already has a referrer, or if it would create a cycle.
• get_direct_referrals(user: str) -> list[str] returns the users this user referred directly, in the order added.

Part 2: reach and ranking

• total_referral_count(user: str) -> int returns how many users this user reached directly or through the people they referred (all descendants).
• top_referrers(k: int) -> list[str] returns the k users with the largest reach, ties broken by name.
• flow_centrality(user: str) -> int counts the pairs (a, b) where b was reached from a through user (so user lies strictly between them).

Part 3: growth

• expected_total(initial: int, p: float, capacity: int, days: int) -> float: the network starts with initial active referrers. Each day, every active referrer makes one successful referral with probability p, a referrer stops after capacity referrals, and each new user becomes an active referrer from the next day. Return the expected total number of referrals after days days.
• days_to_reach(initial, p, capacity, target) -> int: the fewest days for the expected total to reach target.

Example

add_referral("A", "B"); add_referral("A", "C"); add_referral("B", "D")
get_direct_referrals("A")     -> ["B", "C"]
add_referral("D", "A")        -> ValueError    # cycle
total_referral_count("A")     -> 3
total_referral_count("B")     -> 1
top_referrers(2)              -> ["A", "B"]
flow_centrality("B")          -> 1             # only the pair (A, D) passes through B
expected_total(100, 0.5, 10, 1)  -> 50.0
expected_total(100, 0.5, 10, 2)  -> 125.0      # day 2: 100 * 0.5 from the first users + 50 * 0.5 from the new ones

Constraints

• Up to 10^5 users and referrals.
• Each user has at most one referrer, so the network is a forest.

Clarifying questions

• Can a user be referred more than once? What should invalid referrals do?
• Must reach queries be fast after many inserts, or is a traversal per query acceptable?
• Is reach counted over all levels, or only a few?
• In the growth model, is "expected" exact, or is a simulation estimate acceptable?

What a strong answer covers

• Storing a parent map and a children map; the cycle check by walking up from referrer to see whether candidate is an ancestor (O(depth)).
• Reach by DFS, memoized or maintained incrementally (adding a referral adds 1 + reach(candidate) to every ancestor); top-k with a heap or a sort.
• Flow centrality in a forest as (number of ancestors) × (number of descendants), and why that holds.
• Growth by linearity of expectation: track the expected number of active referrers by how many referrals they have left, day by day, instead of simulating; compare with a Monte Carlo check.
• Tests for each rejection rule and for the small example above.

Follow-ups

• Choose k referrers whose combined reach (without double counting) is largest. Why does a greedy choice work well here?
• The growth target must be met by a deadline. What is the smallest p that achieves it (binary search)?
• Users can now be referred by several people, so the network is a DAG. What changes?