webdev: (Default)
[personal profile] webdev
This is the first of the interview questions, and is a very common one: given an array of random integers, output all the pairs that add to a given sum k.

In the original article, Arden mentions the brute force method only in passing. For the sake of completeness, here it is:
function bruteForce(arrIntegers, k) {
    var i = 0,
        j = 0,
        arrIntegersLength = arrIntegers.length,
        arrReturn = [];

    for (i = 0; i < arrIntegersLength; i++) {
        var currentTarget = arrIntegers[i],
            strResult = currentTarget + " + ";
        for (j = 0; j < arrIntegersLength; j++) {
            if ((currentTarget + arrIntegers[j]) === k) {
                strResult = strResult + arrIntegers[j];
                arrReturn.push(strResult);
                break;
            }
        }
    }
    return arrReturn;
}

For each element in the array, the brute force method loops through the entire array again, so the complexity of this solution is O(N^2) which is pretty bad. This solution also doesn't check for duplicates or other edge conditions.

Quick digression from the code: Arden writes that he wouldn't necessarily mention the brute force solution in an interview. I agree somewhat; you definitely wouldn't want to write that as your final solution to the problem. But if I were in a stressful interview or were otherwise having problems thinking of a more optimal solution, getting a suboptimal solution on the board can help me think through the problem and often the optimal solution will come to me as a result. So plenty of times I have written a suboptimal solution on the white board (all the while acknowledging that it is suboptimal) and then walked through improvements, arriving finally at an optimal solution. It's been a useful technique that helps me get where I need to go, while also illustrating my understanding of optimization and overall way of thinking about the problem--all very useful things to do in an interview. So if all you can think about is the brute force solution try throwing it up and see if it helps you work through the problem.

The next solution Arden mentions is a sorting solution:
A more efficient solution would be to sort the array and having two pointers to scan the array from the beginning and the end at the same time. If the sum of the values in left and right pointers equals to k, we output the pair. If the sum is less than k then we advance the left pointer, else if the sum is greater than k we decrement the right pointer, until both pointers meet at some part of the array. The complexity of this solution is O(NlogN) due to sorting.
Here's the corresponding JavaScript:
function betterSolution(arrIntegers, k) {
    var intLeft = 0,
        arrIntegersLength = arrIntegers.length;
        intRight = arrIntegersLength - 1,
        arrReturn = [];

    arrIntegers.sort();

    while (intLeft < intRight) {
        var currentSum = arrIntegers[intLeft] + arrIntegers[intRight];
        if (currentSum === k) {
            arrReturn.push(arrIntegers[intLeft] + " + " + arrIntegers[intRight]);
            intLeft += 1;
        } else if ( currentSum < k) {
            intLeft += 1;
        } else {
            intRight -= 1;
        }
    }
    return arrReturn;
}

This looks a lot like Arden's Python solution; really the main difference is how I've constructed (and optimized) my loop and returned the result.

The optimal solution is a little more clever:
The O(N) algorithm uses the set data structure. We perform a linear pass from the beginning and for each element we check whether k-element is in the set of seen numbers. If it is, then we found a pair of sum k and add it to the output. If not, this element doesn’t belong to a pair yet, and we add it to the set of seen elements.
Arden's Python solution uses the the set data structure which is basically associative arrays with lots of convenience methods, so that's an easy translation into a JavaScript associative array:
function optimalSolution(arrIntegers, k) {
    var arrSeen =[],
        arrReturn = [],
        i = 0, 
        arrIntegersLength = arrIntegers.length;
        
    for (i = 0; i < arrIntegersLength; i++) {
        var intTarget = k - arrIntegers[i];
        if (arrSeen.indexOf(intTarget) === -1) {
            arrSeen.push(arrIntegers[i]);
        } else {
            arrReturn.push(Math.min(arrIntegers[i], intTarget) + " + " + Math.max(arrIntegers[i], intTarget));
        }
    }
    return arrReturn;
}

Again very much like Arden's original Python solution. Different loop structure, but essentially the same implementation of the algorithm.

That's the first problem. Stay tuned for the others, and be sure to check out the original blog posts.

Profile

webdev: (Default)
Jon Reid

October 2013

S M T W T F S
  12 345
6789101112
13141516171819
20212223242526
272829 3031  

Links