1. two sum

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?

def two_Sum(nums, k):
    if len(nums) < 2: return False
  s = set()
  for num in nums:
    if num in s:
      return True
    else:
      s.add(k - num)
  return False

• This would be O(N) since lookups of sets are O(1) each

def two_sum(nums, k):
  nums.sort() 
  for i in range(len(nums)):
    target = k - nums[i]
    j = binary_search(nums, target, 0, len(nums)-1)
    if j == -1:
      continue
    elif j != i:
      return True
    elif j + 1 < len(nums) and nums[j + 1] == target:
      return True
    elif j - 1 >= 0 and nums[j - 1] == target:
      return True
  return False

def binary_search(nums, k, l, r):
  if l > r: return False
  mid = (l + r) // 2
  if nums[mid] == k:
    return mid
  elif nums[mid] > k:
    return binary_search(nums, k, 0, mid - 1)
  else:
    return binary_search(nums, k, mid + 1, r)

• run binary search on N elements, this would take O(N log N) with O(1) space.

  • sort