JavaScript Interview Question 4: Find the missing element

[webdev]

Continuing with the series on JavaScript interview questions, here is Question 4: Given an array of non-negative integers, a second array is created by shuffling the first array and removing one integer. Find the missing integer.

As Arden discusses in his post, the brute force solution is super-simple: for every element in the second array, check to see if it exists in the first array.

function bruteForce(arr1, arr2) {
    var i = 0,
        j = 0,
        arr1Length = arr1.length,
        arr2Length = arr2.length,
        returnVal = -1;

    for (i = 0; i < arr1Length; i++) {
        var currTest = arr1[i],
            boolFound = false;
        for (j = 0; j < arr2Length; j++) {
            if (currTest === arr2[j]) {
                boolFound = true;
            }
        }
        if (boolFound === false) {
            returnVal = arr1[i];
        }
    }
    return returnVal;
}

Arden notes that this is highly inefficient, with a complexity of O(N^2). JavaScript doesn't give us any advantages here.

Arden also suggests a slightly more efficient solution can be had by sorting the arrays and comparing them one off. Since most sorting algorithms have a complexity of O(NlogN) that would be the most expensive part of that solution:

function betterMethod(arr1, arr2) {
    var i = 0,
        arr1Length = arr1.length,
        arr2Length = arr2.length,
        returnVal = -1;
    
    arr1.sort();
    arr2.sort();
    
    for (i = 0; i < arr1Length; i++) {
        var test1 = arr1[i],
            test2 = arr2[i];

        if (test1 !== test2) {
            returnVal = test1;
            i = arr1Length;
        }
    }
    return returnVal;
}

Here is the optimized solution that Arden suggests, using XOR (you can read the details on his post, it's really very clever and I don't think I would have ever thought of this solution myself).

function optimalMethod(arr1, arr2) {
    var i = 0,
        totArray = [],
        totArrayLength = arr1.length + arr2.length,
        returnVal = 0;
        
    totArray = totArray.concat(arr1, arr2);
    
    for (i = 0; i < totArrayLength; i++) {
        returnVal ^= totArray[i];
    }
    return returnVal;
}

Finally, there is a JavaScript specific solution that utilizes Array.indexOf:

function javaScriptSpecific(arr1, arr2) {
    var i = 0,
        arr1Length = arr1.length,
        returnVal = -1;
    
    for (i = 0; i < arr1Length; i++) {
        if (arr2.indexOf(arr1[i]) < 0) {
            returnVal = arr1[i];
        }
    }
    return returnVal;
}

This technique has a complexity of O(N), on par with Arden's clever solution.