← Back
00:00

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 true when a new edge is added.
  • Return false for 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.

Idle