Profile picture

Co-founder @ RMOTR

#1 Interview Questions - Sum of Numbers (Google)

Last updated: November 27th, 20182018-11-27Project preview

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

In [1]:
import utils
In [3]:
utils.render(filename='results.svg')
Out[3]:

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 👉


Problem definition

Given a list containing integers in (ascending) order, and a target value; for example 16:

In [3]:
l = [1, 3, 5, 8, 12, 13, 22]
In [2]:
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

Function definition:

In [4]:
def has_pair_with_sum(a_list, a_target):
    pass

With our original list:

In [6]:
l1 = [1, 3, 5, 8, 12, 13, 22]
In [ ]:
assert has_pair_with_sum(l1, 16) is True # 3 + 13

assert has_pair_with_sum(l1, 19) is False

A smaller list:

In [ ]:
l2 = [1, 3, 5]
In [ ]:
assert has_pair_with_sum(l2, 6) is True # 1 + 5

assert has_pair_with_sum(l2, 2) is False

Solution(s)

I'll be posting the FIRST solution tomorrow! There are several options and I'll try to add all of them in the following days along with explanations. Stay tuned!

Notebooks AI
Notebooks AI Profile20060