Quick Overview

Given unordered user activity log entries, each holding a user id, a timestamp and an action, rebuild every user's journey as the list of their actions in time order. The task tests grouping by user, stable sorting with numeric timestamp comparison, and a deterministic output order across users.

Reconstruct Each User's Journey from Unordered Activity Logs

Company: Whatnot

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: hard

Interview Round: Onsite

An app writes one log entry for every user action, and the entries reach you in no particular order. Each entry records which user acted, when, and what they did. Reconstruct every user's journey: that user's actions in the order in which they happened. ### Function Signature ```python def reconstruct_journeys(logs: list[list[str]]) -> list[list[str]]: ``` ### Rules - `logs[i] = [user_id, timestamp, action]`. All three fields are strings, exactly as read from a log file; `timestamp` is a non-negative integer written in decimal. - A user's journey is that user's actions ordered by timestamp, earliest first. Compare timestamps as integers, not as strings, so `"9"` comes before `"10"`. - Two entries of the same user with the same timestamp keep the relative order they have in `logs`. - Every entry contributes one action, so a journey can contain the same action more than once. - Return one list per distinct user: `[user_id, action_1, action_2, ..., action_k]`. Order these lists by `user_id` in ascending lexicographic order (plain character-code comparison, so `"u10"` comes before `"u9"`). - Return `[]` when `logs` is empty. ### Constraints - `0 <= len(logs) <= 10^5` - `user_id` has 1 to 20 characters, each a lowercase English letter or a digit. - `action` has 1 to 30 characters, each a lowercase English letter or an underscore. - `timestamp` is the decimal form of an integer `0 <= timestamp <= 10^12` (for example, milliseconds since the Unix epoch), with no leading zeros (`"0"` itself is allowed). Values can exceed 2^31-1, so parse them into 64-bit integers. ### Examples **Example 1** ```text Input: logs = [["u2", "5", "view_item"], ["u1", "3", "login"], ["u2", "1", "login"], ["u1", "10", "logout"], ["u1", "7", "search"]] Output: [["u1", "login", "search", "logout"], ["u2", "login", "view_item"]] ``` User `u1` acted at times 3, 7 and 10; `"10"` is the latest even though it would sort first as a string. User `u2` acted at times 1 and 5. **Example 2** ```text Input: logs = [["b7", "4", "add_to_cart"], ["a1", "2", "open_app"], ["b7", "4", "checkout"], ["b7", "1", "open_app"]] Output: [["a1", "open_app"], ["b7", "open_app", "add_to_cart", "checkout"]] ``` User `b7` has two entries at time 4; `add_to_cart` comes before `checkout` because it appears first in `logs`. **Example 3** ```text Input: logs = [] Output: [] ```

Overview: Given unordered user activity log entries, each holding a user id, a timestamp and an action, rebuild every user's journey as the list of their actions in time order. The task tests grouping by user, stable sorting with numeric timestamp comparison, and a deterministic output order across users.

An app writes one log entry for every user action, and the entries reach you in no particular order. Each entry records which user acted, when, and what they did. Reconstruct every user's journey: that user's actions in the order in which they happened. Implement `reconstruct_journeys(logs)`, where `logs[i] = [user_id, timestamp, action]`. ### Rules - All three fields of an entry are strings, exactly as read from a log file; `timestamp` is a non-negative integer written in decimal. - A user's journey is that user's actions ordered by timestamp, earliest first. Compare timestamps as integers, not as strings, so `"9"` comes before `"10"`. - Two entries of the same user with the same timestamp keep the relative order they have in `logs`. - Every entry contributes one action, so a journey can contain the same action more than once. - Return one list per distinct user: `[user_id, action_1, action_2, ..., action_k]`. Order these lists by `user_id` in ascending lexicographic order (plain character-code comparison, so `"u10"` comes before `"u9"`). - Return `[]` when `logs` is empty. ### Constraints - `0 <= len(logs) <= 10^5` - Each `logs[i]` contains exactly three strings: `[user_id, timestamp, action]`. - `user_id` has 1 to 20 characters, each a lowercase English letter or a digit. - `action` has 1 to 30 characters, each a lowercase English letter or an underscore. - `timestamp` is the decimal form of an integer `0 <= timestamp <= 10^12` (for example, milliseconds since the Unix epoch), with no leading zeros (`"0"` itself is allowed). Values can exceed 2^31-1, so parse them into 64-bit integers (`long` in Java, `long long` in C++). ### Example 1 ```text Input: logs = [["u2", "5", "view_item"], ["u1", "3", "login"], ["u2", "1", "login"], ["u1", "10", "logout"], ["u1", "7", "search"]] Output: [["u1", "login", "search", "logout"], ["u2", "login", "view_item"]] ``` User `u1` acted at times 3, 7 and 10; `"10"` is the latest even though it would sort first as a string. User `u2` acted at times 1 and 5. ### Example 2 ```text Input: logs = [["b7", "4", "add_to_cart"], ["a1", "2", "open_app"], ["b7", "4", "checkout"], ["b7", "1", "open_app"]] Output: [["a1", "open_app"], ["b7", "open_app", "add_to_cart", "checkout"]] ``` User `b7` has two entries at time 4; `add_to_cart` comes before `checkout` because it appears first in `logs`.

Constraints

  • 0 <= len(logs) <= 10^5
  • Each logs[i] is [user_id, timestamp, action], three strings
  • user_id has 1 to 20 characters, each a lowercase English letter or a digit
  • action has 1 to 30 characters, each a lowercase English letter or an underscore
  • timestamp is the decimal form of an integer 0 <= timestamp <= 10^12 with no leading zeros ("0" itself is allowed); values can exceed 2^31-1, so parse them as 64-bit integers (long in Java, long long in C++)

Examples

Input: ([],)

Expected Output: []

Explanation: Minimum: empty logs return [].

Input: ([['u1', '42', 'login']],)

Expected Output: [['u1', 'login']]

Explanation: Minimum: a single entry gives one journey with one action.

Hints

  1. Timestamps arrive as strings, but the rules order them as integers: "9" comes before "10", and values reach 10^12, beyond the 32-bit range.
  2. Entries of one user that share a timestamp must keep the order they have in logs, so think about what information preserves that order.
  3. Users are ordered by plain character-code comparison of user_id, so "u10" comes before "u9" and "u1" comes before "u10".

Loading coding console...

Show the approach

Approach

Algorithm: make one pass over logs and append each entry to its user's group as (timestamp parsed as a 64-bit integer, position in logs, action). Sort each group by (timestamp, position), then emit the groups in ascending character-code order of user_id, each as [user_id] followed by its actions in sorted order.

Invariant: every entry lands in exactly one group, so each journey has exactly as many actions as that user has entries; fully duplicate entries and repeated actions are all kept.

Correctness: the integer comparison implements 'earliest first' and puts "9" before "10". Positions are distinct, so (timestamp, position) is a strict total order inside a group and equal timestamps fall back to input order, as the rules require; the result does not depend on the sort being stable. Entries of other users never enter a group, so equal timestamps across users cannot change a journey. Users are then ordered by plain string comparison of user_id (Python sorted on str, JavaScript < on strings, Java TreeMap with String.compareTo, C++ std::mapstd::string), which for these ASCII ids is character-code order: "u1" < "u10" < "u9" and digit-leading ids before letter-leading ones.

Edge cases: empty logs produce no groups and return []; a single entry returns [[user_id, action]]. Timestamps up to 10^12 exceed 2^31-1, so Java uses long and C++ long long; JavaScript Numbers hold them exactly because 10^12 < 2^53.

Time complexity:
O(n log n)
Space complexity:
O(n)