Review and solution for problem 1

Problem Review:

Question: This problem was recently asked by Google.

Given a list of numbers and a number k, return whether any two numbers from the list add up to k.

For example, given [10, 15, 3, 7] and k=17, return true since 10 + 7 is 17.

Bonus: Can you do this in one pass?

Answer One

For this problem there are many ways to solve it, first being a brute force approach.

for i, num in enumerate(inputList, 1):
    for num2 in inputList[i:]:
        if num + num2 == k:
            return True
return False

This does check for the solution but is also very costly for time having O(n²) time complexity.

Answer Two

Assuming that the a space complexity of O(n) is acceptable, a better option would be to remember the previous numbers as you iterate the list the first time. To meet the requirement of O(n) however we need to store numbers we have seen in a way that is easy to recall. Python’s set() data structures have a constant lookup and insertions time since they are based on hash tables. Using a set to store the complements of any numbers we check will allow us to make only one pass of the data.

The following code runs in O(n) time and has a space complexity of O(n).

complementSet = set()

for num in inputList:
    if num in complementSet:
        return True
    elif (k - num) not in complementSet:
        complementSet.add(k - num)

return False

Conclusion

• The brute force options is O(n²) time complexity and O(1) space complexity.
• The complement set searching options is O(n) time complexity and O(n) space complexity.

The set searching algorithm here is much better and in general if you are having to check for values in lists using sets can save time by having their constant lookup costs.

If you have any questions feel free to send me a message though my LinkedIn or email provided in the footer.