Count Mentions Per User

Count Mentions Per User

What is this problem about?

In this simulation problem, you are given a set of events (messages and user status changes) sorted by timestamp. Messages can mention specific users or everyone. Users can also go "offline" for a fixed duration. You need to calculate the total number of times each user was mentioned, keeping in mind that offline users do not receive mentions.

Why is this asked in interviews?

This problem tests your ability to handle Simulation and State Management. It requires coordinating two different types of events over a timeline. It evaluations how you manage data structures to represent user state (online/offline) and how you process strings to extract mention tokens.

Algorithmic pattern used

The pattern is Event-Based Simulation.

1. Sort the events by timestamp. If timestamps are equal, process "Offline" events before "Message" events.
2. Maintain an array mentions for each user and an array online_at to store when a user will be online again.
3. For each "Message" event:
   • If mention is "ALL", increment mentions for all users who are currently online.
   • If mention is "HERE", increment for online users only.
   • If mention is specific IDs, increment for those IDs (regardless of online status, usually, though the problem specifics might vary).
4. For each "Offline" event:
   • Set the user's online_at to current_timestamp + 60.

Example explanation

User A goes offline at time 10. A message mentions "ALL" at time 20.

• At time 10: User A is marked as "Offline until 70".
• At time 20: System checks all users. Since $20 < 70$, User A is offline and doesn't get the mention.
• If another message comes at time 80, User A is now online ($80 \ge 70$) and receives the mention.

Common mistakes candidates make

One common mistake is failing to handle simultaneous events correctly—offline events must often be processed before messages at the same timestamp to ensure the user is correctly excluded. Another mistake is forgetting to parse the mention string into individual user IDs correctly.

Interview preparation tip

When simulating time-based events, pay close attention to tie-breaking rules for identical timestamps. These are often the "hidden" edge cases that interviewers look for to distinguish between good and great solutions.