Katkat
Back

Build User Journey Path Summary

WhatnotSoftware Engineer · Technical Screen
HardSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

This question evaluates the ability to transform unordered user action logs into a trie-like path tree, exercising skills in grouping and time-sorting per user, maintaining stable insertion order, counting distinct users per prefix, and producing deterministic preorder string output.

Implement a function build_summary(logs) -> str that summarizes user journeys as a trie-like path tree.

You are given a list of action logs. Each log has the form:

(user_id: int, time: int, action: str)

Each user may have multiple logs. For each user, sort that user's logs by time in ascending order to obtain the user's action sequence. Then build a tree where each root-to-node path represents an action-prefix taken by at least one user. Each node stores the number of distinct users whose journey reached that exact prefix.

Rules:

  • Logs may arrive unordered, so sort actions by time per user.
  • Each user's journey contributes once to every prefix it traverses.
  • Repeated actions are valid and represent distinct steps. For example, A -> B -> B is different from A -> B and should create a child B under the first A -> B node.
  • Empty input should return an empty string.
  • A single user with a single action should return a one-node tree.
  • For deterministic output, print children in the order they are first created while inserting user journeys. Process users in ascending user_id order after constructing each user's sorted sequence.
  • If two logs for the same user have the same timestamp, preserve their original input order.

Output format:

  • Return a multiline string.
  • Use one line per node.
  • Print the action and count as ACTION (COUNT).
  • Root-level nodes have no prefix.
  • Non-root nodes are prefixed by two spaces per depth level followed by -> .
  • Print the tree using depth-first preorder traversal.

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 after sorting by time:

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

Expected output:

A (2)
 -> B (2)
 -> C (1)
 -> D (1)
 -> B (1)
B (1)
 -> A (1)

Additional test cases:

build_summary([])
# ""

build_summary([(1, 100, "X")])
# "X (1)"

build_summary([
 (1, 100, "A"),
 (1, 200, "B"),
 (2, 100, "A"),
 (2, 200, "B"),
])
# "A (2)\n -> B (2)"

build_summary([
 (1, 300, "C"),
 (1, 100, "A"),
 (1, 200, "B"),
])
# "A (1)\n -> B (1)\n -> C (1)"