Track the User with the Most Distinct Contacts: O(1) Query and Top-K for Changing k

Users send each other messages. Each message is between two users, and messages are **undirected**: a message between `A` and `B` counts as contact for both `A` and `B`. Design a class that supports two operations: - `register(a, b)` records a message between users `a` and `b`. - `most_active_user()` returns the user who has exchanged messages with the **largest number of distinct users**. The problem builds up over three parts. Throughout, analyze time and space complexity carefully, including the memory held by every per-user collection. ### Clarifying Questions - Does messaging the same person many times count once or many times toward a user's activity? - If several users tie for the most distinct contacts, which one should be returned? - What should `most_active_user()` return before any message has been registered? - Can a user message themselves, and does that count? - Which is more frequent, `register` or the queries? Can messages ever be removed? ### Part 1 — Register messages and find the most active user Implement `register(a, b)` and `most_active_user()`. Then state the time complexity of each operation and the space complexity of the whole structure. ```hint Count what is distinct A second message between the same two users must not raise either user's count, so decide what you must remember about each user to recognize a repeat contact. ``` #### What This Part Should Cover - Correct deduplication of repeat contacts, applied to both users in the message - Time complexity per operation - A space bound that accounts for every stored contact, including the worst case where many pairs of users have talked ### Part 2 — Make the query constant time Optimize `most_active_user()` to run in O(1) while keeping `register` efficient. ```hint What can a single message change? Look at how much one call to `register` can change the counts, and whose standing it can affect. ``` #### What This Part Should Cover - An invariant that keeps the answer current after every `register` - An argument for why the invariant holds, including ties - The cost this moves into `register` ### Part 3 — Top K with a changing k Add `top_k(k)`, which returns the `k` users with the most distinct contacts, ordered from most to fewest. The value of `k` can differ on every call, so a heap tied to one fixed `k` is not enough. Sorting all users on every call is the baseline to beat. ```hint Exploit how counts move Counts only ever grow, and each change is small. Ask what kind of structure could stay in order cheaply under exactly that kind of change. ``` #### Clarifying Questions for this Part - If `k` is larger than the number of users, should the result contain every user, or is that an error? - Must users with equal counts appear in a fixed order? #### What This Part Should Cover - The cost of the baselines: sorting, or building a size-`k` heap on every call - A structure whose query cost depends on `k` rather than on the number of users - The update cost in `register` and the extra space used - A tie rule that makes the output deterministic ### What a Strong Answer Covers - Duplicates, ties, and the empty state clarified before coding - Clean, working code for each part, with each part building on the previous one - Correct complexity analysis, especially the space held by the contact sets - A comparison of at least two approaches to top K, with the trade-offs stated - Clear narration of each step while coding ### Follow-up Questions - Messages can now be deleted, so counts can go down. Which of your structures still work, and what has to change? - The message volume no longer fits on one machine. How would you compute the global most active user and top K across shards? - Storing every contact set is too expensive. What would you give up to estimate distinct-contact counts in far less memory?