Skip to content

Instantly share code, notes, and snippets.

Show Gist options
  • Save miku/741526 to your computer and use it in GitHub Desktop.
Save miku/741526 to your computer and use it in GitHub Desktop.
Given a sorted array of integers and a target integer, find a pair of integers in the array that sum to the target in linear time.
#!/usr/bin/env python
# http://www.disinformatics.com/blog/2010/12/14/a-google-internship-interview-question-in-scala/
# The question is:
# given a sorted array of integers and a target integer,
# find a pair of integers in the array that sum to the target in linear time.
# The Solution
#
# A solution is to initialise two pointers to the ends of the array and
# compute the sum of the two elements pointed to. If the sum equals the
# target, we’re done.
#
# If not, it either exceeds the target (in which case we can decrease our
# candidate solution by the smallest amount possible in a unique way:
# decrementing the upper pointer) or is too small (in which case we perform
# the dual operation and increment the lower pointer).
#
# We repeat this process (via a while loop or recursion) until we find a
# solution or the pointers cross (if they cross, there was no pair of distinct
# elements of the array that summed to the target).
#
# It’s linear time because on each pass of the loop/recursion, the algorithm
# either terminates (by success or pointers crossing) or the distance between
# the pointers decreases by one. Therefore in the worst case (i.e. termination
# as late as possible), the pointers meet and force termination – they must
# have jointly travelled n places, where n is the length of the array.
# Therefore it’s O(n) – linear time.
# in python ...
import random
a = sorted([ random.randint(0, 100) for x in range(100) ])
target = sum(random.sample(a, 2))
right = len(a) - 1
left = 0
counter = 0
while not a[left] + a[right] == target:
if a[left] + a[right] > target:
right -= 1
else:
left += 1
counter += 1
print 'counter/len(a):', counter, len(a)
print 'target:', target
print 'index left/right: %s/%s' % (left, right)
print 'values left/right: %s/%s' % (a[left], a[right])
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment