Google Interview (Unordered Sets)

I was just watching a YouTube video where two software engineers go over an interview problem they might present to a potential candidate. In the video, the candidate (the second engineer) is given a set of numbers and must find a pair that equals a specific sum.

Two sets of numbers are presented:

[1, 2, 3, 9 ] Sum = 8
[1, 2, 4, 4 ] Sum = 8

I immediately thought about a linear search with a double for loop.

bool hasPair(const vector<int>&data, int sum)
{
    for(int x = 0; x < data.size() - 1; x++)
        for(int y = 1; y < data.size() - 1; y++)
            if(data[x] + data[y] == sum)
                return true;
} - or something like that

The second engineer also presented the same solution and I thought, "Ya! I got it right." Whereas that solution would solve the problem, the double for loop takes too long and Google is looking for a faster solution.

The second engineer then presented an interesting solution. He mentioned starting at the first number and the last number and checking each pair until they met in the middle. Either the last element would decrease by one if the sum was higher than the desired sum, or the first element would increase by one if the sum was less than the desired sum.

Although I didn't come up with that solution, I understood the logic behind it and thought that it was beautiful.

bool hasPair(const vector<int>&data, int sum)
{
    int low = 0;
    int high = data.size() - 1;
    while(low < high)
        int s = data[low] + data[high];
        if( s == sum)
            return true;
}

At this point the first engineer stopped him and introduced a new problem. The numbers could no longer be considered sorted. I immediately though to myself, "Well, I would just run a sort command on the array." Again, that would be a linear search and would take too much time. They wanted another solution without using the sort function.

This is where I came across a new concept for me, and maybe a new concept for you. The second engineer devised a solution using an unordered set.

Unordered sets are containers that store unique elements in no particular order, and which allow for fast retrieval of individual elements based on their value.

They are initialized like this: unordered_set<datatype>variableName

For this problem, the second engineer decided to go through each number and store the integer needed to equal the sum in the unordered_set. With each number, the program would look to see if the required pair had been stored in the unordered_set. This means the program only has to perform a single loop to find the solution.

For example. in the first array instance [1, 2, 3,9] - 1 requires a 7, so 7 gets stored in the unordered_set. 2 requires 6. 3 required 5. Lastly, 9 is too high. None of the required pairs exists in the unordered_set, so the function returns false.

This method also takes into consideration any duplicate numbers, such as the 4s in the second array, a lack of any numbers, and the possibility of a single number in the array.

Final Solution:

bool hasPair(const vector<int>&data, int sum)
{
    unordered_set<int>comp; //complementary pairs
    for (int value:data)
    {
        if (comp.find(value) != comp.end)
            return true;
        comp.add(sum - value);
    }
    return false;
}

Nice. You can check out more about unordered_set(s) at:
(http://www.cplusplus.com/reference/unordered_set/unordered_set/)

And watch the movie at:
(https://www.youtube.com/watch?v=XKu_SEDAykw)

Another tool in the box!