#1 RESOLVED: This exercise is already resolved and the solutions are posted, as long with some performance results.
This problem was introduced by Google as part of their interview process. See the original video here. You can fork this project and take a stab at it before looking at the solutions.
One of the most interesting things about this problem is that there are multiple solutions, with advantages and disadvantages. I've implemented a few proposed and they're included as part of the project. Here's a summary:
You can fork this project and start working immediately, the definition and a few tests are in
Your Code.ipynb on the right side bar 👉
Given a list containing integers in (ascending) order, and a target value; for example
l = [1, 3, 5, 8, 12, 13, 22]
target = 16
Can you find a pair of numbers whose sum equals the target number?
In our previous example, the answer is YES because
3 + 13 == 16
Some important clarifications¶
- The list is SORTED in ascending order.
- There are NO repeated numbers
- Your job is to answer yes/no, that is, a boolean (you don't need to return the pair or the positions).
- You can't add a number with itself (these would be no valid:
1 + 1,
3 + 3, etc.)
- You can use any programming language. I personally prefer Python, but feel free to use your own.
Some final tests to complement the explanation¶
def has_pair_with_sum(a_list, a_target): pass
With our original list:
l1 = [1, 3, 5, 8, 12, 13, 22]
assert has_pair_with_sum(l1, 16) is True # 3 + 13 assert has_pair_with_sum(l1, 19) is False
A smaller list:
l2 = [1, 3, 5]
assert has_pair_with_sum(l2, 6) is True # 1 + 5 assert has_pair_with_sum(l2, 2) is False