Problem Description

You are tasked with analyzing a directed referral graph where each user can have at most one referrer. The input is provided as a CSV file named 'referrals.csv', containing two columns: user_id (integer) and referred_by (integer, nullable).

Assumptions and Constraints:

• The dataset may contain up to 1 million (1e6) users.
• A referred_by user ID might not be present in the user_id column; such cases should be treated as an external root.
• The input file may contain duplicate rows.
• The graph can contain self-referrals (a user referring themselves) and multi-node cycles.

Requirements

Implement Python code to fulfill the following requirements:

1. chain(u) Function:

   • Implement a function chain(u) that returns the referral chain for a given user u. The chain should be a list of user_ids, ordered from the earliest ancestor (root) to u.
   • If a cycle is encountered on the path to u, detect it and return two components:
     • The simple cycle nodes, in the order they are encountered.
     • The acyclic prefix leading into the cycle.
   • Ensure the function avoids infinite loops when traversing cycles.

2. Global Chain Analysis (O(N) Time & Memory):

   • Compute for every user u a tuple (root_ancestor[u], chain_depth[u]).
   • root_ancestor[u] is the ID of the ultimate root ancestor for user u.
   • chain_depth[u] is the number of unique referrers on the path from u to its root.
   • This computation must be performed in overall O(N) time and O(N) memory, where N is the number of users.
   • Justify your chosen approach (e.g., memoization, Union-Find, DFS with coloring) and its complexity. Avoid recomputing paths from scratch for each user.

3. Top-3 Longest Acyclic Chains:

   • Identify and return the top-3 longest valid acyclic referral chains as lists of user IDs.
   • In case of ties in length, break them by selecting the chain with the smaller root_ancestor ID first. If still tied, use lexicographically smaller full chain lists.

4. Robust Preprocessing:

   • Describe and implement preprocessing steps for the input data to ensure robustness:
     • Deduplication: Handle duplicate rows. If conflicting referred_by values exist for the same user_id across duplicates, keep the earliest seen parent.
     • Null Normalization: Normalize null or empty referred_by values.
     • External Roots: Gracefully handle referred_by IDs that do not appear as user_ids in the dataset, treating them as external roots.
     • Self-Referrals: Flag or identify self-referrals.

5. Unit Tests:

   • Provide minimal unit tests that cover the following scenarios:
     • A standard acyclic chain.
     • A self-referral cycle.
     • A 2-node cycle.
   • Use the exact example data provided below for these tests.

Example Data

referrals.csv content:

user_id,referred_by
1,
2,1
3,1
4,2
5,4
6,5
7,7
8,9
9,8

Expected Behaviors (for testing)

• chain(6) should traverse 1 → 2 → 4 → 5 → 6. The depth(6) should be 4, and the root_ancestor should be 1.
• chain(7) should report a self-cycle at user 7.
• chain(8) should report the 2-node cycle involving users 8 and 9.