Find maximum follow depth using recursion
Company: Roblox
Role: Data Scientist
Category: Coding & Algorithms
Difficulty: easy
Interview Round: Technical Screen
You are given a directed **follows** relationship representing a social graph:
- Each record `(follower_id, followee_id)` means `follower_id` follows `followee_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_id` follows nobody, return `0`.
### 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).
Quick Answer: 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 social graph represented by follow relationships. Each record (follower_id, followee_id) means follower_id follows followee_id. Implement a function solution(follows, start_id) that returns the maximum number of follow layers reachable from start_id by repeatedly following users.
The depth is the number of directed edges in the longest path starting at start_id. A direct follow has depth 1.
Cycles must not cause infinite recursion. For this problem, a valid path may not visit the same user more than once. If a follow edge would lead to a user already in the current path, ignore that edge for that path.
If start_id follows nobody, return 0.
Constraints
- 0 <= len(follows) <= 200
- User IDs are integers and may be negative.
- At most 20 unique users are reachable from start_id.
- Duplicate follow edges may appear and should be treated as the same relationship.
- Cycles may exist in the graph.
Examples
Input: ([(1, 2), (2, 3), (3, 4)], 1)
Expected Output: 3
Explanation: The longest path is 1 -> 2 -> 3 -> 4, which contains 3 follow edges.
Input: ([(1, 2), (2, 1)], 1)
Expected Output: 1
Explanation: From 1 you can follow to 2. The edge 2 -> 1 would revisit 1, so it is ignored.
Hints
- Build an adjacency list from each follower to the users they directly follow.
- Use recursive DFS with a visited set for the current path. If you memoize, the visited state must be part of the memoization key because cycles make the answer path-dependent.