How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a easy difficulty Coding & Algorithms question, commonly asked during Take-home Project rounds at Whatnot.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Whatnot during technical interviews.

Count User Journey Prefixes | Whatnot Coding Question

Count User Journey Prefixes

Company: Whatnot

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: easy

Interview Round: Take-home Project

You are given a list of user activity logs. Each log record has the form `[user_id, timestamp, action]`. Example input: ```text 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"] ] ``` For each user, reconstruct that user's journey by ordering the actions by `timestamp`. Then aggregate all users' journeys and compute the count of every path prefix. Using the example above, the reconstructed journeys are: - `100 -> A, B, C` - `101 -> A, C` - `102 -> B` - `103 -> A, B` The aggregated prefix counts are: ```text A (3) B (2) C (1) C (1) B (1) ``` Explanation: - `A` appears as the first action for 3 users. - `A -> B` appears for 2 users. - `A -> B -> C` appears for 1 user. - `A -> C` appears for 1 user. - `B` appears as the first action for 1 user. Return the aggregated prefix counts in any reasonable structured format, such as a trie, nested map, or a list of prefixes with counts. Discuss the time and space complexity of your approach, and whether the trie can be updated while scanning the logs instead of first building full per-user action lists.

Quick Answer: This question evaluates the ability to reconstruct per-user action sequences from timestamped logs, aggregate and count path prefixes, and apply data-structure and algorithmic reasoning within the Coding & Algorithms domain.

You are given a list of user activity logs. Each log record is [user_id, timestamp, action]. For each user, reconstruct that user's journey by ordering their actions by timestamp. If two records for the same user have the same timestamp, keep their relative order from the original input. Then aggregate all users' journeys and count every non-empty prefix path. Return the result as a list of [prefix, count] pairs, where prefix is a list of action strings. The returned list must be sorted lexicographically by prefix. For example, ["A"] comes before ["A", "B"], which comes before ["A", "C"]. In an interview discussion: if logs are already processed in nondecreasing timestamp order per user, a trie can be updated incrementally while scanning. For arbitrary unsorted logs, you generally need to buffer and sort per user first, because an earlier timestamp discovered later can change that user's prefixes.

Constraints

0 <= len(logs) <= 100000
user_id is an integer
timestamp is an integer
action is a non-empty string
If a user's records have the same timestamp, their input order is used as the tie-breaker
Let L be the total number of action strings across all returned prefixes; test data keeps L <= 200000

Examples

Input: ([[100, 1, "A"], [101, 2, "A"], [100, 3, "B"], [102, 4, "B"], [101, 5, "C"], [100, 6, "C"], [103, 7, "A"], [103, 8, "B"]],)

Expected Output: [[["A"], 3], [["A", "B"], 2], [["A", "B", "C"], 1], [["A", "C"], 1], [["B"], 1]]

Explanation: The journeys are 100: A,B,C; 101: A,C; 102: B; 103: A,B. Their prefixes produce the listed counts.

Input: ([],)

Expected Output: []

Explanation: There are no users and therefore no prefixes.

Input: ([[1, 10, "X"], [1, 10, "Y"], [2, 5, "X"], [2, 6, "X"], [1, 9, "Z"]],)

Expected Output: [[["X"], 1], [["X", "X"], 1], [["Z"], 1], [["Z", "X"], 1], [["Z", "X", "Y"], 1]]

Explanation: User 1's journey is Z,X,Y. The two records at timestamp 10 keep input order: X then Y. User 2's journey is X,X.

Input: ([[5, 3, "C"], [5, 1, "A"], [5, 2, "B"], [6, 2, "A"], [6, 1, "B"], [7, 1, "A"]],)

Expected Output: [[["A"], 2], [["A", "B"], 1], [["A", "B", "C"], 1], [["B"], 1], [["B", "A"], 1]]

Explanation: The logs are not globally sorted. User 5 has A,B,C; user 6 has B,A; user 7 has A.

Input: ([[1, 2, "view"], [1, 1, "login"], [2, 1, "login"], [2, 2, "view"], [3, 1, "login"]],)

Expected Output: [[["login"], 3], [["login", "view"], 2]]

Explanation: Three users start with login, and two of those users continue with view.

Hints

Group log records by user first, then sort each user's records by timestamp.
A trie is a natural way to count how many journeys pass through each prefix; a preorder traversal of sorted children can produce the required sorted list.

Quick Overview

This question evaluates the ability to reconstruct per-user action sequences from timestamped logs, aggregate and count path prefixes, and apply data-structure and algorithmic reasoning within the Coding & Algorithms domain.