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:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 |
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) |