160. Find Most Active Users in Chat Logs

Find Most Active Users in Chat Logs

You are given a stream of chat events.

Each chat event contains:

sender: the user who sent the chat message
receiver: the user who received the chat message
currentTime: the time in seconds at which the chat happened

A user's activeness is defined as the number of distinct other users they have chatted with so far.

A chat between sender and receiver increases the activeness of both users only if they have not chatted with each other before.

Multiple chat events between the same two users do not increase their activeness again.

Implement a chat logs processor that can register chat events, return the most active user at the current moment, and return the top K active users at the current moment.

Class

`ChatLogsProcessor`

Initializes an empty chat logs processor.

Methods

`void registerEvent(String sender, String receiver, int currentTime)`

Registers a chat event between sender and receiver at the given currentTime in seconds.

The chat is considered bidirectional for activeness calculation.

This means:

receiver is counted as a distinct chat partner of sender
sender is counted as a distinct chat partner of receiver

If these two users have already chatted before, their activeness values do not change.

`String getMostActiveUser(int currentTime)`

Returns the user with the highest activeness at the given currentTime.

If multiple users have the same highest activeness, return the user with the lexicographically smallest id.

If no chat event has been registered yet, return an empty string.

`List<String> getMostActiveUsers(int k, int currentTime)`

Returns the top k active users at the given currentTime.

Users must be ordered by:

higher activeness first
lexicographically smaller id first when activeness is equal

If fewer than k users exist, return all existing users using the same ordering.

If no chat event has been registered yet, return an empty list.

Rules

Activeness is based on distinct chat partners, not total number of messages.
A chat between "alice" and "bob" counts once for "alice" and once for "bob".
Repeated chats between the same two users do not increase activeness again.
The chat relation is bidirectional.
currentTime values are given in non-decreasing order globally across all method calls.
currentTime is measured in seconds.
currentTime is used to represent the current moment of each operation.
For getMostActiveUser, if multiple users have the same highest activeness, the lexicographically smallest id is returned.
For getMostActiveUsers, lexicographic ordering is used to break ties, and the smaller id comes first.

Constraints

1 ≤ sender.length() ≤ 100
1 ≤ receiver.length() ≤ 100
sender != receiver
0 ≤ currentTime ≤ 10⁹
1 ≤ k ≤ 10⁵
User ids contain only lowercase English letters, digits, and underscore characters.
No parameter value will be null.
All currentTime values are monotonically non-decreasing globally across all method calls.
At most 10⁶ calls will be made to registerEvent.
At most 10⁵ calls will be made to getMostActiveUser.
At most 10⁵ calls will be made to getMostActiveUsers.

Examples

Example 1

ChatLogsProcessor processor = new ChatLogsProcessor()
processor.getMostActiveUser(currentTime = 0) returns ""
processor.registerEvent(sender = "alice", receiver = "bob", currentTime = 1)
processor.getMostActiveUser(currentTime = 2) returns "alice"

Explanation:
After the first chat, alice has chatted with bob, and bob has chatted with alice. Both users have activeness 1. Since there is a tie, the lexicographically smallest id "alice" is returned.

Example 2

ChatLogsProcessor processor = new ChatLogsProcessor()
processor.registerEvent(sender = "alice", receiver = "bob", currentTime = 1)
processor.registerEvent(sender = "alice", receiver = "charlie", currentTime = 2)
processor.getMostActiveUser(currentTime = 3) returns "alice"
processor.getMostActiveUsers(k = 2, currentTime = 4) returns ["alice", "bob"]

Explanation:
alice has chatted with bob and charlie, so her activeness is 2.
bob has activeness 1.
charlie has activeness 1.
The most active user is "alice".
For the top 2 active users, "bob" and "charlie" are tied with activeness 1, so "bob" comes first because it is lexicographically smaller.

Example 3

ChatLogsProcessor processor = new ChatLogsProcessor()
processor.registerEvent(sender = "alice", receiver = "bob", currentTime = 1)
processor.registerEvent(sender = "bob", receiver = "alice", currentTime = 2)
processor.registerEvent(sender = "bob", receiver = "charlie", currentTime = 3)
processor.getMostActiveUser(currentTime = 4) returns "bob"
processor.getMostActiveUsers(k = 3, currentTime = 5) returns ["bob", "alice", "charlie"]

Explanation:
The first two events are between the same pair of users, so they count as only one distinct chat relation.
alice has chatted with only bob, so her activeness is 1.
bob has chatted with alice and charlie, so his activeness is 2.
charlie has chatted with only bob, so his activeness is 1.
Therefore, "bob" is returned as the most active user.
For the top active users, "alice" and "charlie" are tied with activeness 1, so "alice" comes before "charlie".

Example 4

ChatLogsProcessor processor = new ChatLogsProcessor()
processor.registerEvent(sender = "david", receiver = "emma", currentTime = 10)
processor.registerEvent(sender = "alice", receiver = "bob", currentTime = 10)
processor.registerEvent(sender = "alice", receiver = "charlie", currentTime = 15)
processor.registerEvent(sender = "bob", receiver = "charlie", currentTime = 20)
processor.getMostActiveUsers(k = 4, currentTime = 25) returns ["alice", "bob", "charlie", "david"]

Explanation:
alice, bob, and charlie each have activeness 2. They are ordered lexicographically as "alice", "bob", and "charlie".
david and emma each have activeness 1. Since only the top 4 users are requested, "david" is included before "emma".