How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a easy difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at Roblox.

What role is this question designed for?

This question is commonly asked for Data Scientist candidates at Roblox during technical interviews.

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.

Input: ([(1, 2), (1, 3), (2, 3)], 1)

Expected Output: 2

Explanation: Although 1 directly follows 3, the longest non-repeating path is 1 -> 2 -> 3.

Input: ([(1, 2), (1, 3), (2, 4), (4, 5), (3, 6)], 1)

Expected Output: 3

Explanation: The longest path is 1 -> 2 -> 4 -> 5, which has 3 edges.

Input: ([(2, 3), (3, 4)], 1)

Expected Output: 0

Explanation: User 1 has no outgoing follow edges.

Input: ([(1, 2), (2, 3), (3, 1), (3, 4), (4, 5)], 1)

Expected Output: 4

Explanation: The cycle edge 3 -> 1 is ignored, but the path 1 -> 2 -> 3 -> 4 -> 5 has 4 edges.

Input: ([(-1, 0), (-1, 0), (0, 2), (2, 0), (0, 3)], -1)

Expected Output: 2

Explanation: Duplicate edges do not change the result. The longest valid paths are -1 -> 0 -> 2 and -1 -> 0 -> 3, each with depth 2.

Input: ([], 42)

Expected Output: 0

Explanation: There are no follow relationships, so no layers are reachable.

Solution

def solution(follows, start_id):
    from functools import lru_cache

    adjacency_raw = {}
    for follower, followee in follows:
        if follower not in adjacency_raw:
            adjacency_raw[follower] = set()
        adjacency_raw[follower].add(followee)

    reachable = set()

    def collect_reachable(user):
        if user in reachable:
            return
        reachable.add(user)
        for nxt in adjacency_raw.get(user, ()):
            collect_reachable(nxt)

    collect_reachable(start_id)

    id_to_index = {user: i for i, user in enumerate(reachable)}
    adjacency = [[] for _ in range(len(reachable))]

    for user in reachable:
        user_index = id_to_index[user]
        for nxt in adjacency_raw.get(user, ()):
            if nxt in id_to_index:
                adjacency[user_index].append(id_to_index[nxt])

    start_index = id_to_index[start_id]

    @lru_cache(maxsize=None)
    def dfs(user_index, visited_mask):
        best = 0
        for nxt_index in adjacency[user_index]:
            bit = 1 << nxt_index
            if visited_mask & bit:
                continue
            best = max(best, 1 + dfs(nxt_index, visited_mask | bit))
        return best

    return dfs(start_index, 1 << start_index)

Time complexity: O(E * 2^V), where V is the number of unique users reachable from start_id and E is the number of reachable follow edges.. Space complexity: O(V * 2^V) for memoization, plus O(E) for the adjacency list..

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.

Quick Overview

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.