Implement a Referral Network

Problem Statement

You are tasked with building a referral tracking system for a talent platform. When existing users invite new candidates, directed referral links are established. To prevent fraudulent referral rings, the network must remain a Directed Acyclic Graph (DAG) at all times.

Implement the ReferralNetwork class with the following methods:

• add_referral(referrer: str, referee: str) -> bool: Attempts to add a directed edge from referrer to referee. If adding this edge would create a cycle or if the edge already exists, reject the operation and return False. Otherwise, record the referral and return True. If either user does not exist in the network yet, register them.

• get_reach(user_id: str, max_depth: int) -> int: Returns the number of distinct downstream users reachable from user_id within at most max_depth referral hops. The user themselves is not included in the count. If user_id does not exist or max_depth float: Calculates the expected total commission generated by the downstream network of user_id. Each distinct user v reachable from user_id at shortest path distance d >= 1 independently converts with probability prob. If converted, user v yields a value of base_value * (decay ** (d - 1)). By linearity of expectation, the total expected value is the sum of expected values across all reachable downstream users. If user_id has no downstream referrals or is not in the network, return 0.0.

Interface

class ReferralNetwork:
    def __init__(self):
        pass

    def add_referral(self, referrer: str, referee: str) -> bool:
        pass

    def get_reach(self, user_id: str, max_depth: int) -> int:
        pass

    def expected_network_value(self, user_id: str, base_value: float, prob: float, decay: float) -> float:
        pass

Constraints

• Total number of users N = 0
• 0.0 = 0.0
• User identifiers are non-empty strings of alphanumeric characters.

Examples

Example 1

network = ReferralNetwork()
assert network.add_referral("A", "B") == True
assert network.add_referral("A", "C") == True
assert network.add_referral("B", "D") == True
assert network.add_referral("C", "D") == True
assert network.add_referral("D", "A") == False  # Creates cycle A -> B/C -> D -> A

# Reachability
assert network.get_reach("A", 1) == 2   # B, C
assert network.get_reach("A", 2) == 3   # B, C, D

# Expected Value
# Distances from A: B (d=1), C (d=1), D (shortest d=2)
# E[B] = 0.5 * 100 * (0.5 ** 0) = 50.0
# E[C] = 0.5 * 100 * (0.5 ** 0) = 50.0
# E[D] = 0.5 * 100 * (0.5 ** 1) = 25.0
# Total = 125.0
val = network.expected_network_value("A", base_value=100.0, prob=0.5, decay=0.5)
assert abs(val - 125.0) < 1e-6

Example 2

network = ReferralNetwork()
assert network.add_referral("Alice", "Bob") == True
assert network.add_referral("Alice", "Bob") == False  # Duplicate edge
assert network.get_reach("Unknown", 5) == 0
assert network.expected_network_value("Bob", 50.0, 0.8, 0.9) == 0.0

Edge Cases to Consider

• Disconnected users or querying IDs not present in the graph.
• Self-referrals (referrer == referee) should be rejected.
• Multiple paths of different lengths to the same referee (use the shortest path distance for expected_network_value).
• max_depth = 0 or negative values should return 0.