How do I approach Coding & Algorithms interview questions?

Coding & Algorithms questions require understanding of core concepts and practice. PracHub provides solutions with explanations to help you master coding & algorithms interviews.

What difficulty level is this interview 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 Interview Question

Q: Count User Journey Prefixes

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 has the form [user_id, timestamp, action].

Example input:

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:

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.