Problem Description

You are provided with a list of user activity logs. Each log entry is structured as [user_id, timestamp, action].

The task is to:

1. For each unique user, reconstruct their complete journey by ordering their actions chronologically based on the timestamp.
2. Aggregate all individual user journeys.
3. Compute the frequency of every unique path prefix across all aggregated user journeys.

Example Input

logs = [
  [100, 1, "A"],
  [101, 2, "A"],
  [100, 3, "B"],
  [102, 4, "B"],
  [101, 5, "C"],
  [100, 6, "C"],
  [103, 7, "A"],
  [103, 8, "B"]
]

Reconstructed User Journeys

Based on the example input, the individual user journeys are:

• User 100: A, B, C
• User 101: A, C
• User 102: B
• User 103: A, B

Aggregated Prefix Counts

The final output should represent the aggregated prefix counts, for example:

A (3)
  B (2)
    C (1)
  C (1)
B (1)

This means:

• The action A appears as the first action in 3 user journeys.
• The sequence A -> B appears in 2 user journeys.
• The sequence A -> B -> C appears in 1 user journey.
• The sequence A -> C appears in 1 user journey.
• The action B appears as the first action in 1 user journey.

Deliverables

Return the aggregated prefix counts in any reasonable structured format, such as a trie (prefix tree), a nested map, or a list of prefixes with their corresponding counts.

Discussion Points

In addition to providing a solution, discuss the time and space complexity of your chosen approach. Also, consider and discuss whether the trie (or chosen data structure) can be updated incrementally while scanning the logs, rather than first building full per-user action lists and then processing them.