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.

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.

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.

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