Katkat

Find maximum follow depth using recursion

RobloxData Scientist · Technical Screen

Last 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) 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).