Define and Calculate Employee Referral Counts

You are given the list of employees and a list of referral records. Each record is a pair `(referrer, referred)`. Compute a referral count for every employee. Before you choose an algorithm, pin down what a referral count means and what shape the referral relationships can take. ```hint Distinguish people from paths In a graph where referral paths converge, adding up descendant counts can count the same person more than once. ``` ### Constraints and Clarifications - The record format beyond `(referrer, referred)` pairs, the direct-versus-downstream counting rule, the duplicate policy, and the graph structure are not specified. - Do not assume that every employee has exactly one referrer or that the records contain no duplicates or cycles. Label the interpretation you implement. ### Clarifying Questions - Does a count include only employees referred directly, or everyone downstream of them? - Can an employee have several referrers, and can duplicate records or cycles occur? - Should a downstream employee be counted once even if they are reachable along several paths? - Should employees with zero referrals appear in the output? ### What a Strong Answer Covers - An explicit counting rule, including self-exclusion and duplicate handling, plus the input validation it implies. - Correct algorithms for direct counts, for tree-shaped data, and for distinct downstream counts in general graphs. - Time and memory complexity for each case, with output that covers every relevant employee. ### Follow-up Questions - How would you keep counts current as new referrals arrive, instead of recomputing everything? - Why does a recurrence that is correct on a tree overcount on a general DAG? - How does your method scale to a few hundred thousand employees?