Referral Network Data Structure and Algorithms
Mercor interview questions · Hard · Coding round · reported 1× · 6 tests
Mercor interview reports describe a three-part graph problem built around a referral network.
Implement a class ReferralNetwork that supports:
- Building the referral graph.
- Ranking users by the number of unique downstream candidates they can reach.
- Ranking users by a deterministic flow centrality score.
- Estimating expected future network size under a simple stochastic growth model.
API
class ReferralNetwork {
addReferral(referrer: string, referee: string): boolean;
topKByCandidateCount(k: number): Array<{ user: string; count: number }>;
topKByFlowCentrality(k: number): Array<{ user: string; count: number }>;
estimateExpectedNetworkSize(days: number, p: number): number;
}
Part 1: Graph construction
addReferral(referrer, referee) inserts a directed edge referrer -> referee.
- Return
truewhen a new edge is added. - Return
falsefor self-referrals or duplicate edges. - Users are created automatically the first time they appear.
Part 2A: Candidate-count ranking
For each user, define their candidate count as the number of unique other users reachable by following one or more referral edges. Indirect referrals count, but the user themself does not.
Run your code with Ctrl+Enter to see results.