Recently, I Have been researching common coding interview-problems and I’ve discovered that most of the major tech companies like Google or facebook have overlapping problem lists. One of these problems is called
Pair With Sum and it states the following
Find a pair of elements from an array whose sum equals a given number.
This request is a bit ambiguous - so let’s start out by listing all the assumptions that we are making before we begin working on a solution:
- The array contains only integers
- The array can have duplicates
- Return a boolean that indicates if the list has such a pair
- We will start with an ordered (ascending order) list example
Lets code the most naive solution. Basically, try every pair possible and see if their sum is equal to the given number. It would look like this in Ruby
1 2 3 4 5 6 7 8 9 10
This solution would work whether the list is sorted or not. However, this is an inefficient way of solving the problem, indicated by the complexity of this algorithm at O(n2). This will get out of control pretty quickly for large arrays. We need a solution that has a linear complexity or a O(n). Let’s explore another solution where we assume that the array elemets are sorted.
1 2 3 4 5 6 7 8 9 10 11 12
This solution has the algorithm complexity of O(n) we are looking for, making it much more scalable and efficient. Let’s go over the solution briefly. We have one pointer at the begining of the array and one at the end. we sum the value pointed with the two pointer
- If the sum is equal to the given number then we have found a solution
- If the sum is greater than the given number then the sum is too big, so we move the last pointer to the value before it
- If the sum is smaller than the given number then the sum is too small so we move the last pointer to the value after it
Saving the Complement
Imagine now that our list is not ordered, In this case, the previous method would not work. We need to come up with another algorithm with a linear complexity to retain our scalability. We note that in order for us to determine if a number has a pair, that the sum would equal to the given number, it needs to have its complement in the array. Let’s assume that the first element of the array is 2 and that the given number is 8- the complement of 2 to make 8 is
8-2=6. If we find 6 in the array, we know that it represents a valid pair.
Here’s an example:
array = [1,3,2], given_number = 4
Let’s go through this array and save the complements in some data structure. The ideal data structure in this case would be some kind of hash that would save only keys. The reason why we would choose this data structure is because it will ensure our collection constantly maintains unique elements (no redundancy) and it will do the element look up in a constant complexity O(1). In Ruby we can use the Set library.
Back to our array traversal. The first element is 1, its complement is (4-1=3), let’s add this complement to the complements set. The second element is 3, this number is a complement of a previous element, therefore we have a valid pair here. Let’s code the method that would do that:
1 2 3 4 5 6 7 8 9 10 11 12 13 14
Let’s prove that the best solution is not the brute force method by using the
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
The brute force solution is 73.24 times slower than the unordered list algorithm. The unordered list algorithm is 1.46 times slower that the ordered list algorithm (very insignificant difference).
As you can see, there are multiple ways to solve an these common interview questions. Each method would lead to a perfect linear complexity solution. Ensuring you have identified the right assumptions is essential in solving similar problems.