roblox_karat.py

user0 = ["/start", "/pink", "/register", "/orange", "/red", "a"]
user1 = ["/start", "/green", "/blue", "/pink", "/register", "/orange", "/one/two"]
user2 = ["a", "/one", "/two"]
user3 = ["/pink", "/orange", "/yellow", "/plum", "/blue", "/tan", "/red", "/amber", "/HotRodPink", "/CornflowerBlue", "/LightGoldenRodYellow", "/BritishRacingGreen"]
user4 = ["/pink", "/orange", "/amber", "/BritishRacingGreen", "/plum", "/blue", "/tan", "/red", "/lavender", "/HotRodPink", "/CornflowerBlue", "/LightGoldenRodYellow"]
user5 = ["a"]




from typing import List, Tuple, Dict, Set

def parse_counts(counts: List[str]) -> List[Tuple[int, str]]:
    acc = []
    for line in counts:
        value = line.split(',')
        left = int(value[0])
        right = value[1].strip()
        acc.append((left, right))
    return acc

# print("blah.com"[:-4])

def get_all_subdomains(x: str) -> Set[str]:
    value = x.split('.')
    acc = []
    for word in reversed(value):
        if len(acc) == 0:
            acc.append(word)
        else:
            suffix = acc[-1]
            acc.append(word + "." + suffix)
    return acc

# print(get_all_subdomains("www.google.com"))  

def get_counts_by_subdomain(x: List[Tuple[int, str]]) -> Dict[str, int]:
    initial_result = {key: value for value, key in x}
    result = {}
    for domain, amount in initial_result.items():
        result[domain] = amount if domain not in result else result[domain] + amount
        sub_domains = [i for i in get_all_subdomains(domain) if i != domain]
        for sub_domain in sub_domains:
            result[sub_domain] = amount if sub_domain not in result else result[sub_domain] + amount
    return result

def final_answer(counts: List[str]) -> Dict[str, int]:
    return get_counts_by_subdomain(parse_counts(counts))

# print(final_answer(counts))

# print(get_counts_by_subdomain(parse_counts(counts)))
    
    

"""
We have some clickstream data that we gathered on our client's website. Using cookies, we collected snippets of users' anonymized URL histories while they browsed the site. The histories are in chronological order, and no URL was visited more than once per person.

Write a function that takes two users' browsing histories as input and returns the longest contiguous sequence of URLs that appears in both.

Sample input:

user0 = ["/start", "/pink", "/register", "/orange", "/red", "a"]
user1 = ["/start", "/green", "/blue", "/pink", "/register", "/orange", "/one/two"]


user2 = ["a", "/one", "/two"]
user3 = ["/pink", "/orange", "/yellow", "/plum", "/blue", "/tan", "/red", "/amber", "/HotRodPink", "/CornflowerBlue", "/LightGoldenRodYellow", "/BritishRacingGreen"]
user4 = ["/pink", "/orange", "/amber", "/BritishRacingGreen", "/plum", "/blue", "/tan", "/red", "/lavender", "/HotRodPink", "/CornflowerBlue", "/LightGoldenRodYellow"]
user5 = ["a"]

Sample output:

findContiguousHistory(user0, user1)
   /pink
   /register
   /orange

findContiguousHistory(user1, user2)
   (empty)

findContiguousHistory(user2, user0)
   a 

findContiguousHistory(user5, user2)
   a 

findContiguousHistory(user3, user4)
   /plum
   /blue
   /tan
   /red

findContiguousHistory(user4, user3)
   /plum
   /blue
   /tan
   /red

n: length of the first user's browsing history
m: length of the second user's browsing history

"""


"""
user0 = ["/start", "/pink", "/register", "/orange", "/red", "a"]
user1 = ["/start", "/green", "/blue", "/pink", "/register", "/orange", "/one/two"]  

{
    "/start": 0,
    "/pink": 1,
    "/register": 2
}
"""

user0 = ["/start", "/pink", "/register", "/orange", "/red", "a"]
user1 = ["/start", "/green", "/blue", "/pink", "/register", "/orange", "/one/two"] 

def find_common_history(user1: List[str], user2: List[str]) -> List[int]:
    index_map_user1 = {value: index for index, value in enumerate(user1)}  
    index0 = 0
    max_acc = None
    while index0 < len(user2):
        current_page = user2[index0]
        if current_page not in index_map_user1:
            index0 += 1
        else:
            acc = [index0, index0]
            index1 = index_map_user1[current_page]
            while user2[index0] == user1[index1]:
                index0 += 1
                index1 += 1
            acc[-1] = index0
            max_acc = max([max_acc, acc], key = lambda x: x[-1] - x[0]) if max_acc is not None else acc
    return user2[max_acc[0]: max_acc[-1]]

print(find_common_history(user0, user1))