basic interview question

# QUESTION: Given a list of size N and an integer k, find out
# whether there are any two numbers in the list that add up to k.


l = [1, 2, 3, 4, 5]

def f1(x, k):
    # O(n^2), brute force method
    for i in range(len(x)):
        for j in range(i+1, len(x)):
            if x[i] + x[j] == k:
                return True
    return False

print("f1")
print(f1(l, 8))
print(f1(l, 9))
print(f1(l, 10))


from bisect import bisect_left as bl
def f2(x, k):
    # O(n * log(n)), binary search method
    for i in range(len(x)):
        b = k - x[i]
        j = bl(x, b)
        if (
            j in range(len(x))
            and i != j
            and x[i] + x[j] == k
        ):
            return True
    return False


print("f2")
print(f2(l, 8))
print(f2(l, 9))
print(f2(l, 10))


def f3(x, k):
    # O(n), dictionary method
    d = {}
    for index in range(len(x)):
        value = x[index]
        d[value] = index
    for i in range(len(x)):
        c = k - x[i]
        if c in d and i != d[c]:
            return True
    return False


print("f3")
print(f3(l, 8))
print(f3(l, 9))
print(f3(l, 10))