Array.prototype for fun and profit

Was listening to the StackOverflow podcast during a walk the other day. Joel was describing the tests he gives to prospective Fog Creek employees. He mentioned one, which went something along the lines of:

Take an array of numbers, find a number within the array and see if the sum of the numbers before that number and after it are equal.

So I was walking down the street listening and it seemed like an interesting question. After all, I’m always trying to better myself as a mammal. I figured it would be easy to do in Python with some list comprehensions. Then I tried to do it in my head in JavaScript while I was walking, which nagged at me enough so that I sat down to figure it out when I got home.

JavaScript 1.5 doesn’t have a built-in Array function that will pluck an element and return its index (see ECMAscript 1.6 for that), but you can create one with prototypical inheritance:

Array.prototype.has = function(v) {
    for (var i = 0; i < this.length; i++) {
        if (this[i] == v) return i;
    }
    return false;
}

I picked that up on Jonathan Snook’s blog when I was googling about to see if JavaScript had an equivalent function to PHP’s array_search (So yeah, I would have failed the code test since I Googled part of it, but I still learned something.)

Now that I could get the array key of the element in question I could write another function to return the sum of all the numbers in an array:

Array.prototype.sum = function() {
    var sum = 0;
    for (var i = 0; i < this.length; i++) {
        sum = sum + this[i];
    }
    return sum;
}

This is one of the reasons I like JavaScript, you can build-up on the language quickly. I’m already pretty familiar with most of the array functions in JavaScript, so I could use Array.slice() to do some more work for me. I wasn’t sure if the first array should include the plucked number or not, so I just included it. So let’s string it all together:

/**
 * pull element from array and return index
 */ 
Array.prototype.has = function(v) {
    for (var i = 0; i < this.length; i++) {
        if (this[i] == v) return i;
    }
    return false;
}

/**
 * Return sum of numbers in array
 */ 
Array.prototype.sum = function() {
    var sum = 0;
    for (var i = 0; i < this.length; i++) {
        sum = sum + this[i];
    }
    return sum;
}

/**
 * Simple test array
 */
var test = [4 ,3 ,2 ,1 ,0, 6, 0, 1, 2, 3, 4, 6];

var index = test[test.has(6)];                      // return index of 6
var first = test.slice(0, index);                   // grab [4,3,2,1,0,6]
var second = test.slice(index + 1, test.length);    // grab [0,1,2,3,4,6]

if (first.sum() === second.sum())
{
    console.log('the two halves split by ' + index + ' are equal' + first.sum() + ' | ' + second.sum());
}
else
{
    console.log('the two halves split by ' + index + ' are NOT equal: ' + first.sum() + ' | ' + second.sum());
}

I’m also trying to learn about proper Unit Testing, so I reckon over the next day or so I should write a proper test for this.

The more I look at it though I see a few issues. First off is that Array.has() returns the first instance of a found element. There are two 6s in my test array, so I’m only getting the key of the first one and operating from there. How should duplicates be handled?

Comments

Man if I understood this stuff I'm sure I'd be calling you a genius. Since I don't I'm just going to have to go with awesomely awesome beta male.

Dr. Robotnik | posted on Fri, Jan 15th 2010, 00:33