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.

goog-a-1.py

#
# 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))

goog-a-2.py

#
# 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))

goog-a-3.py

#
# 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))

goog-b.py

#
# 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))

goog-c.py

#
# 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))