FastPrep
Problem · Trie

User Journey Paths

● MediumWhatnotFULLTIMEPHONE SCREEN

Complete the function below. The function receives the full standard input as a single string and must return the exact standard output lines for the described problem.

User Journey Paths (Action Log Trie Summary)

You are given action logs emitted by a platform. Each log entry is a tuple: (user_id, time, action).

Build a path tree (Trie-like summary) of users' journeys:

  • For each user, sort their logs by time ascending to obtain that user's action sequence.
  • Insert each user's sequence into a tree.
  • Each node represents an action; a path from the root represents an action-prefix.
  • Each node stores a count = the number of distinct users whose journey reached that node via that prefix.

Input

Lines of the form user_id time action, one log entry per line.

Output

Return an indented string representation of the tree as an array of lines (no trailing newline characters):

  • Do not print the root.
  • Each line: ACTION (count).
  • A node at depth d (root's children are depth 1) is prefixed with 2*d spaces followed by -> . For example, depth-1 nodes are prefixed with -> , depth-2 nodes with -> , depth-3 nodes with -> , and so on. Root-level nodes (depth 0) have no prefix.
  • For deterministic output, print siblings in lexicographic order by action.

Notes / Edge cases

  • Logs can be unordered: group by user and sort by time.
  • Each user contributes +1 to every prefix node along their path.
  • Repeated actions are distinct steps (e.g., A -> B -> B is valid; the second B is a child of the first B).
  • Empty input ⇒ empty output (empty array).
  • Single user / single action ⇒ single line with no prefix.

Example

Input logs:

100 1000 A
300 1150 A
200 1200 B
100 1200 B
100 1300 C
200 1400 A
300 1500 B
300 1550 B
100 1560 D

Per-user sequences:

  • user 100: A -> B -> C -> D
  • user 200: B -> A
  • user 300: A -> B -> B

Expected output lines:

A (2)
  -> B (2)
    -> B (1)
    -> C (1)
      -> D (1)
B (1)
  -> A (1)
Examples
01 · Example 1
input = "100 1000 A\n300 1150 A\n200 1200 B\n100 1200 B\n100 1300 C\n200 1400 A\n300 1500 B\n300 1550 B\n100 1560 D"
return = ["A (2)", "  -> B (2)", "    -> B (1)", "    -> C (1)", "      -> D (1)", "B (1)", "  -> A (1)"]
The indentation rule is depth-scaled: a node at depth d is prefixed with 2*d spaces then -> . Root-level nodes (depth 0) have no prefix. So: A (2) at depth 0 has no prefix; B (2) at depth 1 gets -> ; B (1) and C (1) at depth 2 get -> ; D (1) at depth 3 gets -> ; B (1) at depth 0 has no prefix; A (1) at depth 1 gets -> . Note that user 100's path is A->B->C->D, so C is a child of B (depth 2) and D is a child of C (depth 3).
Constraints

Constraints:

  • Each input line contains exactly three whitespace-separated fields: an integer user_id, an integer time, and a non-empty alphanumeric string action.
  • All time values for a given user are distinct (no tie-breaking needed within a user's sequence).
  • Action strings are non-empty and contain no whitespace.
  • Empty input produces an empty output array.
  • Output lines must not have trailing newline characters.
drafts saved locally
public String[] solveUserJourneyPaths(String input) {
    // write your code here
}
input"100 1000 A\n300 1150 A\n200 1200 B\n100 1200 B\n100 1300 C\n200 1400 A\n300 1500 B\n300 1550 B\n100 1560 D"
expected["A (2)", "-> B (2)", "-> B (1)", "-> C (1)", "-> D (1)", "B (1)", "-> A (1)"]
checking account