PracHub
QuestionsPremiumLearningGuidesCheatsheetNEWCoaches

Quick Overview

This question evaluates skills in modeling and manipulating directed acyclic graphs, implementing graph-based ranking metrics (reachability and flow centrality), and reasoning about stochastic growth and expected-value computations, testing competencies in graph algorithms, data structures, combinatorics, and probabilistic modeling within the Coding & Algorithms domain. It is commonly asked because it probes both practical implementation ability and algorithmic thinking—requiring deterministic traversal and ranking logic as well as conceptual understanding of probabilistic growth models and trade-offs between exact dynamic programming, approximations, and simulation—thereby assessing both practical application and conceptual understanding.

  • medium
  • Mercor
  • Coding & Algorithms
  • Machine Learning Engineer

Implement a Referral Network

Company: Mercor

Role: Machine Learning Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Onsite

Implement a referral network in three parts. You are building an in-memory model of a directed referral graph. An edge `A -> B` means user `A` referred user `B`. A user may refer multiple people. Unless you document a different assumption, treat the graph as directed and acyclic, and reject any referral that would create a cycle. ### Part 1: Core referral graph Implement APIs to: - Add a user if they do not already exist. - Add a referral from a referrer to a referred candidate. - Retrieve a user's direct referrals. - Retrieve a user's direct referrer or referrers, depending on your chosen model. ### Part 2: Ranking functions Build on Part 1 and implement two ranking functions: 1. **Top K by total candidate reach** - For each user, count the number of unique downstream candidates reachable from that user through one or more referral edges. - Include both direct and indirect referrals. - Return the top `k` users by this count, with deterministic tie-breaking. 2. **Top K by flow centrality** - Define a referral path as any directed path following referral edges from an upstream user to a downstream user. - A user's flow centrality is the number of referral paths in which that user appears. State whether your implementation counts endpoints or only intermediate nodes, and be consistent. - Return the top `k` users by flow centrality, with deterministic tie-breaking. ### Part 3: Expected network growth Implement a function that estimates the expected network size after `N` days. Assumptions: - At the start of each day, every active person in the network independently has probability `p` of making one successful referral that day. - A successful referral adds exactly one new person to the network. - A newly referred person becomes active starting the next day. - Each person can make at most `10` successful referrals over their lifetime. Your function should return the expected total number of users after `N` days. You may use an exact dynamic-programming approach, a deterministic approximation, or a Monte Carlo simulation, but you should clearly explain the trade-offs and edge cases.

Quick Answer: This question evaluates skills in modeling and manipulating directed acyclic graphs, implementing graph-based ranking metrics (reachability and flow centrality), and reasoning about stochastic growth and expected-value computations, testing competencies in graph algorithms, data structures, combinatorics, and probabilistic modeling within the Coding & Algorithms domain. It is commonly asked because it probes both practical implementation ability and algorithmic thinking—requiring deterministic traversal and ranking logic as well as conceptual understanding of probabilistic growth models and trade-offs between exact dynamic programming, approximations, and simulation—thereby assessing both practical application and conceptual understanding.

Part 1: Process Core Referral Graph Operations

You are given a sequence of commands for an in-memory referral network. Model the network as a directed acyclic graph with the additional rule that each user may have at most one direct referrer. Process every command in order and return the result of each command. Supported commands: - ('ADD_USER', user): add the user if missing. - ('ADD_REFERRAL', referrer, referred): add a directed edge referrer -> referred. - ('GET_DIRECT_REFERRALS', user): return the user's direct referrals. - ('GET_REFERRER', user): return the user's direct referrer. Rules: - 'ADD_REFERRAL' automatically creates missing users before trying to add the edge. - Reject the referral if it is a self-loop, duplicates an existing edge, gives the referred user a second direct referrer, or would create a cycle. - If a referral is rejected, any newly auto-created users still remain in the network. - 'GET_DIRECT_REFERRALS' must return names sorted lexicographically. - For an unknown user, 'GET_DIRECT_REFERRALS' returns [] and 'GET_REFERRER' returns None.

Constraints

  • 0 <= len(operations) <= 10^4
  • User IDs are non-empty strings of length at most 50
  • Each user may have at most one direct referrer
  • The graph must remain acyclic after every successful referral

Examples

Input: ([('ADD_USER', 'A'), ('ADD_USER', 'B'), ('ADD_REFERRAL', 'A', 'B'), ('GET_DIRECT_REFERRALS', 'A'), ('GET_REFERRER', 'B')],)

Expected Output: [True, True, True, ['B'], 'A']

Explanation: Basic add/query flow.

Input: ([('ADD_USER', 'A'), ('ADD_USER', 'A'), ('ADD_REFERRAL', 'A', 'B'), ('ADD_REFERRAL', 'A', 'B'), ('GET_DIRECT_REFERRALS', 'A'), ('GET_REFERRER', 'B')],)

Expected Output: [True, False, True, False, ['B'], 'A']

Explanation: Adding an existing user returns False, and a duplicate referral is rejected.

Input: ([('ADD_REFERRAL', 'A', 'B'), ('ADD_REFERRAL', 'C', 'B'), ('GET_REFERRER', 'B'), ('GET_DIRECT_REFERRALS', 'C')],)

Expected Output: [True, False, 'A', []]

Explanation: B already has direct referrer A, so C -> B is rejected. C still exists because users are auto-created.

Input: ([('ADD_REFERRAL', 'A', 'B'), ('ADD_REFERRAL', 'B', 'C'), ('ADD_REFERRAL', 'C', 'A'), ('GET_DIRECT_REFERRALS', 'C'), ('GET_REFERRER', 'A')],)

