webdev | Entries tagged with javascript

jQuery does a great job of providing a normalized event model across all browsers. It’s my go-to library for that particular task, plus it has several other useful features. One of the great features jQuery has for its event system is namespacing. You can namespace your event types as you attach, detach, and call them. For example:

// Attach a simple event handler to the element
$(“#targetEl”).on(“click”, function(event) {
  console.log(‘A click event happened!’);
});

// Now attach a namespaced event handler to the element
$(‘#targetEl’).on(‘click.plugin’, function(event) {
  console.log(‘A click.plugin event happened!’);
});

Now, when you click on the target element, both event handlers will fire. If you manually trigger a click event you can add the namespace to it:

$(‘#targetEl’).trigger(‘click.plugin’);

This will trigger only the click.plugin event handler. This gives you an easy way of segregating your event handlers, and is particularly useful with custom events.

Event namespacing is a great feature, and I decided to think about how I might implement it from scratch, just as an exercise. The reason jQuery has namespaced events is because it has its own event handling system, so I started to think about what it would take to write a simple event manager that would provide a namespacing feature.

So here’s a first stab at a general event manager. The goal here isn’t to produce production-quality code, but rather to explore the desired features and get some code up that implements them, and if we like the direction we can later create something that’s more structured.

( Long post is best post! Click to continue... )

One of my favorite little-known features of the DOM is the EventListener interface. We all know how to attach an event listener to a DOM element using Element.addEventListener method, which takes three parameters:

eventType: a string that indicates the type of event

handler: a function to execute when the event happens

bubble: whether or not to execute the function during the bubble phase

What’s little known is that the DOM specifies you can use any object as the handler, as long as it implements the EventListener interface. According to the DOM Level 2 standard:

The EventListener interface is the primary method for handling events. Users implement the EventListener interface and register their listener on an EventTarget using the AddEventListener method. The users should also remove their EventListener from its EventTarget after they have completed using the listener.

An EventListener interface is simply a method on the object called handleEvent. Thus, the two event handlers can be used interchangeably:

function handleClickFunction(event) {
  alert(‘The element was clicked!’);
}

var handleClickObject = {
  handleEvent: function(event) {
    alert(‘The element was clicked!’);
  }
}

You register an event handler object using Element.addEventListener just like a function:

var myElement = document.getElementById(“targetElement”);
myElement.addEventListener(“click”, handleClickObject, true);

When a click event happens on the target element, handleClickObject.handleEvent will be invoked. Within that method, the this keyword will be a reference to handleClickObject, just like you’d expect.

One of the great things about this is it makes it easy to build a single object containing several event handlers, and then use the EventListener interface to delegate to the appropriate type. For example:

// Create an EventManager “class” that we can use as a base from which
// to instantiate event managers for elements as needed.
var EventManager = {
  handleEvent: function(event) {
    if (this[event.type] != null) {
      this[event.type].call(this, event);
    } else {
      console.log('no event handler for event of type ' + event.type);
    }
  }
};

// Create an event manager object from our base class, adding in
// methods for click and mousedown (but not mouseup)
var testElEventManager = Object.create(EventManager, {
  click: {
    value: function(event) {
      console.log('click event happened');
    }
  },
  mousedown: {
    value: function(event) {
      console.log('mousedown event happened');
    }
  }
});

// Bind the new event manager to testEl for the events click, 
// mousedown, and mouseup.
testEl.addEventListener('click', testElEventManager);
testEl.addEventListener('mousedown', testElEventManager);
testEl.addEventListener('mouseup', testElEventManager

In this example I’ve created a base object which implements the EventListener interface. All it does is check to see if a method exists on the object for a given event type, and if it does it calls it, and if it doesn’t it provides an error.

Then I create a new event manager from that base object using Object.create(). You could just as easily have created a constructor function; I prefer this technique because it allows me to add new methods as part of the creation step. In this example, I’m adding methods for click and mousedown events.

Then I bind the new event manager object to my test element for the three events click, mousedown, and mouseup.

When you click on the element, the mousedown-mouseup-click event sequence will fire, and the following output will result on the console:

mousedown event happened
no event handler for event of type mouseup
click event happened

This illustrates using a single object to handle multiple event types--pretty nifty.

Coming up: Using this method to create a single Event Manager object that serves as a one-stop shop for everything event-related: registration, delegation, etc. We can even include some nifty extra features like namespacing.

Continuing with the series of JavaScript interview questions, here's the next one: given a singly-linked list, delete every entry that has a given value.

This is a great interview question because it tests out the applicant's knowledge of linked lists, which is one of the most basic of data structures. JavaScript of course has no implementation of linked lists, so solving this problem will basically mean implementing a linked list from scratch.

A singly linked list basically is a list of entries, where each entry has a value and a pointer to the next entry. In JavaScript, this is super easy to imagine:

var linkedList = {
    value: 1,
    next: null
}

linkedList.next = {
    value: 2,
    next: null;
}

linkedList.next.next = {
    value: 3,
    next: null;
}

Or, to put it in literal notation:

var linkedList = {
    value: 1,
    next: {
        value: 2,
        next: {
            value: 3,
            next: null
        }
    }
}

Each node has a value and a pointer to the next node. In the last node, the next node is null. Very simple.

Based on this, let's create a simple implementation of a singly linked list in JavaScript. In our case, we will want the class to have the following properties:

A public length property, to show how many elements are in the list

A public pointer to the first element, called firstNode

A public pointer to the last element, called lastNode

and the following methods:

getSize, which will return the length of the list

addNode, which will add a node with the specified value to the end of the list

toString, which will present a delimted list of all values. Default delimiter will be a comma, but can be specified as a parameter

removeNode, which will remove all nodes with a specified value from the list and return true if any were found and deleted, or false if not. (This is where most of the work for answering the question will go.)

function SinglyLinkedList() {
    this.firstNode = null;
    this.lastNode = null;
    this.size = 0;

    // Get the size of the list, super-simple: just return this.size
    this.getSize = function() {
        return this.size;
    }

    // Add a node to the list
    this.addNode = function(newVal) {

        // First, create the node
        var newNode = {
            data: newVal,
            next: null
        }

        // If there are no other nodes, then this is the first node
        if (this.firstNode == null) {
            this.firstNode = newNode;
            this.lastNode = newNode;
        } else {
            // Not the first node, so tack it on to the end of the list
            this.lastNode.next = newNode;
            this.lastNode = newNode;
        }

        // Increment size
        this.size++;
    }
    
    // toString method: create a comma-delimited list of values
    this.toString = function(strDelimiter) {
        var currentNode = this.firstNode,
            i = 0,
            strResult = "{";

        // Provide a default delimiter if none was specified.
        if (typeof(strDelimiter) === "undefined") {
            strDelimiter = ","
        }

        // Loop through the list and concatenate all values
        for( i = 0; currentNode != null; i++) {
            if(i > 0) {
                strResult += strDelimiter;
            }
            var dataObject = currentNode.data;

            strResult += (dataObject == null ? "" : dataObject);
            currentNode = currentNode.next;
        }
        strResult += "}";

        return strResult;
    }

    // Remove a node from the list with a given data value
    // Returns true if the value was successfully found and deleted, false if not.
    this.removeNode = function(targetVal) {
        // Are there even any nodes?
        if (this.size === 0) {
            return false;
        }

        // Traverse the list and look for targetVal.
        var currentNode = this.firstNode,
            previousNode = null,
            wasDeleted = false;

        // Check for the edge cases around deleting the first node in the list
        if (targetVal === currentNode.data) {
            
            // One possible edge case is that this is the only node in the list,
            // in which case we just need to reset the list and return.
            if (currentNode.next == null) {
                this.firstNode.data = null;
                this.firstNode = null;
                this.lastNode = null;
                this.size = 0;
                return true;
            }

            // The other possible edge case is that we are deleting the first node
            // in the list, but there are still other nodes to search.
            currentNode.data = null;
            currentNode = currentNode.next;
            this.firstNode = currentNode;
            this.size--;
            wasDeleted = true;
        }

        // Loop through all the remaining nodes and look for values to delete
        currentNode = this.firstNode;
        while (true) {
            if (currentNode == null) {
                // We're done.  Break out of the loop.
                break;
            } else {
                if (targetVal === currentNode.data) {
                    // Found one!
                    // To get rid of this node, just get the next one and
                    // set currentNode to it.
                    var nextNode = currentNode.next;
                    if (nextNode != null) {
                        currentNode.data = nextNode.data;
                        currentNode.next = nextNode.next;
                    } else {
                        // Edge case: Deleting last entry in list.
                        currentNode.data = null;
                        if (previousNode != null) {
                            previousNode.next = null;
                        } else {
                            // Edge case: turns out this was a linked list with multiple entries of targetValue,
                            // and we just deleted the last one.
                            // Reset the list and return.
                            this.firstNode = null;
                            this.lastNode = null;
                            this.size = 0;
                            return true;
                        }
                        this.lastNode = currentNode;
                    }
                    wasDeleted = true;
                    this.size--;
                } else {
                    // Move on to the next node.
                    previousNode = currentNode;
                    currentNode = currentNode.next;
                }
            }
       }
       // Looping all done.  Return result.
       return wasDeleted;
    }
}

Now all you have to do is create a new linked list using that constructor:

var llNumbers = new SinglyLinkedList();
llNumbers.addNode(5);
llNumbers.addNode(5);
console.log(llNumbers.toString()); // Will output {5,5} to console
console.log(llNumbers.removeNode(5)); // Will output true to console
console.log(llNumbers.removeNode(5)); // Will output false to console
console.log(llNumbers.toString()); // Will output {} to console
llNumbers.addNode(1);
llNumbers.addNode(2);
llNumbers.addNode(3);
llNumbers.addNode(4);
console.log(llNumbers.toString()); // Will output {1,2,3,4} to console
console.log(llNumbers.removeNode(4)); // Will output true to console
console.log(llNumbers.removeNode(4)); // Will output false to console
console.log(llNumbers.toString()); // Will output {1,2,3} to console

And there you have it.

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.

It doesn’t. JavaScript arrays on numeric indices only. You can push anything you want into an array, including objects, which is nice.

JavaScript arrays are also objects, so they can have properties like objects. And JavaScript has overloaded its square bracket notation so that square brackets not only refer to array members, but also to properties on objects. Thus:

var myObj = {}; 
myObj.newProp = 4;
console.log(myObj[newProp]); // will output a reference error because newProp (no quotes) is undefined
console.log(myObj[‘newProp’]); // will output 4 on the console.

That’s covered in the ECMA standard, section 11.2.1:

11.2.1 Property Accessors
Properties are accessed by name, using either the dot notation:
MemberExpression . IdentifierName
CallExpression . IdentifierName
or the bracket notation:
MemberExpression [ Expression ]
CallExpression [ Expression ]

You can add all of the properties you want to arrays (I do it all the time) but a property on an array is not a member of that array. That means a property has no index in the array, and cannot be searched for using methods like indexOf. Thus:

var myObj = {};
var myArray = [‘apples’, ‘oranges’, ‘lemons’, ‘pluots’];
console.log(myArray.length); // will output 4 on the console.
myArray.newProp = myObj;  // newProp is now a property on myArray.
console.log(myArray.newProp === myArray[‘newProp’]); // will output true.
console.log(myArray.length); // will output 4 on the console.
console.log(myArray.indexOf(‘newProp’)); // will output -1, because newProp is not a member of the array, it is a property.

Out of the box, JavaScript has no implementation of the classical OO concept of "classes." In my experience, this is one of the biggest stumbling blocks for people coming to the language from classical OO languages like C++ or Java. Prototypal inheritance is also something of a challenge, though generally it's so well-hidden you won't be encountering it unless you go digging. Despite these barriers, JavaScript classless existence gives it a dynamic nature that classic OO languages just don't have.

So if there are no classes, how do you create objects and templates for objects in JavaScript? There are actually three methods.

Constructor Functions

In JavaScript, you can create a constructor function that applies properties and methods and initialization routines to an empty object and then returns it. JavaScript has a special built-in functionality for this using the new keyword: when you invoke a function with the new keyword, JavaScript will create a new empty object and then invoke the function with the empty object as the invocation context (in other words, within the function the this keyword will refer to the new object). JavaScript will automatically return the modified context when the function is done executing, or you can do it yourself by explicitly returning this when you're done. Here's a simple example:

function constructorFunction() {
  this.myNumber = 10;
  this.myMethod = function() {
    console.log('Method was called');
  }
  return this;
}

var myNewObject = new constructorFunction();
console.log(myNewObject.myNumber); // will output 10 to console.
myNewObject.myMethod(); // will output 'Method was called' to console.

Constructor functions have the benefit of having a great deal of flexibility. You can create very complex objects and have all of the creation and initialization code nicely encapsulated within the constructor.

On the other hand, my experience has shown me that constructor functions tend to confuse new JavaScript programmers, especially those with experience with classic class-oriented languages. I think it's because the new keyword makes it look like you're instantiating a member of a class, but you're not. The mechanisms are completely different, even though the result is a new object.

Object Literals

You can simply define a new object using literal notation. I use this method most often when creating singletons.

var mySingleton = {
  intProp: 10,
  strProp: "hello world",
  myMethod: function() {
    console.log(this.strProp);
  }
};
mySingleton.myMethod(); // will output "hello world" to the console.

Literals are a fast, down-and-dirty way of creating one-off objects. The disadvantage is that it's kind of hard to do extensive initialization, unless you specify a method as part of your literal that you can then invoke. Encapsulation is also a challenge.

Object.create()

By far my favorite way to create new objects is to use the create method on the global Object object. Object.create takes two parameters:

prototypeObject: An existing object that will serve as the prototype for the new object.
propertiesObject: An optional map of properties along with their descriptors, to be copied onto the new object. (See JavaScript Property Descriptors for an in-depth explanation.)

When you invoke Object.create it creates a new object, sets its prototype to prototypeObject and then copies the properties from propertiesObject (if it was provided) onto the new object, and then returns the new object.

This method basically allows you to use any object as a template for a new object. In my opinion, this really helps clarify JavaScript's prototypal inheritance, so I generally prefer this method.

We're all familiar with properties on objects. In JavaScript, an object with its properties can be defined in several different ways. Using literal notation, for example:

var myObject = {
  myProperty: "hello world"
}
console.log(myObject.myProperty); // will output "hello world" to the console.

With the advent of ECMAScript 5, every property has a set of descriptors defined upon it. These descriptors specify how (or whether) the property is accessed. You can, for example, specify whether or not a property should be enumerable in a for-in loop, or whether or not a property can be changed later on.

ECMAScript 5 specifies a new set of methods on the global Object object for accessing property descriptors. To set a descriptor on an object's properties, you have to use the new Object.defineProperty method, which takes the following parameters:

targetObject: The object that is being modified
strPropName: The name of the property being created or modified
objDescriptors: An object that provides a map of descriptors in the form of key/value pairs

Valid descriptors for a simple property are:

configurable: when set to false, you cannot change the property's value or any of its descriptors. Defaults to true.
enumerable: when set to true (the default) the property will be included as a property on a for-in loop executed on the object.
writable: when set to false, you cannot change the property's value. Defaults to true.
value: the actual value of the property.

So in our example above, we would do the following:

var myObject = {};
Object.defineProperty(myObject, "myProperty", {
  value: "hello world",
  enumerable: true,
  writable: true,
  configurable: true
});
console.log(myObject.myProperty); // will output "hello world" to the console.

Of course those are the default values for those descriptors, so you don't need to define them explicitly. I'm showing them here to illustrate the use of the new method.

In addition, ECMAScript 5 specifies a new kind of property called an Accessor. Accessor properties cannot have value or writable descriptors and instead have get and set descriptors which are functions that are invoked when the property is accessed.

var myObject = {
  _myProperty = ''
};
Object.defineProperty(myObject, "myProperty", {
  get: function() {
    console.log('myObject.myProperty was accessed');
    return this._myProperty;
  },
  set: function(value) {
    console.log('myObject.myProperty was changed');
    this._myProperty = value;
  },
  enumerable: true,
  configurable: true
});
var testVar = myObject.myProperty; // will output "myObject.myProperty was accessed" to the console.
myObject.myProperty = true; // will output "myObject.myProperty was changed" to the console.

Accessor properties are super-powerful and I'll have to write another blog post about them sometime--you can use them to create data binding!

You can also set the descriptors on properties added when you use Object.create, which (just like Object.defineProperty) also takes an optional descriptor map:

var templateObject = {
  templateProperty: "hello from the template",
  templateMethod: function() {
    console.log(this.templateProperty);
  }
}

var myNewObject = Object.create(templateObject, {

  // Notation convention: A property prefixed with _ is "private."
  _myVal: {
    enumerable: false,
    value: null
  },
  // Define getter and setter and use the "private" property to store the value.
  myVal: {
    get: function() {
      return this._myVal;
    },
    set: function(newVal) {
      if (newVal !== this._myVal) {
        this._myVal = newVal;
      }
    },
    enumerable: true
  },

  // Here's how to create a method.
  newMethod: {
    value: function() {
      console.log('Hello from the new properties.');
    },
    enumerable: false
  }
});

myNewObject.newMethod(); // will output 'Hello from the new properties.' to the console.
myNewObject.templateMethod(); // will output 'hello from the template' to the console.
myNewObject.myVal = 5; // Will use set() method.
console.log(myNewObject.myVal); // will use get() method to output 5 to console.

Finally, to access the descriptors on an existing property, you can use the Object.getOwnPropertyDescriptor method, which takes two parameters:

targetObject: The target object with the property whose descriptors you want to view
strPropName: The name of the property whose descriptors you want to view.

The method returns a descriptor map object, just like the ones defined in the above examples.

No, not dead, just buried under the mountain that is Google. The first few months at Google are pretty intense, and I've been having a blast. We're still working on Ninja, stay tuned for more awesomeness there. Overall I think I'm digging myself out from under the pile, and should be posting here more and re-engaging on Twitter.

In the meantime, I've been finishing up a new project: The JavaScript Programmer's Reference, which will be published by Apress. I just finished up the first draft of the last chapter last night. This project came out of nowhere for me, I was brought in to co-author on the project that was floundering, so I dove in head first and really worked hard to get things on track. It's been an awesome experience for me, though I wish I'd been able to do it faster (see above, Re: new job at Google). And I hope people will find it useful. As soon as we get the Table of Contents set up I'll do a post about it explaining more about the content and our take on the language and how we built the reference.

Unfortunately, both the new job and the new book have delayed my work on updating jQuery Mobile. I apologize for that, and I do intend to move forward with that update. The jQuery Mobile team has been doing awesome work, and they've really brought some great new features to the framework, and the old book just doesn't cut it. Once we've finished the editorial process on the other book, I'll get right back on updating jQuery Mobile.

It's been a busy winter for me, but totally worth it. The new book has only served to increase my appreciation of JavaScript. There are aspects of the language that I never get to use in my daily work, simply because they're not called for, and so it's been really an amazing thing to revisit them as I've been writing about them.

Continuing the series on JavaScript Interview Questions, here's the next one: given an array of positive and negative integers, find the largest continuous sum.

This is pretty simple to do in JavaScript and uses the same algorithm that Arden describes in his original post:

function optimalSolution(arrIntegers) {
    var maxSum = 0,
        currentSum = 0,
        i = 0,
        arrIntegersLength = arrIntegers.length;
    
    if (arrIntegersLength === 0) {
        return;
    }
    
    for (i = 0; i < arrIntegersLength; i++) {
        currentSum = Math.max((currentSum+arrIntegers[i]), arrIntegers[i]);
        maxSum = Math.max(currentSum, maxSum);
    }
    return maxSum
}

Here I have optimized the loop but otherwise it's almost exactly the same as Arden's solution in Python.

Continuing through the interview questions, here's another very common one: Given a matrix of integers and coordinates of a rectangular region within the matrix, find the sum of numbers inside the rectangle.

My usual way of visualizing two-dimensional matrices is as an array of arrays, thus:

var M = [];
M.push([70, 37, 23, 57, 27, 22, 90, 99, 22, 59]);
M.push([47, 63, 33,  1, 42, 46,  6, 70, 98, 93]);
M.push([36, 62, 50, 21, 92, 27, 60, 29, 15, 34]);
M.push([70, 37, 23, 57, 27, 22, 90, 99, 22, 59]);
M.push([47, 63, 33,  1, 42, 46,  6, 70, 98, 93]);
M.push([36, 62, 50, 21, 92, 27, 60, 29, 15, 34]);
M.push([70, 37, 23, 57, 27, 22, 90, 99, 22, 59]);
M.push([47, 63, 33,  1, 42, 46,  6, 70, 98, 93]);
M.push([36, 62, 50, 21, 92, 27, 60, 29, 15, 34]);
M.push([70, 37, 23, 57, 27, 22, 90, 99, 22, 59]);

Here I am taking obvious advantage of copy-and-paste! This results in a two-dimensional array (so M[9][9] = 59) but it's easier to visualize the iterations as dealing with subarrays. So the brute force solution involves adding up the subarrays from given starting points to given ending points:

function arrSum(fromRow, toRow, fromCol, toCol) {
    var totSum = 0;
    for (i = fromRow; i <= toRow; i ++) {
      var currArrSeg = M[i],
          rowSum = 0;

      for (j = fromCol; j <= toCol; j++) {
        rowSum += currArrSeg[j];
      }
      totSum += rowSum;
    }
    return totSum;
}

Arden mentions that the complexity of this solution is O(MN). That's about as good as it gets for a one-shot method. If, however, we assume that our method will be called multiple times, then this problem becomes one that can benefit from caching.

Arden discusses the caching algorithm in his original post so I won't repeat that here. In our case we'll use an object as a cache that we'll need to initialize on the first pass and use from that point on. We'll also use our arrSum method to do the initial caching, since we already have it built:

var cache = new Object();
cache.boolInitialized = false;

function optimalSolution(fromRow, toRow, fromCol, toCol) {
    if (!cache.boolInitialized) {
        var maxRow = 10,
            maxCol = 10,
            i = 0,
            j = 0;
            cache.boolInitialized = true;

        for (i = 0; i < maxRow; i++) {
            for (j = 0; j < maxCol; j++) {
                var cachePtr = i + "," + j;
                cache[cachePtr] = arrSum(0, i, 0, j);
            }
        }
    }

    var returnVal = 0,
        toRowToCol = (typeof(toRowToCol) === "undefined") ? cache[toRow + "," + toCol] : 0,
        fromRowToCol = (typeof(fromRowToCol) === "undefined") ? cache[(fromRow-1) + "," + toCol] : 0,
        toRowFromCol = (typeof(toRowFromCol) === "undefined") ? cache[toRow + "," + (fromCol-1)] : 0,
        fromRowFromCol = (typeof(fromRowFromCol) === "undefined") ? cache[(fromRow-1) + "," + (fromCol-1)] : 0;

    returnVal = toRowToCol - fromRowToCol - toRowFromCol + fromRowFromCol;
    return returnVal;
}

Now the first time we call our optimal solution it will fill the cache, and from that point it will use the cache rather than recalculating anything. So the complexity of the initial call is O(MN) but subsequent calls are O(1), which is a significant saving.

I'm using a simple object as the cache; the key is the toRow,toCol string and the value is the sum of the region. To account for occasionally looking for something in the cache that isn't there (imagine looking in the cache for the sum of 0,0 to 2,2, for example), we check for undefined values and substitute 0 for them.

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.

Over on his blog Arden Dertat has an excellent series of articles about common interview questions and their solutions. He discusses multiple solutions for almost every problem and talks about their complexities and other advantages and disadvantages. They're a really excellent series of articles and I highly recommend them.

Arden has done many of the solutions in Python or C. I decided it would be helpful to review the questions and present solutions in JavaScript, especially where JavaScript provides its own solutions that Python or C do not. After all, web application development often employs many of the techniques these questions illustrate: string and array manipulation, basic data structures, algorithms and optimization. I won't repeat Arden's excellent discussions of the details (I doubt I could do better), but I will be adding my own observations. I'll also be posting my code on Github as I go.

If anyone has worked through these examples in another language--even if it's just a repo on Github--let me know!

Question 1: Array Pair Sum. Given an array of random integers, output the pairs that add to a given number k.

Question 2: Matrix Region Sum. Given a matrix of integers and coordinates of a rectangular region within the matrix, find the sum of numbers inside the rectangle.

Question 3: Largest Continuous Sum of an Array. Given an array of positive and negative integers, find the largest continuous sum.

Profile

Jon Reid

October 2013

S	M	T	W	T	F	S
		1	2	3	4	5
6	7	8	9	10	11	12
13	14	15	16	17	18	19
20	21	22	23	24	25	26
27	28	29	30	31

Please State the Nature of the Technical Emergency: An Autobiography

Entries tagged with javascript

An Event Manager

The Event Listener Interface

JavaScript Interview Question #5: Remove Node from Linked List

JavaScript Interview Question 4: Find the missing element

JavaScript Does Not Have Associative Arrays

Creating JavaScript Objects

JavaScript Property Descriptors

Is that a sort of...updatey-thing?

JavaScript Interview Question 3: Largest Continuous Sum of an Array

JavaScript Interview Question 2: Matrix Region Sum

JavaScript Interview Question 1: Array Pair Sum

JavaScript Interview Questions

Profile

October 2013

Links

Syndicate