Video Game Pulse

Problem

In a recent project I was tasked with creating a function which would go through a list of phone numbers and identify which ones were duplicates. It seemed like a simple task which could be tackled with a for loop and some arrays; however, upon diagnosing the potential scale of the function’s usage, I determined that I needed to think this thing through quite a bit more to make it scalable.

I won’t bore you with the math, but the jist of it is that my initial instinct to use for loops and arrays would have meant my algorithm was O(n2), which means that if I put in 5 numbers, it would loop through 25 times in order to identify the duplicates. Scaling this up to 50 phone numbers would mean 250 loops!

Solution

The solution was to use objects instead of arrays, which allows me to use hash functions to point directly for what I’m searching for; the algorithm is O(n), meaning that if I put in 5 numbers, it loops 5 times. You may be wondering what exactly do I mean by “hash functions”. Here’s an analogy to help describe the difference between how to look up values in arrays and objects:

Arrays

Looking up a value in an array is like calling a list of unlabeled phone numbers looking for Bob.

Objects

Looking up a value in an object is like having a contact list with Bob’s name in it.

Example Using Arrays


function getListofDuplicatePhoneNumbersIndex(phoneNums)
{
    var dups = [], phoneNums = phoneNums;
    $.each(phoneNums, function (i)
    {
        $.each(phoneNums, function (j) {
            if(j!=i){
                if(phoneNums[i] == phoneNums[j]){
                    dups[j] = j;
                }
            }
        });
    });
    return dups;
}


Example Using Objects


function getListofDuplicatePhoneNumbersIndex(phoneNums)
{
    var seen = {}, dups = {};
    $.each(phoneNums, function(i)
    {
        var phoneNumber = phoneNums[ i ];
        if( seen.hasOwnProperty( phoneNumber ) )
        {
            dups[ i ] = true;
            dups[ seen[ phoneNumber ] ] = true;
        }else
        {
            seen[ phoneNumber ] = i;
        }
    });
    return dups;
}


If you’ve got Firebug installed or any console tool, you can observe how many loops each one takes when you click “Submit” in the Demo linked below

Demo http://wecodesign.com/demos/getDups/