I was asked in a telephone interview how to find out if there are two numbers in
a list that sum to a certain value. I did an O(N^2) algorithm, then refined it to an O(n lg n) algorithm. Unfortunately, there’s an O(n) algorithm which I didn’t think of on the phone but came up with after the fact:

def somePair(values, Z):
    """
    Given a list of numbers and value Z, are there any pair of numbers such that X+Y = Z?
    This does this in O(N) time looking at each value, val, and checking if Z-val is
    already in a lookup table.
    """
    lookup = set()         # Store the values
    for val in values:
        diff = Z - val
        if diff in lookup:
            return True
        else:
            lookup.add(val)
    return False
if __name__ == '__main__':
    assert somePair([], 4) == False
    assert somePair([4], 4) == False
    assert somePair([1,2,3,4], 1) == False
    assert somePair([1,2,3,4], 2) == False
    assert somePair([-8, 12], 4)
    assert somePair([1,2,3,4], 3)
    assert somePair([1,2,3,4, 4], 3)
    assert somePair([1,2,3,4], 4)