Python Sum Two Number Interview Question:

As part of a recent interview, I was asked to take a few numbers within a list and find the combination of two numbers that equal the target.

The only caveat was to assume that there was only one solution. The numbers used on the assessment made that assumption possible, but from the wording, it seemed optional. ¯(ツ)/¯

# Global Variables
listNumbers = [2, 7, 11, 13] #List of number given by examiner
target = 9 #We want to check if any two number(non-repeated) equal the target

Solution 1: My Intuition This is how I naturally thought about solving the problem

#Solution 1: Brute Force
n=0 #used in While Loop

while n < len(listNumbers): #While the value of "n" is less than the number of objects in the
#list continue to iterate through the following code 
    for i in listNumbers:
        if i + listNumbers[n] == target and i != listNumbers[n]: #Create a multiple
          # conditional statement to find if the combination of numbers equals the target and
          # the numbers are unique.
            print((i,listNumbers[n]))
    n +=1

#Soultion 1.5: Another brute force approach(less code)

for i in listNumbers:
    if (target - i) in listNumbers:
        print(target-i,i)

Returns:

(7, 2)
(2, 7)
7 2
2 7

Solution 2: I took some additional time to think about the problem, and I came up with the following solution:

I had to use pseudocode, so I doubt I could have relied on importing a module, and it is unnecessary, but let’s take a look anyway.

#Solution 2: Using Python Modules
from itertools import combinations #imports the combinations module which has special
#functions/methods specific for dealing with combinations

adding = lambda a : a[0] + a[1] #Setup a quick anynomous function that will add the our 
#2-pair combinations together!
combs = combinations(listNumbers, 2) #the combination function does all the hard work and
#thinking for us, by splitting finding all of the unqiue combination of a list. 

for i in list(combs): #Lets loop through each of the combinations generated by the combinations module and print the outcome!
    if target == (adding(i)):
        print(i)

Returns:

(2, 7)

**Solution 3: **Let’s look online for the “right” Solution. I know my created solutions probably won’t scale well if we have to sort through a list with millions or billions of numbers.

Full Disclosure: I had to read what a hash table was to understand the solution.

# Solution 3: Using a Hash Table
def twoSumHashing(num_arr, pair_sum):
    hashTable = {} #intiate an empty hastable (Notice that this is expressed as a Python
    #dictonary. A hashtable is a lookup table with keys and values.)
    for i in range(len(num_arr)): # Loop through each element of our list of numbers
        complement = pair_sum - num_arr[i]
        #print complement
        if complement in hashTable: #we take the value of complement and check if that key has a value in our hashTable
            print(num_arr[i],complement)
        hashTable[num_arr[i]] = num_arr[i] #for each pass of the loop we will add the value of
        #index and map it to a key with the same value. 
        # In this example mapping the value with a corresponding key allows easy
        # use of the membership operation "in" to check for the result of complement in the
        # hashtable we are programatically creating. 
        #(E.g. the output will be the following for our list of numbers: 
        # {2: 2, 7: 7, 11: 11, 13: 13} )
    #print(hashTable)

# Execute function
twoSumHashing(listNumbers, target)

#I have added some print statements which can be commented out that will allow better
# understanding of the execution flow of this algorithm
#Source: https://www.educative.io/edpresso/how-to-implement-the-two-sum-problem-in-python

Returns:

Let’s understand why this is the “right” solution.

To understand why using a Hash Table is more efficient than most other solutions, we must understand time complexity. Great article for understanding time complexity:

https://www.geeksforgeeks.org/understanding-time-complexity-simple-examples/
https://medium.com/swlh/time-complexity-of-algorithms-big-o-notation-explained-in-plain-english-e12a11dc4a4f

Understanding Hashtables:

https://www.youtube.com/watch?v=KyUTuwz_b7Q
https://www.youtube.com/watch?v=shs0KM3wKv8

TL;DR Because the time to execute a program on different computer hardware with different software can vary between different setups, the amount of time it takes for a program to execute varies. Instead, by comparing the maximum number of steps to get the desired output by the number of inputs for your program(rules/algorithm), computer scientists can express the time-complexity(“time efficiency”) of a program.

Generally, we want to minimize the time complexity. There are maybe scenarios where it may not be practically feasible or beneficial.

By using a hashtable, it will allow our program to run at a constant time complexity in most situations. In the case that there are many errors, our program will run with linear time complexity.