Expected Output: [True, True, False, [], None]

Explanation: C -> A would create a cycle A -> B -> C -> A, so it is rejected.

Input: ([('GET_DIRECT_REFERRALS', 'X'), ('GET_REFERRER', 'X')],)

Expected Output: [[], None]

Explanation: Edge case: queries for an unknown user.

Hints

  1. Keep two hash maps: one from user -> set of direct referrals, and one from user -> direct referrer.
  2. To reject a cycle when adding referrer -> referred, check whether referrer is already reachable from referred.

Part 2: Rank Users in a Referral DAG

You are given all users in a referral network and a list of directed referral edges u -> v. The graph is intended to be a DAG. Compute two rankings: 1. Top K by total candidate reach - For each user, count how many unique downstream users are reachable through one or more referral edges. - Count both direct and indirect referrals. 2. Top K by flow centrality - A referral path is any directed path of length at least 1. - In this problem, a user's flow centrality counts how many referral paths contain that user as an intermediate node only, not as a start or end node. Tie-breaking: - Higher score ranks first. - If scores tie, smaller user ID in lexicographic order ranks first. Return both rankings. If the given edges contain a cycle, return {'reach': [], 'flow': []}.

Constraints

  • 0 <= len(users) <= 500
  • 0 <= len(referrals) <= 5000
  • User IDs are strings and are distinct in the users list
  • Duplicate edges may appear in input; treat them as one edge
  • If the graph is not acyclic, return {'reach': [], 'flow': []}

Examples

Input: (['A', 'B', 'C', 'D'], [('A', 'B'), ('A', 'C'), ('B', 'D'), ('C', 'D')], 3)

Expected Output: {'reach': [('A', 3), ('B', 1), ('C', 1)], 'flow': [('B', 1), ('C', 1), ('A', 0)]}

Explanation: A can reach B, C, and D. B and C each appear as an intermediate node in exactly one path.

Input: (['A', 'B', 'C'], [('A', 'B'), ('B', 'C')], 5)

Expected Output: {'reach': [('A', 2), ('B', 1), ('C', 0)], 'flow': [('B', 1), ('A', 0), ('C', 0)]}

Explanation: In the chain A -> B -> C, only B is an intermediate node on path A -> B -> C.

Input: (['A', 'B', 'C', 'D'], [('A', 'B')], 4)

Expected Output: {'reach': [('A', 1), ('B', 0), ('C', 0), ('D', 0)], 'flow': [('A', 0), ('B', 0), ('C', 0), ('D', 0)]}

Explanation: Edge case with isolated users and no intermediate nodes.

Input: ([], [], 2)

Expected Output: {'reach': [], 'flow': []}

Explanation: Empty network.

Input: (['A', 'B', 'C', 'D', 'E'], [('A', 'B'), ('A', 'C'), ('B', 'D'), ('C', 'D'), ('D', 'E')], 2)

Expected Output: {'reach': [('A', 4), ('B', 2)], 'flow': [('D', 4), ('B', 2)]}

Explanation: D lies in four longer referral paths as an intermediate node; A reaches everyone else.

Hints

  1. For total reach in a DAG, process nodes in reverse topological order and accumulate descendant sets.
  2. For intermediate-node flow centrality, count how many paths end at a node from above and how many start from it below; multiplying those two counts gives the number of full paths where it is in the middle.

Part 3: Expected Referral Network Growth

Start with initial_users active users on day 0. For each of the next N days: - Every active user independently makes one successful referral with probability p. - A successful referral creates exactly one new user. - A newly created user becomes active starting the next day. - Each user can make at most 10 successful referrals over their entire lifetime. Return the expected total number of users after N days, rounded to 6 decimal places. Implement an exact deterministic dynamic-programming solution. The key idea is to track expected counts of users by how many successful referrals they have already made (0 through 10).

Constraints

  • 0 <= initial_users <= 10^6
  • 0 <= days <= 10^5
  • 0.0 <= p <= 1.0
  • Each user can make at most 10 successful referrals over their lifetime

Examples

Input: (1, 0, 0.3)

Expected Output: 1.0

Explanation: Edge case: after 0 days, the network size is unchanged.

Input: (3, 10, 0.0)

Expected Output: 3.0

Explanation: If p = 0, nobody ever refers anyone.

Input: (1, 2, 0.5)

Expected Output: 2.25

Explanation: Expected births are 0.5 on day 1 and 0.75 on day 2, for a total expected size of 2.25.

Input: (2, 1, 0.25)

Expected Output: 2.5

Explanation: Two active users produce an expected 2 * 0.25 = 0.5 new users on day 1.

Input: (1, 11, 1.0)

Expected Output: 2047.0

Explanation: With p = 1, growth doubles each day until the original user hits the 10-referral lifetime cap; on day 11 only that original user is capped.

Hints

  1. Track 11 states: how many successful referrals a user has already made, from 0 to 10.
  2. By linearity of expectation, the expected number of users moving from state s to s+1 on a day is simply p * state[s].
Last updated: May 15, 2026

Loading coding console...

PracHub

Master your tech interviews with 7,500+ real questions from top companies.

Product

  • Questions
  • Learning Tracks
  • Interview Guides
  • Resources
  • Premium
  • For Universities
  • Student Access

Browse

  • By Company
  • By Role
  • By Category
  • Topic Hubs
  • SQL Questions
  • Compare Platforms
  • Discord Community

Support

  • support@prachub.com
  • (916) 541-4762

Legal

  • Privacy Policy
  • Terms of Service
  • About Us

© 2026 PracHub. All rights reserved.