Analyze User Website Visit Pattern - Practice Coding Problems

Analyze User Website Visit Pattern - Problem

You are given three arrays username, website, and timestamp, all of the same length. The tuple [username[i], website[i], timestamp[i]] indicates that user username[i] visited website website[i] at time timestamp[i].

A pattern is a list of three websites (not necessarily distinct). The score of a pattern is the number of users that visited all websites in the pattern in the same order they appeared in the pattern (chronologically).

Return the pattern with the largest score. If there are multiple patterns with the same largest score, return the lexicographically smallest pattern.

Input & Output

Example 1 — Multiple Users Same Pattern

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

› Output: ["home","about","career"]

💡 Note: Both users 'joe' and 'james' visited home→about→career in chronological order, giving this pattern a score of 2, which is the maximum possible.

Example 2 — Lexicographic Tie Breaking

$ Input: username = ["ua","ua","ua","ub","ub","ub"], website = ["a","b","a","a","b","c"], timestamp = [1,2,3,4,5,6]

› Output: ["a","b","a"]

💡 Note: Two patterns have score 1: ["a","b","a"] and ["a","b","c"]. We return the lexicographically smaller one.

Example 3 — Same User Multiple Patterns

$ Input: username = ["u1","u1","u1","u1"], website = ["a","b","c","d"], timestamp = [1,2,3,4]

› Output: ["a","b","c"]

💡 Note: User 'u1' generates multiple 3-website patterns: ["a","b","c"], ["a","b","d"], ["a","c","d"], ["b","c","d"]. All have score 1, so we return the lexicographically smallest.

Constraints

3 ≤ username.length ≤ 50
1 ≤ username[i].length ≤ 10
1 ≤ website[i].length ≤ 10
1 ≤ timestamp[i] ≤ 10⁹
All tuples [username[i], website[i], timestamp[i]] are unique

Visualization

Tap to expand

Understanding the Visualization

Input Data

Three parallel arrays: usernames, websites, timestamps

Group & Sort

Organize visits by user and sort chronologically

Generate Patterns

Create all possible 3-website subsequences

Count & Select

Find pattern with highest user count

Key Takeaway

🎯 Key Insight: Group visits by user first, then systematically generate all 3-website patterns while preserving chronological order

Asked in

a Amazon 15 G Google 12 f Facebook 8 M Microsoft 6

The key insight is to group visits by user first, then generate all possible 3-website subsequences while preserving chronological order. Best approach uses hash map to count pattern frequencies efficiently. Time: O(n³), Space: O(n²)

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force - Generate All Patterns	O(n³)	O(n)	Check every possible combination of 3 websites for each user
Optimized Pattern Generation	O(n³)	O(n²)	Group visits by user first, then efficiently generate 3-website patterns

Brute Force - Generate All Patterns — Algorithm Steps

Step 1: Group visits by username and sort by timestamp
Step 2: For each user, generate all possible 3-website combinations
Step 3: Count pattern frequencies and find maximum

Visualization

Tap to expand

Step-by-Step Walkthrough

Group by User

Organize visits by username and sort by timestamp

Generate Patterns

For each user, create all possible 3-website combinations

Count & Select

Count pattern frequencies and select lexicographically smallest maximum

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX_USERS 1000
#define MAX_VISITS 1000
#define MAX_PATTERNS 10000
#define MAX_LEN 100

struct Visit {
    int timestamp;
    char website[MAX_LEN];
};

struct User {
    char username[MAX_LEN];
    struct Visit visits[MAX_VISITS];
    int visitCount;
};

struct Pattern {
    char pattern[MAX_LEN * 3];
    char users[MAX_USERS][MAX_LEN];
    int userCount;
};

int compareVisits(const void *a, const void *b) {
    return ((struct Visit*)a)->timestamp - ((struct Visit*)b)->timestamp;
}

