← Whatnot Interview InsightsSoftware Engineer

Whatnot·Software Engineer·Technical Phone Screen·Intermediate

IntermediateRejected
Jun 2026Remote

Summary

Whatnot phone coding round for a Software Engineer role. One problem, 60 minutes, and I didn't finish. Got rejected.

Questions Asked (1)

Q1

Given a log of user actions with timestamps (user_id, time, action), build a summary of unique action paths across users. Output should be an indented tree where each node shows the action name and the count of distinct users who followed that path up to that point. Logs may arrive out of order.

Algorithms & Data StructuresSystem Design
Author's notes

I knew immediately it was a Trie problem.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Start by clarifying requirements and edge cases, then propose a two-phase solution: first sort the log by user and timestamp to reconstruct each user's action sequence, then build a prefix tree (trie) where each node tracks the set of distinct users who passed through it. Finally, output the trie as an indented tree with counts of distinct users per node.

Pro tip: Mention that using a set of user IDs per node ensures distinct user counts even if a user repeats the same path, and discuss memory trade-offs for large-scale logs. Also, note that sorting can be done externally if the log doesn't fit in memory.

1. Clarify requirements and constraints

Ask about log size, memory limits, expected output format, and whether actions are case-sensitive. Confirm that 'unique action paths' means distinct sequences of actions per user, and that counts are of distinct users.

2. Preprocess and sort the log

Group log entries by user_id and sort each user's actions by timestamp to reconstruct the correct sequence. If the log is too large, consider external sorting or streaming with a window.

3. Build the prefix tree (trie)

Insert each user's action sequence into a trie. At each node, maintain a set of user IDs that have visited that node. Increment the count when a new user reaches the node.

4. Generate the indented tree output

Traverse the trie depth-first, printing each node's action name and the size of its user set, with indentation proportional to depth. Ensure the output is sorted consistently (e.g., alphabetically) for readability.

5. Analyze complexity and optimize

Discuss time and space complexity: O(N log N) for sorting (N = number of log entries) and O(total unique path nodes) for trie. Suggest optimizations like using a hash map for user sets or compressing the trie if needed.

Key Points to Mention

  • Handling out-of-order logs by sorting per user based on timestamps.
  • Using a trie (prefix tree) to represent action paths and aggregate distinct user counts.
  • Maintaining a set of user IDs at each node to ensure distinct user counts.
  • Time complexity: O(N log N) due to sorting, and space complexity proportional to unique paths.
  • Scalability considerations: external sorting, streaming, or distributed processing for large logs.
  • Output formatting: indented tree with action names and counts, possibly sorted for determinism.

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