Social Network Best-Friend Recommendation

Problem: Social Network Best-Friend Recommendation You are given connection data from a social network. Each record has the format: user1 user2 likes It means there is a directed connection from user1 to user2, and user1 has given likes likes to user2. Implement a preprocessing function transform() and support the following queries: GET u v Return the number of likes from u to v. If the connection (u, v) does not exist, return None. Important: if the connection exists and the like count is 0, return 0, not None. BEST u Return the user connected from u with the maximum like count, i.e. u's best friend. If u has no outgoing connections, return None. If there is a tie in like count, return the lexicographically smallest username. RECOMMEND u Use the “best friend of best friend” rule: Find u's best friend, denoted as b. Find b's best friend, denoted as c. Return c. If any step does not exist, return None. If c == u, return None to avoid recommending the user back to themselves. Design the data structures so that: GET u v is O(1). After preprocessing, BEST u is as close to O(1) as possible. Discuss how to handle a celebrity user with millions of friends without scanning all friends for every query. Input Format m q user1 user2 likes ... m lines query ... q lines Each query is one of: GET u v BEST u RECOMMEND u Output Format Print one line for each query. If the answer does not exist, print: None Constraints 1 <= m, q <= 200000 0 <= likes <= 10^9 Usernames are strings without spaces Each (user1, user2) appears at most once Example Input: 5 6 A B 10 A C 5 B D 7 B A 1 D E 3 GET A B GET A D GET A C BEST A BEST C RECOMMEND A Output: 10 None 5 B None D Example Input 5 6 A B 10 A C 5 B D 7 B A 1 D E 3 GET A B GET A D GET A C BEST A BEST C RECOMMEND A Output 10 None 5 B None D