Count Referral Descendants
Company: Robinhood
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
Quick Answer: This question evaluates graph and tree reasoning, algorithmic aggregation for computing descendant counts, and system-level thinking for incremental updates and recursion-depth mitigation.
Part 1: Compute Total Referral Descendant Counts
Constraints
- 0 <= len(referrals) <= 100000
- User IDs are non-empty strings.
- Each referred user has at most one direct referrer.
- The referral graph is acyclic.
- Referral pairs are unique.
Examples
Input: ([('A', 'B'), ('A', 'C'), ('B', 'D'), ('B', 'E'), ('C', 'F')],)
Expected Output: {'A': 5, 'B': 2, 'C': 1, 'D': 0, 'E': 0, 'F': 0}
Explanation: A reaches B, C, D, E, and F. B reaches D and E. C reaches F.
Input: ([],)
Expected Output: {}
Explanation: No users appear in the input, so the result is empty.
Input: ([('root', 'child')],)
Expected Output: {'root': 1, 'child': 0}
Explanation: root has one direct referral, and child has none.
Input: ([('A', 'B'), ('C', 'D'), ('C', 'E')],)
Expected Output: {'A': 1, 'B': 0, 'C': 2, 'D': 0, 'E': 0}
Explanation: The input contains two separate referral trees.
Input: ([('A', 'B'), ('B', 'C'), ('C', 'D')],)
Expected Output: {'A': 3, 'B': 2, 'C': 1, 'D': 0}
Explanation: This is a chain, so each earlier user reaches all later users.
Hints
- A user's answer is the sum of 1 plus the descendant count of each direct child.
- Process children before parents, for example with postorder DFS or an explicit stack.
Part 2: Find the Top 3 Users by Referral Count
Constraints
- 0 <= len(referrals) <= 100000
- User IDs are non-empty strings.
- Each referred user has at most one direct referrer.
- The referral graph is acyclic.
- Referral pairs are unique.
Examples
Input: ([('A', 'B'), ('A', 'C'), ('B', 'D'), ('B', 'E'), ('C', 'F')],)
Expected Output: ['A', 'B', 'C']
Explanation: Counts are A=5, B=2, C=1, and leaves=0.
Input: ([],)
Expected Output: []
Explanation: No users appear, so there are no top users.
Input: ([('A', 'B')],)
Expected Output: ['A', 'B']
Explanation: There are only two users. A has count 1 and B has count 0.
Input: ([('A', 'D'), ('B', 'E'), ('C', 'F')],)
Expected Output: ['A', 'B', 'C']
Explanation: A, B, and C all have count 1, so lexicographic order breaks the tie.
Input: ([('A', 'B'), ('B', 'C'), ('D', 'E'), ('F', 'G')],)
Expected Output: ['A', 'B', 'D']
Explanation: Counts are A=2, B=1, D=1, F=1, and leaves=0. B beats D and F by lexicographic order; D beats F.
Hints
- First compute each user's descendant count using a postorder traversal.
- Because only 3 users are needed, you do not need to sort every user by count.
Part 3: Count Descendants Without Recursion
Constraints
- 0 <= len(referrals) <= 200000
- User IDs are non-empty strings.
- Each referred user has at most one direct referrer.
- The referral graph is acyclic.
- Referral depth may exceed the language recursion limit, so the solution must not rely on recursion.
Examples
Input: ([('A', 'B'), ('A', 'C'), ('B', 'D'), ('B', 'E'), ('C', 'F')], 'A')
Expected Output: 5
Explanation: A reaches B, C, D, E, and F.
Input: ([('A', 'B'), ('A', 'C'), ('B', 'D'), ('B', 'E'), ('C', 'F')], 'B')
Expected Output: 2
Explanation: B reaches D and E.
Input: ([], 'A')
Expected Output: 0
Explanation: There are no referral edges.
Input: ([('A', 'B'), ('A', 'C')], 'C')
Expected Output: 0
Explanation: C is a leaf user.
Input: ([('0', '1'), ('1', '2'), ('2', '3'), ('3', '4'), ('4', '5'), ('5', '6'), ('6', '7'), ('7', '8'), ('8', '9'), ('9', '10')], '0')
Expected Output: 10
Explanation: The start user is at the head of a chain of 10 descendants.
Hints
- Build an adjacency list from each referrer to their direct referred users.
- Use an explicit stack or queue instead of recursive function calls.
Part 4: Incremental Referral Count Queries
Constraints
- 0 <= len(operations) <= 100000
- User IDs are non-empty strings.
- Every add operation is valid: the referred user has no current direct referrer, the edge is not a duplicate, and adding it does not create a cycle.
- Users may appear for the first time in either add or query operations.
- The total number of ancestor links walked across all add operations is at most 300000.
Examples
Input: ([('query', 'A'), ('add', 'A', 'B'), ('query', 'A'), ('query', 'B')],)
Expected Output: [0, 1, 0]
Explanation: Initially A is unknown, so its count is 0. After A refers B, A has one descendant and B has none.
Input: ([('add', 'B', 'C'), ('add', 'B', 'D'), ('query', 'B'), ('add', 'A', 'B'), ('query', 'A'), ('query', 'B')],)
Expected Output: [2, 3, 2]
Explanation: B first has descendants C and D. When A refers B, A gains B plus B's two descendants.
Input: ([('add', 'A', 'B'), ('add', 'B', 'C'), ('query', 'A'), ('add', 'C', 'D'), ('query', 'A'), ('query', 'B'), ('query', 'C'), ('query', 'D')],)
Expected Output: [2, 3, 2, 1, 0]
Explanation: Adding D under C increases the counts of C, B, and A.
Input: ([('add', 'X', 'Y'), ('add', 'A', 'B'), ('query', 'X'), ('query', 'A'), ('query', 'Z')],)
Expected Output: [1, 1, 0]
Explanation: X and A are separate roots. Unknown user Z has count 0.
Input: ([],)
Expected Output: []
Explanation: No operations means no query answers.
Hints
- When adding referrer -> referredUser, referrer and all ancestors of referrer gain the entire subtree rooted at referredUser.
- Maintain parent pointers and current descendant counts so that queries are dictionary lookups.