Quick Overview

Count how many chat messages mention each user, where one @ can list several comma-separated ids and a user counts at most once per message. The task tests precise parsing of mention groups, per-message deduplication, and sorting the results by count descending with ties broken by id.

Count Per-User @ Mentions with Comma-Separated IDs in Chat Messages

Company: Ramp

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: easy

Interview Round: Online Assessment

You are given a list of chat messages. A user is mentioned with `@` followed by their id, and a single `@` can mention several users at once by listing ids separated by commas, as in `@id1,id2`. For every user mentioned at least once, count how many messages mention them; a user mentioned several times in the same message counts only once for that message. Return the counts ordered from the highest count to the lowest, breaking ties by id in ascending order. The report describes the mention syntax only through the `@id1,id2` form; the Rules below fix the exact parsing. ### Function Signature ```python def count_mentions(messages: list[str]) -> list[tuple[str, int]]: ``` ### Rules - An id is a nonempty run of lowercase English letters, digits and underscores, taken as long as possible. - Every `@` in a message, wherever it appears, starts a mention group when the character right after it is an id character; the id that follows is mentioned. An `@` not immediately followed by an id character mentions nobody. - After a mentioned id, if the next character is a comma and the character right after that comma is an id character, the id after the comma is mentioned too, and this repeats. Any other character, including a space after the comma, ends the group. So `@ann,bob` mentions `ann` and `bob`, while `@ann, bob` mentions only `ann`. - A user's count is the number of messages in which the user is mentioned at least once. - Return one `(id, count)` pair for each user mentioned at least once, sorted by `count` descending and then by `id` ascending. Ids are compared character by character by character code, so digits sort before letters and `"u10"` comes before `"u2"`. - Return an empty list if no message mentions anyone. ### Constraints - `1 <= len(messages) <= 10^4` - `0 <= len(messages[i]) <= 500` - Messages contain only lowercase English letters, digits, underscores, spaces, and the characters `@`, `,`, `.`, `!` and `?`. - Every count is between 1 and `len(messages)`. ### Examples **Example 1** ```text Input: messages = ["@ann,bob lunch?", "@bob @bob,cal see notes", "thanks @ann, dan!"] Output: [("ann", 2), ("bob", 2), ("cal", 1)] ``` The first message mentions `ann` and `bob`. The second mentions `bob` twice and `cal` once; `bob` still counts once for that message. In the third, the comma after `ann` is followed by a space, so the group ends and `dan` is not mentioned. `ann` and `bob` tie at 2 and are ordered by id. **Example 2** ```text Input: messages = ["@u10,u2,u10 ok", "@ hi", "@u2,", "ping @u10"] Output: [("u10", 2), ("u2", 2)] ``` The first message mentions `u10` and `u2`; the repeated `u10` counts once. `@ hi` mentions nobody because a space follows the `@`. In `@u2,` the trailing comma is not followed by an id, so only `u2` is mentioned. Both ids have count 2, and `"u10"` sorts before `"u2"` because the character `1` comes before `2`. **Example 3** ```text Input: messages = ["ok@sam.", "@!", "no mention"] Output: [("sam", 1)] ``` The `@` inside `ok@sam.` still starts a group, so `sam` is mentioned. `@!` mentions nobody.

Overview: Count how many chat messages mention each user, where one @ can list several comma-separated ids and a user counts at most once per message. The task tests precise parsing of mention groups, per-message deduplication, and sorting the results by count descending with ties broken by id.

