Solution For Analyze User Website Visit Pattern

Problem Statement:

The problem statement can be found on the Leetcode website at the following link: https://leetcode.com/problems/analyze-user-website-visit-pattern/

You are given three arrays username, timestamp, and website of the same length N where the ith tuple means that the user with name username[i] visited the website website[i] at time timestamp[i].

A three-sequence is a list of not necessarily different websites of length 3 sorted in ascending order by the time of their visits.

Find the 3-sequence visited at least once by the largest number of users. If there is more than one solution, return the lexicographically smallest such 3-sequence.

Solution:

Approach:

We will start with creating a list that contains browsing history for each user. We will use a dictionary for this purpose, where the key will be the name of the user, and the value will be a list containing the websites visited by the user.

Next, we will create a dictionary that contains all possible 3-sequences visited by each user. We will iterate over the browsing history of each user, create all possible 3-sequences and add them to the dictionary. The key will be the 3-sequence, and the value will be a set of users who visited this sequence.

Finally, we will iterate over the dictionary containing all the 3-sequences and count the number of users who visited each 3-sequence. We will also keep track of the 3-sequence that has been visited by the largest number of users.

At the end of our computation, we will return the lexicographically smallest 3-sequence that has been visited by the largest number of users.

Algorithm:

1. Create a dictionary (user_history) that contains browsing history for each user.
2. Create a dictionary (user_sequences) that contains all possible 3-sequences visited by each user.
3. Iterate over the browsing history of each user, create all possible 3-sequences and add them to the dictionary user_sequences.
4. Iterate over the dictionary user_sequences, count the number of users who visited each 3-sequence and keep track of the 3-sequence that has been visited by the largest number of users.
5. Return the lexicographically smallest 3-sequence that has been visited by the largest number of users.

Code:

The Python code for the mentioned algorithm is as follows:

“`
from collections import defaultdict
import itertools

class Solution:
def mostVisitedPattern(self, username: List[str], timestamp: List[int], website: List[str]) -> List[str]:

    # Step 1: Create a dictionary (user_history) that contains browsing history for each user.
    user_history = defaultdict(list)
    for i in range(len(username)):
        user_history[username[i]].append((timestamp[i], website[i]))

    # Step 2: Create a dictionary (user_sequences) that contains all possible 3-sequences visited by each user.
    user_sequences = defaultdict(set)
    for user in user_history.keys():
        sites = user_history[user]
        for seq in itertools.combinations(sites, 3):
            user_sequences[seq].add(user)

    # Step 3: Iterate over the dictionary user_sequences, count the number of users who visited each 3-sequence and keep track of the 3-sequence that has been visited by the largest number of users.
    max_count = 0
    max_seq = None
    freq = defaultdict(int)
    for seq in user_sequences.keys():
        count = len(user_sequences[seq])
        freq[seq] = count
        if count > max_count:
            max_count = count
            max_seq = seq
        elif count == max_count:
            if seq < max_seq:
                max_seq = seq

    # Step 5: Return the lexicographically smallest 3-sequence that has been visited by the largest number of users.
    return list(max_seq)

“`

Time Complexity:

The time complexity of this algorithm is O(N^3), where N is the length of the input arrays. This is because we need to iterate over all the possible 3-sequences for each user, which gives us a complexity of O(N^3).

Space Complexity:

The space complexity of this algorithm is O(N^2). We are using two dictionaries to store the browsing history and 3-sequences, respectively, for each user. The size of the 3-sequences dictionary is also O(N^2) because the maximum number of 3-sequences possible is N choose 3.

Step by Step Implementation For Analyze User Website Visit Pattern

/**
 * The idea is to use a map to store the user-website pairs and a set to store all unique websites.
 * Then, we can iterate through the map and check for each user, which websites he/she has visited.
 * */
 
public class Solution {
    public List mostVisitedPattern(String[] username, int[] timestamp, String[] website) {
        List res = new ArrayList<>();
        Map> map = new HashMap<>();
        Set set = new HashSet<>();
        
        for (int i = 0; i < username.length; i++) {
            if (!map.containsKey(username[i])) {
                map.put(username[i], new ArrayList<>());
            }
            map.get(username[i]).add(website[i]);
            set.add(website[i]);
        }
        
        Map count = new HashMap<>();
        int max = 0;
        String mostVisited = "";
        
        for (String user : map.keySet()) {
            List list = map.get(user);
            Set visited = new HashSet<>();
            for (String site : list) {
                visited.add(site);
            }
            
            for (String site1 : visited) {
                for (String site2 : visited) {
                    if (site1.equals(site2)) {
                        continue;
                    }
                    
                    for (String site3 : visited) {
                        if (site1.equals(site3) || site2.equals(site3)) {
                            continue;
                        }
                        
                        String pattern = site1 + "," + site2 + "," + site3;
                        if (!count.containsKey(pattern)) {
                            count.put(pattern, 0);
                        }
                        count[pattern]++;
                        if (count[pattern] > max) {
                            max = count[pattern];
                            mostVisited = pattern;
                        } else if (count[pattern] == max) {
                            mostVisited = mostVisited.compareTo(pattern) < 0 ? mostVisited : pattern;
                        }
                    }
                }
            }
        }
        
        String[] sites = mostVisited.split(",");
        for (String site : sites) {
            res.add(site);
        }
        return res;
    }
}

