Find maximum follow depth using recursion
RobloxData Scientist · Technical ScreenLast updated
This question evaluates a candidate's competency with recursion, directed graph traversal, cycle detection, and memoization when computing longest-path depths in social-network-style follow graphs.
You are given a directed follows relationship representing a social graph:
- Each record
(follower_id, followee_id)meansfollower_idfollowsfollowee_id. - Treat this as a directed graph.
Task
Implement a function that, given:
- a list of follow edges
follows = [(follower_id, followee_id), ...] - a starting user
start_id
returns the maximum number of follow “layers” reachable from start_id by repeatedly following the next user.
Formally, compute the length of the longest directed path starting at start_id:
- Layer 1: users directly followed by
start_id - Layer 2: users followed by those users
- …
Return the maximum layer count reachable.
Requirements / edge cases
- Use recursion (you may add memoization).
- Handle cycles (e.g., A→B→C→A) without infinite recursion.
- If
start_idfollows nobody, return0.
Example
If edges are: 1→2, 2→3, 3→4, then max_depth(1) = 3 (layers: {2}, {3}, {4}).
If edges are: 1→2, 2→1, then max_depth(1) = 1 (cycle; do not loop forever).
Solution walkthrough is for members
Get the full walkthrough with reference code and complexity analysis, plus Kitty Coach at 300 messages a day. Hints, the code runner and community answers stay free.