Extra Practice for Week 8 (Due never)


  1. mostCommonName(L) in O(n) time
    Write the function mostCommonName, that takes a list of names (such as ["Jane", "Aaron", "Cindy", "Aaron"], and returns the most common name in this list (in this case, "Aaron"). If there is more than one such name, return a set of the most common names. So mostCommonName(["Jane", "Aaron", "Jane", "Cindy", "Aaron"]) returns the set {"Aaron", "Jane"}. If the set is empty, return None. Also, treat names case sensitively, so "Jane" and "JANE" are different names. You should write three different versions, one that runs in O(n**2), O(nlogn) and O(n). 
    def mostCommonName(L):
    return 42 # place your answer here!

def testMostCommonName():
    print("Testing mostCommonName()...", end="")
    assert(mostCommonName(["Jane", "Aaron", "Cindy", "Aaron"])
           == "Aaron")
    assert(mostCommonName(["Jane", "Aaron", "Jane", "Cindy", "Aaron"])
           == {"Aaron", "Jane"})
    assert(mostCommonName(["Cindy"]) == "Cindy")
    assert(mostCommonName(["Jane", "Aaron", "Cindy"])
           == {"Aaron", "Cindy", "Jane"})
    assert(mostCommonName([]) == None)
    print("Passed!")

testMostCommonName()

  2. Code Tracing: indicate what each of the following will print: 
    def ct1(n):
    s, t = set(), set()
    while (n   > 0):
        (d, n) = (n%10, n//10)
        if  (d in t): t.remove(d)
        elif   (d in s): t.add(d)
        s.add(d)
    return sorted(t)
print(ct1(13051231))
    

def ct2(d, key):
    while (key in d) and ((key+2) not in d):
        d[key+2] = key+1
        key = d[key]
    L = [ ]
    for key in  sorted(d.keys()):
        L.append(10*key + d[key])
    return L
print(ct2({1:5, 0:2}, 0))

  3. Reasoning over Code: For each function, give an input that makes the function return True: 
    def rc1Helper(d): 
    s = ""
    for key in d: 
        if key % 2 == 0: 
            s += d[key] 
    return s

def rc1(d): 
    assert(sorted(d.keys()) == list(range(0,4)))
    s = rc1Helper(d) 
    return s == "good luck!"



def rc2(d):
    i = j = k = m = 0
    for key in d:
        i += 1
        value = d[key]
        if (key == value):
            j = min(value, j)
            k = max(value, k)
        else:
            m += 1
    return ((i, j, k, m) == (4, -2, +2, 1))

  4. mostCommonWebsite(L)
    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.

  5. mostPopularFriend(d)
    Recall that friendsOfFriends(d) takes a dictionary d like this: 
        d = dict()
    d["fred"] = set(["wilma", "betty", "barney"])
    d["wilma"] = set(["fred", "betty", "dino"])
    With this in mind, write the function mostPopularFriend(d) that takes a dictionary of that form, and returns the name that occurs the most number of times in all the sets of friends. In the example above, mostPopularFriend(d) would return "betty". You may assume that there is exactly one such name, so ignore ties.

  6. findTriplets(L)
    Write the function findTriplets(L) that takes as input a list L of integers of length N and returns a set of all triplets in the list whose sum is equal to 0. For example, if the given list is [-1, 0, -3, 2, 1], you should return {(1, 0, -1), (-3, 2, 1)} (or any permutation of those numbers). If there is no valid triplet, you should return the empty set. You may assume that L is a list containing only integers. The "naive" solution would use 3 loops to check all triplets of values in L. You should use sets and/or dictionaries to do this in a faster way.