###############################################################################
# -------- 15-112 Recitation #12: Sets, Dictionaries, Efficiency ------------ #

# This is a starter file of the problems we did in recitation. A good way to
# use this file is to try to re-write problems you saw in recitation from
# scratch. This way, you can test your understanding and ask on Piazza or
# office hours if you have questions :)

# --------------------------------------------------------------------------- #
###############################################################################
# Big Oh Analysis
###############################################################################
# LEARNING OBJECTIVES
# What is efficiency?
# What is Big O?
# How do we determine the efficiency of code?


def bigO1(L): #L is a list of length _
    count = 0 # O(_)
    for i in range(len(L)): # loops _ times
        count += L[i] # O(_)
        if sum(L[2:]) > max(L): # O(_)
            for j in range(i, len(L)): # loops _ times
                count += L[j] # O(_)
    return count # O(_)
# Overall - O(_)



def bigO2(L): # L is a list of length N
    i = 1 # O(_)
    listLength = len(L) # O(_)
    result = [] # O(_)
    while i < listLength: # loops _ times
        result += L[i] # O(_)
        i *= 3 # O(_)
    return result # O(_)
# Overall - O(_)



def bigO3(L): # L is a list of length N
    result = 0 # O(_)
    for elem in L: # loops _ times
        for c in string.ascii_letters: # loops _ times
            result += L.count(elem) # O(_)
    return result # O(_)
# Overall - O(_)



def bigO4(a): # a is a list of length N
    for i in range(len(a)): # loops _ times
        j = 1 # O(1)
        while j < len(a): # O(_)
            j *= 2  # O(_)
    return a # O(_)
# Overall - O(_)


###############################################################################
# Most Common Website
###############################################################################
# LEARNING OBJECTIVES
# How do we use sets and dictionaries?
# How do we make our code more efficient?
'''
As a busy CMU student, you notice that you’re getting distracted a lot while 
you’re trying to work and decide to put that to rest by using your internet history 
to track which sites you visit the most. Luckily, since you’re a superstar 112 
student who just learned about efficiency, you can do this analysis super fast.

Write the function mostCommonWebsite, that takes a browser history (list  
of strings) such as ["google.com", "agar.io", "cs.cmu.edu/~112", "agar.io"], 
and returns a set of the most commonly visited sites in this list (in this case, 
there is only one most common site ("agar.io"), so we return {"agar.io"}). If there 
is more than one most common site, then return a set containing all of them. So, 
mostCommonWebsite(["cs.cmu.edu/~112", "agar.io", "cs.cmu.edu/~112", "google.com", "agar.io"]) 
returns the set {"agar.io", "cs.cmu.edu/~112"} since both occur twice. Your solution 
should run in O(n) where n is the length of your history.
'''

def mostCommonWebsite(history):
	return 42




###############################################################################
# In Room At Time
###############################################################################
# LEARNING OBJECTIVES
# How do we solve a problem using sets and dictionaries?
# How do we write efficient code?


'''
Monday, June 10, Bikini Bottom: The secret recipe for the Krabby Patty has gone 
missing. Mr. Krabs comes to CMU and wants your help to help him figure out who 
took the recipe from his secret vault in his office. He brings to you a list of 
(time, person) logs that record who used the door to his office and at what time. 
For example, for a log list of logs = [(0, 'Krabs'), (10, 'Spongebob'), (25, 'Krabs'), 
(30, 'Krabs'), (35, 'Spongebob'), (420, 'Krabs')] means that Krabs entered at 
time 0, left at time 25, and re-entered at time 30, and re-exited at time 420, and 
Spongebob entered at time 10 and exited at time 35.

Using this log file, Krabs wants to be able know who was in his office at any time, 
but he does not know how to do this :’(. Luckily, with your knowledge of sets and 
dictionaries, you can do this for him very easily! Write the function
inRoomAtTime(logs, t) that returns a set of all people in Krabs’ office at time t. 
Your solution should run in O(n), where n is the number of entries seen before 
reaching time t.

For example, using the log file above, inRoomAtTime(logs, 10) == inRoomAtTime(logs, 15) 
would return the set of {‘Krabs’, ‘Spongebob’} and inRoomAtTime(logs, 40) would 
return the set {‘Krabs’}.
'''

def inRoomAtTime(logs, t):
	return 42