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:
(follower_id, followee_id)
means
follower_id
follows
followee_id
.
Implement a function that, given:
follows = [(follower_id, followee_id), ...]
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:
start_id
Return the maximum layer count reachable.
start_id
follows nobody, return
0
.
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).