Katkat
Back

Find the Most Common Visit Pattern

AmazonSoftware Engineer · Onsite
HardSoftware EngineerOnsiteCoding & Algorithms

Last updated

This problem tests your ability to process chronological event data to identify the most frequent 3-step sequence, requiring efficient data structures to handle large volumes of user logs.

Problem Statement

You are given a list of user visits to a website, where each visit consists of a username, a timestamp, and a website name. A 'visit pattern' is defined as a sequence of three websites visited by a single user in chronological order. A user may visit the same website multiple times, but a visit pattern is only counted once per user.

If a user visits the sequence [A, B, C, D], their unique patterns are [A, B, C] and [B, C, D]. If a user visits [A, B, A, C], their patterns are [A, B, A], [A, B, C], and [B, A, C].

Your goal is to find the visit pattern of length 3 that appears for the greatest number of unique users. If there is a tie, return the pattern that is lexicographically smallest.

Function Signature

def find_most_common_pattern(username, timestamp, website) -> List[str]:
    # username: List[str]
    # timestamp: List[int]
    # website: List[str]
    pass

Constraints

  • The number of visits n is up to 10,000.
  • 1 <= len(username) == len(timestamp) == len(website) <= 10,000.
  • Timestamps are unique for a single user.

Example

Input: username = ['joe', 'joe', 'joe', 'james', 'james', 'james'] timestamp = [1, 2, 3, 4, 5, 6] website = ['home', 'about', 'career', 'home', 'cart', 'books']

Output: ['home', 'about', 'career']

Explanation: Joe visited: (home, about, career). James visited: (home, cart, books). Both patterns appear exactly once. Lexicographically, 'home' < 'home', 'about' < 'cart'.

Hints

Hint 1

Group all websites visited by each user and sort them by their respective timestamps.

Hint 2

For each user, generate all possible 3-length subsequences using a sliding window or nested loops, ensuring you only count each unique pattern once per user.

Hint 3

Use a hash map to count the occurrences of each unique pattern across all users, and keep track of the max count.

Follow-up questions

  • How would you optimize the memory usage if the number of users grew to millions?
  • What changes are needed if we needed to find the top K most common patterns instead of just the single most common one?
  • How would you handle cases where two visits have the same timestamp for a single user (e.g., logging errors)?