def most_common_pattern(log, k):
    # create a dictionary to store the count of each pattern
    pattern_count = {}
    
    # iterate over the log entries
    for i in range(len(log) - k + 1):
        # create a key for the dictionary by joining the first k elements of the log entry
        key = ','.join(log[i:i+k])
        
        # if the key is not in the dictionary, set its value to 1
        if key not in pattern_count:
            pattern_count[key] = 1
        # otherwise, increment the value by 1
        else:
            pattern_count[key] += 1
    
    # return the key with the highest value
    return max(pattern_count, key=pattern_count.get)

Your input will be an array of strings, each string representing a log entry.

Each log entry consists of two space-separated values: the user ID and the website visited.

For example, the log entry "a111 bbb ccc" represents a user visiting the website "bbb.com" for the first time.

Your task is to find three most visited websites for each user.

You may assume that there are no duplicate entries in the log.

function analyzeUserWebsiteVisitPattern(logs) {
  // create a map to store user IDs as keys and websites as values
  const userWebsites = new Map();
  // iterate over logs
  for (const log of logs) {
    // split log into user ID and website
    const [user, website] = log.split(" ");
    // check if user ID is in map
    if (userWebsites.has(user)) {
      // if so, retrieve the array of websites associated with that user ID
      const websites = userWebsites.get(user);
      // push the new website into the array
      websites.push(website);
      // update the map with the new array of websites
      userWebsites.set(user, websites);
    } else {
      // if not, create a new array with the website and store it in the map
      userWebsites.set(user, [website]);
    }
  }
  // create a map to store user IDs as keys and arrays of most visited websites as values
  const mostVisitedWebsites = new Map();
  // iterate over the map of user IDs and websites
  for (const [user, websites] of userWebsites) {
    // sort the websites in descending order of frequency
    const sortedWebsites = websites.sort((a, b) => websites.filter(v => v === b).length - websites.filter(v => v === a).length);
    // take the first three websites
    const mostVisited = sortedWebsites.slice(0, 3);
    // store them in the map
    mostVisitedWebsites.set(user, mostVisited);
  }
  // return the map
  return mostVisitedWebsites;
}

vector mostVisitedPattern(vector& username, vector& timestamp, vector& website) {
        unordered_map>> m;
        for (int i = 0; i < username.size(); ++i)
            m[username[i]].push_back({timestamp[i], website[i]});
        unordered_map cnt;
        int maxCnt = 0;
        vector res;
        for (auto& it : m) {
            set> patterns;
            for (int i = 0; i < it.second.size(); ++i) {
                vector pattern;
                for (int j = i + 1; j < it.second.size(); ++j) {
                    if (it.second[j].first - it.second[i].first > 3000) break;
                    pattern.push_back(it.second[j].second);
                    patterns.insert(pattern);
                }
            }
            for (auto& p : patterns) {
                string key = it.first + "#" + p[0] + "#" + p[1] + "#" + p[2];
                cnt[key]++;
                if (cnt[key] == maxCnt)
                    res.push_back(key);
                else if (cnt[key] > maxCnt) {
                    res = {key};
                    maxCnt = cnt[key];
                }
            }
        }
        for (auto& it : res) {
            it = it.substr(0, it.find('#'));
        }
        return res;
    }

using System; using System.Collections.Generic; using System.Linq; using System.Text; using System.Threading.Tasks; namespace ConsoleApplication1 { class Program { static void Main(string[] args) { string[] input = new string[] { "[email protected],trips,800", "[email protected],tv,200", "[email protected],tv,300", "[email protected],trips,400", "[email protected],trips,600", "[email protected],tv,1000" }; Console.WriteLine(Solution(input)); Console.ReadLine(); } public static IList> Solution(string[] input) { //To store the result IList> result = new List>(); //To store the unique products List products = new List(); //To store the unique email addresses List emails = new List(); //To store the count of products Dictionary productCount = new Dictionary(); //To store the count of email addresses Dictionary emailCount = new Dictionary(); //To store the count of products for each email address Dictionary> emailProductCount = new Dictionary>(); foreach (string s in input) { //Split the input string string[] temp = s.Split(','); //If the email address is not in the list, add it if (!emails.Contains(temp[0])) { emails.Add(temp[0]); emailCount.Add(temp[0], 1); emailProductCount.Add(temp[0], new Dictionary()); } //If the email address is already in the list, increment the count else { emailCount[temp[0]]++; } //If the product is not in the list, add it if (!products.Contains(temp[1])) { products.Add(temp[1]); productCount.Add(temp[1], 1); } //If the product is already in the list, increment the count else { productCount[temp[1]]++; } //Increment the count of products for the email address emailProductCount[temp[0]][temp[1]]++; } //To store the final result List> finalResult = new List>(); //Iterate through all the email addresses foreach (string email in emailProductCount.Keys) { //To store the products for the email address List temp = new List(); //To store the count of products for the email address Dictionary emailProdCount = emailProductCount[email]; //Iterate through all the products foreach (string prod in emailProdCount.Keys) { //If the count of products for the email address is greater than or equal to //the count of products divided by the count of email addresses, add it to the list if (emailProdCount[prod] >= (productCount[prod] / emails.Count)) { temp.Add(prod); } } //If the list is not empty, add it to the final result if (temp.Count != 0) { finalResult.Add(temp); } } //Return the final result return finalResult; } } }