You are given a list of chat messages. A user is mentioned with `@` followed by their id, and a single `@` can mention several users at once by listing ids separated by commas, as in `@id1,id2`. For every user mentioned at least once, count how many messages mention them; a user mentioned several times in the same message counts only once for that message. Return the counts ordered from the highest count to the lowest, breaking ties by id in ascending order. Implement `count_mentions(messages)`. **Rules** - An id is a nonempty run of lowercase English letters, digits and underscores, taken as long as possible. - Every `@` in a message, wherever it appears, starts a mention group when the character right after it is an id character; the id that follows is mentioned. An `@` not immediately followed by an id character mentions nobody. - After a mentioned id, if the next character is a comma and the character right after that comma is an id character, the id after the comma is mentioned too, and this repeats. Any other character, including a space after the comma, ends the group. So `@ann,bob` mentions `ann` and `bob`, while `@ann, bob` mentions only `ann`. - A user's count is the number of messages in which the user is mentioned at least once. - Return one `(id, count)` pair for each user mentioned at least once, sorted by `count` descending and then by `id` ascending. Ids are compared character by character by character code, so digits sort before letters and `"u10"` comes before `"u2"`. - Return an empty list if no message mentions anyone. **Return value by language** - Python: a list of `(id, count)` tuples. - JavaScript: an array of `[id, count]` arrays. - Java: a `java.util.List<java.util.List<Object>>` whose inner lists are `[id (String), count (Integer)]`. - C++: a `std::vector<std::pair<std::string, int>>`. Every count is at most `len(messages)` <= 10^4, so no value exceeds 2^31 - 1 and a 32-bit `int` is enough in every language. **Example 1** ```text Input: messages = ["@ann,bob lunch?", "@bob @bob,cal see notes", "thanks @ann, dan!"] Output: [("ann", 2), ("bob", 2), ("cal", 1)] ``` The first message mentions `ann` and `bob`. The second mentions `bob` twice and `cal` once; `bob` still counts once for that message. In the third, the comma after `ann` is followed by a space, so the group ends and `dan` is not mentioned. `ann` and `bob` tie at 2 and are ordered by id. **Example 2** ```text Input: messages = ["@u10,u2,u10 ok", "@ hi", "@u2,", "ping @u10"] Output: [("u10", 2), ("u2", 2)] ``` The first message mentions `u10` and `u2`; the repeated `u10` counts once. `@ hi` mentions nobody because a space follows the `@`. In `@u2,` the trailing comma is not followed by an id, so only `u2` is mentioned. Both ids have count 2, and `"u10"` sorts before `"u2"` because the character `1` comes before `2`. **Constraints** - `1 <= len(messages) <= 10^4` - `0 <= len(messages[i]) <= 500` - Messages contain only lowercase English letters, digits, underscores, spaces, and the characters `@`, `,`, `.`, `!` and `?`. - Every count is between 1 and `len(messages)`.

Constraints

  • 1 <= len(messages) <= 10^4
  • 0 <= len(messages[i]) <= 500
  • Messages contain only lowercase English letters, digits, underscores, spaces, and the characters '@', ',', '.', '!' and '?'.
  • Every count is between 1 and len(messages), so every count fits in a 32-bit signed integer.

Examples

Input: (['@ann,bob lunch?', '@bob @bob,cal see notes', 'thanks @ann, dan!'],)

Expected Output: [('ann', 2), ('bob', 2), ('cal', 1)]

Explanation: Source Example 1: comma chaining, a repeat inside one message counts once, a comma followed by a space ends the group (dan not mentioned), and the 2-2 tie is ordered by id.

Input: (['@u10,u2,u10 ok', '@ hi', '@u2,', 'ping @u10'],)

Expected Output: [('u10', 2), ('u2', 2)]

Explanation: Source Example 2: repeated id within one group counts once, '@ hi' mentions nobody, a trailing comma ends the group, and 'u10' sorts before 'u2' by character code.

Hints

  1. A user's count rises by at most one per message, however many times that message mentions them.
  2. An `@` starts a group only when an id character follows it, and a comma continues the group only when an id character immediately follows the comma; any other character ends the group, but a later `@` can still start a new one.
  3. Ties on count are broken by comparing ids character by character by character code, so `_` falls between digits and letters and a shorter prefix comes before its extensions.

Loading coding console...

Show the approach

Approach

Scan each message once with an index i. When msg[i] is '@' and the next character is an id character (a-z, 0-9 or '_'), a mention group starts: read the maximal run of id characters as one id and put it into a per-message set; then, while the character right after that id is ',' and the character right after the comma is an id character, read the next maximal id and add it too. When the group stops, resume scanning at the character that stopped it (it may itself be an '@' that starts a new group, as in ',@' or 'x@y@z'); any other position just advances by one. After the message, add 1 to the global count of every id in the per-message set. Finally sort the (id, count) pairs by count descending and then by id ascending, comparing ids by character code (Python str order, Java String.compareTo, C++ std::string operator<, JavaScript < on strings; every character is ASCII).

Invariant: when the scanner sits at position i outside a group, every mention that starts before i has been recorded. A group consumes only id characters and the commas that join two ids, so no '@' is ever skipped, and reading each id to the end of its run implements 'taken as long as possible'. The per-message set makes each user contribute at most 1 per message, which is exactly the definition of a count. Ids are distinct keys, so (count descending, id ascending) is a total order and the output is unique.

Edge cases: empty messages and messages with no '@' followed by an id character contribute nothing; a final '@' or a trailing comma is handled by the bounds checks; an '@' inside a word still mentions; ', ' and ',,' end a group; if nobody is mentioned anywhere the result is an empty list. Counts never exceed len(messages) <= 10^4, so 32-bit integers suffice.

Time complexity:
O(L + U log U), where L is the total number of characters across all messages and U is the number of distinct mentioned ids
Space complexity:
O(L)