Define and Calculate Employee Referral Counts

Problem Statement

At Robinhood, referral programs reward users and employees for bringing new members onto the platform. Given a list of referral pairs where each pair (referrer, referred) indicates that referrer referred referred, calculate both the direct and total downstream referral counts for every employee present in the data.

• Direct referral count: The number of unique individuals directly referred by this employee.
• Downstream referral count: The total number of unique individuals reachable via one or more referral steps originating from this employee, excluding the employee themselves.

Due to potential data anomalies or co-referrals:

1. The input may contain duplicate referral pairs.
2. A person can be referred by multiple people (converging paths).
3. Referral loops/cycles may exist (e.g., Alice refers Bob, and Bob refers Alice).
4. An employee must never be counted as their own referral, even if reachable via a cycle.
5. Any employee appearing in either position (referrer or referred) must be included in the output.

Function Signature

from typing import List, Tuple, Dict

def calculate_referral_counts(referrals: List[Tuple[str, str]]) -> Dict[str, Dict[str, int]]:
    pass

Input & Output Format

• Input: referrals, a list of tuples (referrer, referred) where each element is a string representing an employee ID.
• Output: A dictionary mapping each employee ID to a dictionary with keys "direct" and "downstream".

Constraints

• 0 <= len(referrals) <= 5,000
• Number of unique employees N <= 1,000
• Employee IDs are non-empty strings of alphanumeric characters.

Examples

Example 1: Converging Paths

referrals = [
    ("A", "B"),
    ("A", "C"),
    ("B", "D"),
    ("C", "D"),
]

output = calculate_referral_counts(referrals)
# Result:
# {
#     "A": {"direct": 2, "downstream": 3},  # downstream: B, C, D
#     "B": {"direct": 1, "downstream": 1},  # downstream: D
#     "C": {"direct": 1, "downstream": 1},  # downstream: D
#     "D": {"direct": 0, "downstream": 0}
# }

Example 2: Cycles and Duplicates

referrals = [
    ("A", "B"),
    ("B", "C"),
    ("C", "A"),
    ("A", "B"),  # duplicate
    ("C", "D")
]

output = calculate_referral_counts(referrals)
# Result:
# {
#     "A": {"direct": 1, "downstream": 3},  # downstream: B, C, D (A excluded)
#     "B": {"direct": 1, "downstream": 3},  # downstream: C, D, A (B excluded)
#     "C": {"direct": 2, "downstream": 3},  # downstream: A, B, D (C excluded)
#     "D": {"direct": 0, "downstream": 0}
# }

Edge Cases

• Empty input list should return an empty dictionary.
• Self-referrals like ("A", "A"): direct and downstream counts for A should both be 0.
• Disconnected components in the graph.