This problem was recently asked by Google.
Given a list of numbers and a number k, return whether any two numbers from the list add up to k.
For example, given [10, 15, 3, 7] and k of 17, return true since 10 + 7 is 17.
Bonus: Can you do this in one pass?
Very Bad Solution:
def add_up_to_k_v1(mylist, k): ans = [x+y==k for x in mylist for y in mylist] return sum(ans) > 0
My Original Solution Demo
def add_up_to_k_v2(mylist, k): for i, num in enumerate(mylist): if k-num in mylist: return True return False assert add_up_to_k_v1(mylist, k) == True, 'fail' assert add_up_to_k_v2(mylist, k) == True, 'fail'
Zyaad Jaunoo: Using a “set” instead of a list will bring down the complexity to nlogn.