Count User Journey Prefixes

Problem Statement

In an e-commerce marketplace, understanding how users navigate the platform helps identify common drop-off points and popular discovery paths. You are given a list of user activity logs, where each log entry contains a user_id, an integer timestamp, and an action representing a page visit or interaction.

Your task is to reconstruct each user's chronological journey and count how many users completed each path prefix of length 1 up to k.

Specifically:

1. Group the logs by user_id and sort each user's actions in ascending order of timestamp.
2. For each user, extract every prefix of their action sequence with length between 1 and min(k, len(user_actions)).
3. Count the number of unique users who experienced each prefix.

Return the counts as a dictionary (or hash map) where the key is a tuple of action strings representing the prefix, and the value is the integer count of users.

Interface

def count_user_prefixes(logs: list[tuple[str, int, str]], k: int) -> dict[tuple[str, ...], int]:
    """
    Args:
        logs: List of (user_id, timestamp, action) tuples.
        k: Maximum prefix length to consider (1 <= k).

    Returns:
        A mapping from prefix tuples to the number of distinct users who have that prefix.
    """

Input & Output Format

• Input:
  • logs: A list of tuples (user_id, timestamp, action) where user_id is a string, timestamp is an integer, and action is a string.
  • k: An integer representing the maximum length of prefixes to count.
• Output: A dictionary mapping tuple[str, ...] to int.

Examples

Example 1

logs = [
    ("u1", 100, "home"),
    ("u2", 90, "home"),
    ("u1", 110, "item"),
    ("u1", 105, "search"),
    ("u2", 95, "search"),
    ("u2", 120, "cart"),
    ("u3", 50, "stream")
]
k = 2

output = count_user_prefixes(logs, k)
# Output:
# {
#     ("home",): 2,
#     ("home", "search"): 2,
#     ("stream",): 1
# }

Explanation:

• u1 journey: ["home", "search", "item"]. Prefixes up to length 2: ("home",) and ("home", "search").
• u2 journey: ["home", "search", "cart"]. Prefixes up to length 2: ("home",) and ("home", "search").
• u3 journey: ["stream"]. Prefixes up to length 2: ("stream",).

Example 2

logs = [
    ("u1", 10, "login"),
    ("u1", 20, "login")
]
k = 3

output = count_user_prefixes(logs, k)
# Output:
# {
#     ("login",): 1,
#     ("login", "login"): 1
# }

Constraints

• 1 <= len(logs) <= 10^5
• 1 <= k <= 10
• 1 <= len(user_id), len(action) <= 30
• 0 <= timestamp <= 10^9
• All (user_id, timestamp) pairs are unique within logs.