###############################################################################
# ------------------ 15-112 Recitation Week 8: 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 O Analysis
###############################################################################


def bigO1(L):  # L is a list of length N
    count = 0  # O(_)
    for i in range(len(L)):  # loops _ times
        count += L[i]  # 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
        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(_)
        while j < len(a):  # loops _ times
            j *= 2  # O(_)
    return a  # O(_)
# Overall - O(_)


###############################################################################
# Get Pair Sum
###############################################################################
"""
Write the function getPairSum(a, target) that takes a list of numbers
and a target value (also a number), and if there is a pair of numbers
in the given list that add up to the given target number, returns that pair,
and otherwise returns an empty list. If there is more than one valid pair, you
can return any of them. You should write two different versions, one that runs
in O(n**2) and the other in O(n). (or just do the O(n) one)
"""


def getPairSum(a, target):
    return [42, 0]


def testGetPairSum():
    print("Testing getPairSum...", end="")
    assert(getPairSum([1], 1) == [])
    assert(getPairSum([5, 2], 7) in [[5, 2], [2, 5]])

    # (can return [10, -8] or [-1,3] or [1,1])
    assert(getPairSum([10, -1, 1, -8, 3, 1], 2) in [[10, -8], [-8, 10],
                                                    [-1, 3], [3, -1],
                                                    [1, 1]])

    assert(getPairSum([10, -1, 1, -8, 3, 1], 10) == [])
    assert(getPairSum([1, 4, 3], 2) == [])
    print("Passed!")


###############################################################################
# Most Common Name
###############################################################################
'''
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). (or just do the O(n) one)
'''


def mostCommonName(L):
    return {42}


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!")