Whatnot·Software Engineer·Technical Phone Screen·Intermediate

Intermediate

May 2026

Summary

Whatnot software engineer interview with a trie/prefix-tree coding problem that looks straightforward until you actually read the edge cases. The problem is dressed up as a product analytics thing but it's really just careful tree construction plus sorting logic.

Questions Asked (1)

Given a list of user action logs as (user_id, timestamp, action) tuples, implement a function that builds a trie-like prefix tree of user journeys and returns it as a formatted multiline string. Each node should show the action and how many distinct users passed through that prefix. Children should be printed in insertion order, users processed in ascending ID order, and ties in timestamp should preserve original input order.

Algorithms & Data StructuresSystem Design

Author's notes

Took me a bit to realize the ordering rules were doing a lot of work here.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Start by clarifying the requirements and edge cases, then outline a solution that sorts the logs by user_id and timestamp (preserving input order for ties), builds a trie where each node tracks the set of distinct users, and finally performs a depth-first traversal to generate the formatted string with counts and insertion-ordered children. Discuss time and space complexity, and consider how to handle large inputs efficiently.

Pro tip: Mention that you would use a set per node to track distinct users, but if memory is a concern, you could use a more memory-efficient structure like a bitset or a hash set of user IDs, and note that the output format requires careful handling of indentation and counts.

1. Clarify requirements and edge cases

Ask about input size, expected output format, handling of duplicate actions, and whether users can have multiple sessions. Confirm sorting rules: ascending user ID, then timestamp, preserving original order for ties.

2. Design the trie structure

Each node represents an action and stores a set of distinct user IDs and an ordered map (or list) of children to maintain insertion order. The root is a dummy node.

3. Process logs and build trie

Sort logs by user_id, then timestamp, then original index. For each user, traverse their actions in order, inserting nodes as needed and adding the user ID to each node's set.

4. Generate formatted output

Perform a depth-first traversal, printing each node as 'action (count)' with appropriate indentation. Children are visited in insertion order.

5. Analyze complexity and optimize

Discuss time complexity: O(N log N) for sorting plus O(N * L) for trie insertion, where L is average journey length. Space: O(N * L) for trie nodes and user sets. Suggest optimizations if needed.

Key Points to Mention

Sorting stability: use a stable sort or include original index to preserve input order for ties.
Distinct user counting: use a set per node to avoid double-counting users who pass through the same prefix multiple times.
Insertion order of children: maintain an ordered data structure (e.g., list or LinkedHashMap) to preserve the order in which actions first appear.
Output formatting: recursive DFS with indentation, ensuring counts are correctly displayed.
Edge cases: empty input, single user, users with identical timestamps, actions with same name but different cases.
Scalability: consider memory usage of sets and potential for streaming or approximate counting if data is huge.

AI-generated suggestions, not part of the candidate's original notes. May be inaccurate — verify before relying on them.