Top K Users by Distinct Contacts
Google● MediumFULLTIMEPHONE SCREENProblem statement
Each row of messages records one undirected message between two user IDs. Return at most k users ordered by descending number of distinct contacts, then by lexicographically smaller user ID.
A repeated pair contributes one contact to each endpoint, regardless of direction. A self-message adds its user to the observed user set but adds no contact.
If fewer than k users appear, return every observed user. Return an empty array when no user appears.
Function
topKActiveUsers(messages: String[][], k: int) → String[]Examples
Example 1
messages = [["Ada","Bob"],["Ada","Cara"],["Bob","Cara"],["Ada","Drew"],["Bob","Ada"]]k = 2return = ["Ada","Bob"]Ada has three contacts; Bob and Cara tie at two, so Bob wins the lexical tie.
Example 2
messages = [["zoe","zoe"],["amy","bob"],["bob","amy"]]k = 5return = ["amy","bob","zoe"]Repeated pairs count once, the self-message adds no contact, and fewer than k users are returned.
Example 3
messages = []k = 3return = []No users are present.
Constraints
0 <= messages.length <= 200000.- Every row contains exactly two nonempty case-sensitive user IDs.
- Each ID has at most 100 characters, and the combined input length is at most
2 * 10^6. 1 <= k <= 200000.