We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Count Mentions Per User

Number: 3721

Difficulty: Medium

Paid? No

Companies: N/A

Problem Description

Given the total number of users and a list of events, count how many times each user is mentioned across all MESSAGE events. Each event is one of two types: a MESSAGE event that contains a string of mention tokens ("id", "ALL", or "HERE") and an OFFLINE event where a specific user goes offline for 60 time units. All users start online and status changes due to OFFLINE events (and coming back online when the timeout expires) are processed before any MESSAGE event at the same timestamp. Note that duplicate mentions in a single message should be counted separately.

Key Insights

  • Simulate the event processing in timestamp order, ensuring that offline status changes are applied before processing any MESSAGE events at the same time.
  • Use an array to track the number of mentions per user.
  • Maintain the online/offline status for each user along with the time when an offline user should automatically come back online.
  • Handle mention tokens:
    • "id": increment the count for that specific user (even count duplicates).
    • "ALL": increment the count for all users regardless of status.
    • "HERE": increment the count only for users who are online at the time of the event.
  • Since the number of users and events is small, a linear scan to update statuses is acceptable.

Space and Time Complexity

Time Complexity: O(n * m) where n is the number of events and m is the maximum number of tokens per MESSAGE event (with an additional O(numberOfUsers) per event to update statuses). Since numberOfUsers and tokens per message are small, this is efficient. Space Complexity: O(numberOfUsers) for storing the mentions counts and online/offline status information.

Solution

We simulate the events sequentially. For each event:

  1. Convert the event timestamp to an integer.
  2. Before processing the event, update the status of all users: if a user is offline and the current timestamp is greater than or equal to the time they come back online, mark them as online.
  3. For an OFFLINE event, mark the specified user offline and record their "back online" time as the current timestamp + 60.
  4. For a MESSAGE event, split the mention string into tokens and process each one:
    • If the token is "ALL", increment the mention count for every user.
    • If the token is "HERE", increment the mention count only for users whose status is currently online.
    • If the token starts with "id", parse the id number and increment that user’s count.

This approach ensures that each event is processed with the correct user statuses and that every mention is counted appropriately.

Code Solutions

# Python solution
def countMentionsPerUser(numberOfUsers, events):
    # Initialize an array for mentions count for each user
    mentions = [0] * numberOfUsers
    # Online status for each user, True indicates online.
    online = [True] * numberOfUsers
    # Timestamp when offline user will become online again; 0 if online.
    back_online_time = [0] * numberOfUsers

    # Function to update user statuses based on the current timestamp
    def update_statuses(current_time):
        for user in range(numberOfUsers):
            # If user is offline and it's time to come back online
            if not online[user] and current_time >= back_online_time[user]:
                online[user] = True

    # Process each event
    for event in events:
        event_type, timestamp_str, info = event
        current_time = int(timestamp_str)
        # Update the statuses before processing the current event
        update_statuses(current_time)
        if event_type == "OFFLINE":
            # Parse the user id that goes offline
            user_id = int(info)
            # Set the user offline and record when they'll be back online
            online[user_id] = False
            back_online_time[user_id] = current_time + 60
        elif event_type == "MESSAGE":
            # Split the mention string into tokens
            tokens = info.split()
            for token in tokens:
                if token == "ALL":
                    # Mention all users regardless of online/offline status
                    for user in range(numberOfUsers):
                        mentions[user] += 1
                elif token == "HERE":
                    # Mention only users that are currently online
                    for user in range(numberOfUsers):
                        if online[user]:
                            mentions[user] += 1
                elif token.startswith("id"):
                    # Extract the user id number and increment that user's count
                    user_id = int(token[2:])
                    mentions[user_id] += 1
    return mentions

# Example usage:
print(countMentionsPerUser(2, [["MESSAGE", "10", "id1 id0"], 
                               ["OFFLINE", "11", "0"], 
                               ["MESSAGE", "71", "HERE"]]))
← Back to All Questions