Skip to content

Instantly share code, notes, and snippets.

@gpiancastelli
Last active August 17, 2018 08:45
Show Gist options
  • Save gpiancastelli/69da3823a4c6b5c7892b14a0d23f01e4 to your computer and use it in GitHub Desktop.
Save gpiancastelli/69da3823a4c6b5c7892b14a0d23f01e4 to your computer and use it in GitHub Desktop.
Given a sequence of numbers and a value, find a couple of numbers in the sequence whose sum is equal to value. This is the problem Google showcases in their example coding/engineering interview at https://youtu.be/XKu_SEDAykw. This Gist contains possible solutions written in Python.
#
# The first (intuitive but inefficient) solution is to nest two loops
# on the sequence, with the second loop shifted by one w.r.t the first.
#
# Since Python does not offer the same kind of for instruction that
# C-based languages find so suitable to this kind of looping, the
# implementation of this solution uses while loops.
#
def find_pair_with_sum(numbers, s):
i = 0
while i < len(numbers):
a = numbers[i]
j = i + 1
while j < len(numbers):
b = numbers[j]
if a + b == s:
return (a, b)
j += 1
i += 1
# let's try it with some samples
n1 = [1, 2, 3, 9]
n2 = [1, 2, 4, 4]
s = 8
print(find_pair_with_sum(n1, s))
print(find_pair_with_sum(n2, s))
#
# Nonetheless, you can write the same solution using for loops,
# introducing an index only when is needed, and exploiting the
# iterative nature of the loop otherwise.
#
# For loops in Python are easier to read and more compact to
# write than their C-based language equivalent.
#
def find_pair_with_sum(numbers, s):
for i, a in enumerate(numbers):
for b in numbers[i + 1:]:
if a + b == s:
return (a, b)
# let's try it with some samples
n1 = [1, 2, 3, 9]
n2 = [1, 2, 4, 4]
s = 8
print(find_pair_with_sum(n1, s))
print(find_pair_with_sum(n2, s))
#
# An even cleaner solution is to use some of the "batteries included"
# that Python gives you in the standard library. The gist of this first
# solution is to check the combinations of numbers in the sequence, and
# there's an app, I mean, a function in the itertools module for that.
#
import itertools
def find_pair_with_sum(numbers, s):
for a, b in itertools.combinations(numbers, 2):
if a + b == s:
return (a, b)
# let's try it with some samples
n1 = [1, 2, 3, 9]
n2 = [1, 2, 4, 4]
s = 8
print(find_pair_with_sum(n1, s))
print(find_pair_with_sum(n2, s))
#
# What happens when we do not want to incur the performance penalties
# of doing nested loops?
#
# If we are guaranteed that the number in the sequence are sorted,
# we can resort to using a couple of indices to traverse the sequence
# from the beginning onward and from the end inward, comparing the sum
# of the indexed numbers with the required value and moving indices on
# the basis of this comparison, until the indices overlap with each other.
#
def find_pair_with_sum(numbers, s):
lo, hi = 0, len(numbers) - 1
while lo < hi:
a, b = numbers[lo], numbers[hi]
total = a + b
if total < s:
lo += 1
elif total > s:
hi -= 1
else:
return (a, b)
# let's try it with some samples
n1 = [1, 2, 3, 9]
n2 = [1, 2, 4, 4]
s = 8
print(find_pair_with_sum(n1, s))
print(find_pair_with_sum(n2, s))
#
# And what if the sequence is not sorted?
#
# Then we need to "compensate" using some sort of storage to remember
# what numbers we have seen while traversing the sequence in a form
# that would be easy to test for "compatibility" with the subsequent
# numbers.
#
def find_pair_with_sum(numbers, s):
complements = set()
for n in numbers:
if n in complements:
return (s - n, n)
complements.add(s - n)
# let's try with some samples
n1 = [1, 9, 3, 2]
n2 = [4, 2, 1, 4]
s = 8
print(find_pair_with_sum(n1, s))
print(find_pair_with_sum(n2, s))
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment