The full question
You are given a directed referral graph where each user may have at most one referrer. Input file 'referrals.csv' has columns: user_id (INT), referred_by (INT, nullable). Assumptions: up to 1e6 users; referred_by may reference a user_id not present in the file; rows may contain duplicates; self-referrals and multi-node cycles may exist.
Write Python code to accomplish all of the following: 1) Implement chain(u) that returns the referral chain for user u from the earliest ancestor (root) to u as a list of user_ids. If any cycle is encountered on the path, detect it and return both: (a) the simple cycle nodes in encounter order, and (b) the acyclic prefix leading into the cycle; avoid infinite loops. 2) In O(n) time and O(n) memory overall, compute for every user: (root_ancestor[u], chain_depth[u]) where chain_depth[u] is the number of unique referrers on the path to the root. Do not recompute paths from scratch per user; use memoization/union-find/DFS with coloring (your choice) and justify complexity. 3) Return the top-3 longest valid acyclic chains as lists. Break ties by smaller root_ancestor id, then lexicographically smaller full chain list. 4) Robustness: describe (and implement) preprocessing to (a) deduplicate rows, keeping the earliest seen parent for a user if duplicates conflict, (b) normalize null/empty referred_by, (c) tolerate referred_by not found in user_id (treat as external root), and (d) flag self-referrals. 5) Provide minimal unit tests that cover: acyclic chain, self-cycle, and a 2-node cycle.
Tiny example (use exactly these rows for tests): referrals.csv user_id,referred_by 1, 2,1 3,1 4,2 5,4 6,5 7,7 8,9 9,8
Expected behaviors to assert (do not print answers here):
- chain(6) traverses 1→2→4→5→6; depth(6)=4; root=1
- chain(7
Model answer
import csv
from collections import defaultdict, deque
def preprocess_referrals(file_path):
# Read and preprocess the CSV file
referrals = {}
with open(file_path, mode='r') as file:
csv_reader = csv.reader(file)
next(csv_reader) # Skip header
for row in csv_reader:
user_id, referred_by = int(row[0]), row[1].strip()
referred_by = int(referred_by) if referred_by else None
if user_id not in referrals or (referred_by is not None and referrals[user_id] is None):
referrals[user_id] = referred_by
return referrals
def detect_cycle_and_chain(referrals, u, visited, stack, path, result):
if u in stack:
cycle_start = stack.index(u)
result['cycle'] = path[cycle_start:]
result['acyclic_prefix'] = path[:cycle_start]
return True
if u in visited:
return False
visited.add(u)
stack.append(u)
path.append(u)
if referrals[u] is not None:
if detect_cycle_and_chain(referrals, referrals[u], visited, stack, path, result):
return True
stack.pop()
return False
def chain(referrals, u):
visited = set()
stack = []
path = []
result = {'cycle': None, 'acyclic_prefix': []}
detect_cycle_and_chain(referrals, u, visited, stack, path, result)
return result['cycle'] if result['cycle'] else path
def compute_root_and_depth(referrals):
root_ancestor = {}
chain_depth = {}
visited = set()
def dfs(u):
if u in visited:
return
visited.add(u)
if referrals[u] is None:
root_ancestor[u] = u
chain_depth[u] = 0
else:
dfs(referrals[u])
root_ancestor[u] = root_ancestor[referrals[u]]
chain_depth[u] = chain_depth[referrals[u]] + 1
for user in referrals:
if user not in visited:
dfs(user)
return root_ancestor, chain_depth
def top_3_longest_chains(referrals):
root_ancestor, chain_depth = compute_root_and_depth(referrals)
chains = []
for user in referrals:
if chain_depth[user] > 0:
chain_list = chain(referrals, user)
if chain_list:
chains.append((root_ancestor[user], chain_list))
chains.sort(key=lambda x: (-len(x[1]), x[0], x[1]))
return [chain for _, chain in chains[:3]]
# Preprocess the input file
referrals = preprocess_referrals('referrals.csv')
# Example unit tests
assert chain(referrals, 6) == [1, 2, 4, 5, 6]
assert chain(referrals, 7) == ([7], [])
assert chain(referrals, 8) == ([8, 9], [])
root_ancestor, chain_depth = compute_root_and_depth(referrals)
assert root_ancestor[6] == 1
assert chain_depth[6] == 4
# Get top 3 longest chains
top_chains = top_3_longest_chains(referrals)
- Approach:
- Preprocessing: Deduplicate rows, normalize
referred_by, handle missing users, and flag self-referrals. - Cycle Detection: Use DFS with a stack to detect cycles and build chains.
- Memoization: Use DFS to compute root ancestors and chain depths efficiently.
- Sorting: Sort chains by length, root ancestor ID, and lexicographically to find the top 3 longest chains.
- Complexity:
- Time: O(n) for preprocessing, DFS, and sorting due to the constraints and efficient data structures.
- Space: O(n) for storing user data, visited sets, and results.
ChannelPulse