char* solution(char username[][MAX_LEN], char website[][MAX_LEN], int timestamp[], int n) {
    struct User users[MAX_USERS];
    int userCount = 0;
    
    // Group visits by user
    for (int i = 0; i < n; i++) {
        int userIdx = -1;
        for (int j = 0; j < userCount; j++) {
            if (strcmp(users[j].username, username[i]) == 0) {
                userIdx = j;
                break;
            }
        }
        
        if (userIdx == -1) {
            userIdx = userCount++;
            strcpy(users[userIdx].username, username[i]);
            users[userIdx].visitCount = 0;
        }
        
        users[userIdx].visits[users[userIdx].visitCount].timestamp = timestamp[i];
        strcpy(users[userIdx].visits[users[userIdx].visitCount].website, website[i]);
        users[userIdx].visitCount++;
    }
    
    // Sort visits by timestamp for each user
    for (int i = 0; i < userCount; i++) {
        qsort(users[i].visits, users[i].visitCount, sizeof(struct Visit), compareVisits);
    }
    
    // Count patterns
    struct Pattern patterns[MAX_PATTERNS];
    int patternCount = 0;
    
    for (int u = 0; u < userCount; u++) {
        if (users[u].visitCount < 3) continue;
        
        // Generate all 3-website combinations
        for (int i = 0; i < users[u].visitCount; i++) {
            for (int j = i + 1; j < users[u].visitCount; j++) {
                for (int k = j + 1; k < users[u].visitCount; k++) {
                    char pattern[MAX_LEN * 3];
                    sprintf(pattern, "%s,%s,%s", 
                           users[u].visits[i].website,
                           users[u].visits[j].website,
                           users[u].visits[k].website);
                    
                    // Find or create pattern
                    int patternIdx = -1;
                    for (int p = 0; p < patternCount; p++) {
                        if (strcmp(patterns[p].pattern, pattern) == 0) {
                            patternIdx = p;
                            break;
                        }
                    }
                    
                    if (patternIdx == -1) {
                        patternIdx = patternCount++;
                        strcpy(patterns[patternIdx].pattern, pattern);
                        patterns[patternIdx].userCount = 0;
                    }
                    
                    // Check if user already counted for this pattern
                    int found = 0;
                    for (int uc = 0; uc < patterns[patternIdx].userCount; uc++) {
                        if (strcmp(patterns[patternIdx].users[uc], users[u].username) == 0) {
                            found = 1;
                            break;
                        }
                    }
                    
                    if (!found) {
                        strcpy(patterns[patternIdx].users[patterns[patternIdx].userCount], users[u].username);
                        patterns[patternIdx].userCount++;
                    }
                }
            }
        }
    }
    
    // Find pattern with maximum score
    int maxScore = 0;
    char *resultPattern = NULL;
    
    for (int i = 0; i < patternCount; i++) {
        int score = patterns[i].userCount;
        if (score > maxScore || (score == maxScore && (resultPattern == NULL || strcmp(patterns[i].pattern, resultPattern) < 0))) {
            maxScore = score;
            resultPattern = patterns[i].pattern;
        }
    }
    
    static char result[MAX_LEN * 3];
    strcpy(result, resultPattern);
    return result;
}

int main() {
    char username[MAX_USERS][MAX_LEN];
    char website[MAX_USERS][MAX_LEN];
    int timestamp[MAX_USERS];
    int n = 0;
    
    // Simple parsing - assuming small input
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%s %s %d", username[i], website[i], &timestamp[i]);
    }
    
    char *result = solution(username, website, timestamp, n);
    
    // Format output as JSON array
    char *token = strtok(result, ",");
    printf("[\"%s\"", token);
    token = strtok(NULL, ",");
    while (token != NULL) {
        printf(",\"%s\"", token);
        token = strtok(NULL, ",");
    }
    printf("]\n");
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n³)

For each user with k visits, we generate O(k³) patterns, worst case O(n³) total

⚠ Quadratic Growth

Space Complexity

O(n)

Hash map to store pattern frequencies and user visit lists

⚡ Linearithmic Space

28.4K Views

Medium Frequency

~25 min Avg. Time

856 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force - Generate All Patterns — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler