Interview Questions

There are several way in which this puzzle can be solved. One of them is to first sort the numbers and then to check if the sum of first and last value in the array is equal to k. If the sum is formed by these two values is smaller than k then you move your left index by one to larger number. If sum however is greater than k, then you move your right index. We print the sum and move both left and right index if sum is equal to k. Note that this solution does not use extra memory and overall finds the answer in O(nlogn), that is because sorting takes O(nlogn), visiting all values from left and right is O(n).

void printPairs(vector<int> &a, int k)
{
    std::sort(a.begin(), a.end()); //sort input numbers in-place O(nlogn)
    int  i=0;
    int j=a.size()-1;
    while(i < j)
    {
        int sum = a[i] + a[j];
        if (sum == k)
        {
            std::cout << a[i] << ", " << a[j] << std::endl;
            i++;
            j--;
        }
        else if (sum < k)
        {
            i++;
        }
        else
        {
            j--;
        }
    }  
}

Another solution is to use hash table. For each value if check if there is corresponding value in hash table that would form a sum. If not you add value to hash table and continue. If the pair is found you print both numbers and remove them from hash table. This apporach gives us O(n) running time but requires additional O(n) space for hash table.

void printPairs(vector<int> &a, int k)
{
    unordered_map<int, int> m;
    for (size_t i = 0; i<a.size(); ++i)
    {
        int neededValue = k - a[i];
        if (m.find(neededValue) != m.end() && m[neededValue] > 0)
        {
            std::cout << a[i] << ", " << neededValue << std::endl;
            m[neededValue]--;
        }
        else
        {
            m[a[i]]++;
        }
    }
}

Array pair sum