Cracking the Coding Interview – JavaScript Min/Max Binary Heap

I finished my second algorithm from Cracking the Coding Interview – the Binary Heap.

This algorithm racketed up the complexity from the Linked List. The heap’s structure is easy to understand – it’s a binary tree (a tree where each node can have at most two children). In the case of a max heap, the parents have a greater value than their children. So the values in a Max Heap decrease as you move down the tree from the parent to children.

(This image is from Wikipedia)
Max Tree Example

The complexity comes from the behaviour. Though the algorithms are easy to understand, there is enough going on in each one that it’s easy to sneak in bugs. It took me a bit of time to get each of my implementations the way I wanted it.

The insert operation is the easiest to implement. The algorithm is also straight forward.

  1. Add the element to the bottom of the heap.
  2. Compare the added element with its parent; if they are in the correct order, stop.
  3. If not, swap the element with its parent and return to the previous step.

Here is part of my implementation of insert:


binaryHeap.prototype.add = function(data) {
	if (data === undefined) { throw "data must be valid to add"; }

	this.array.push(data);
	this.bubbleUp(this.array.length - 1, data); 
};

binaryHeap.prototype.bubbleUp = function(childIndex, childData) {
	if(childIndex > 0) {
		var parentIndex = this.getParentIndex(childIndex);
		var parentData = this.array[parentIndex]; 

		if (this.shouldSwap(childData, parentData)) { 
			this.array[parentIndex] = childData;
			this.array[childIndex] = parentData;
			this.bubbleUp(parentIndex, childData);
		}
	}
};

binaryHeap.prototype.getParentIndex = function (childIndex) {
	return Math.floor((childIndex - 1) / 2);
};

Delete is a quite bit more complicated, though the algorithm reads about the same.

To delete the top of a heap:

  1. Replace the root of the heap with the last element on the last level.
  2. Compare the new root with its children; if they are in the correct order, stop.
  3. If not, swap the element with one of its children and return to the previous step.
    • Swap with its smaller child in a min-heap and its larger child in a max-heap.

binaryHeap.prototype.removeHead = function() {
	
	var headNode = this.array[0]; 
	var tailNode = this.array.pop();

	this.array[0] = tailNode; 
	this.bubbleDown(0, tailNode);

	return headNode;
};

binaryHeap.prototype.bubbleDown = function(parentIndex, parentData) {
	if(parentIndex < this.array.length) {
		var targetIndex = parentIndex;
		var targetData = parentData;

		var leftChildIndex = this.getLeftChild(parentIndex);
		var rightChildIndex = this.getRightChild(parentIndex);

		if(leftChildIndex < this.array.length) {
			var leftChildData = this.array[leftChildIndex];

			if (this.shouldSwap( leftChildData, targetData )) {
				targetIndex = leftChildIndex;
				targetData = leftChildData;
			}
		}
		
		if(rightChildIndex < this.array.length) {
			var rightChildData = this.array[rightChildIndex];

			if(this.shouldSwap(rightChildData, targetData )) {
				targetIndex = rightChildIndex;
				targetData = rightChildData;
			}
		}

		if(targetIndex !== parentIndex) {
			this.array[parentIndex] = targetData;
			this.array[targetIndex] = parentData;
			this.bubbleDown(targetIndex, parentData);
		} 
	}
};

binaryHeap.prototype.getLeftChild = function (parentIndex) {
	return parentIndex * 2 + 1;
};

binaryHeap.prototype.getRightChild = function (parentIndex){
	return parentIndex * 2 + 2;
};

It’s quite a bit more code to delete the top element and reshuffle the list into the correct order. With all the extra comparisons there are quite a few places that bugs can sneak into the code.

The source code for the project and the tests are here.

Advertisements

Derby.js – Starting out with Components; Creating a Twitter Bootstrap Input Component

In working with Twitter Bootstrap Forms, one of my favorite ways to lay out a form is using the Horizontal form layout. The layout requires a bit of css/html to get each of the form elements (the text boxes and what not) to play nicely.

To add form elements to the horizontal form layout, you need the following html structure for each field:

 
<div class="control-group"><!-- additional classes here to change state -->
  <label class="control-label">INPUT_LABEL_TEXT_HERE</label>
  <div class="controls">
    <input type="text" /> <!-- This is the control you want to display -->
    <span class="help-inline">ERROR_OR_INFORMATIONAL_MESSAGE_HERE</span>
  </div>
</div> 

That’s a hefty amount of markup to copy and paste all over your pristine views. Which makes this a great place to use a Component.

So what’s a Component?

A component is basically a derby template you can supply parameters to. Those parameters are supplied in the form of HTML attributes and HTML content.

There are two types of components: application and library. Application components can only be used in a single project. Library components can be re-used across multiple projects.

For my project I’m going to create an application component. Eventually if I need the component on another project I’ll add it to a component library. But that process is more complicated and less documented so I’ll save that for another day.

There are two ways to create an application component:

  • Inline
  • If your component is only being used on a single view, you can add it to the same file as your view.

  • External
  • If your component is going to be used on multiple views, you should create a separate file for your component.

Apparently there are two ways to create a library component as well:

The ui directory contains a component library, which can be used to create custom components for the containing project. These are re-usable templates, scripts, and styles that can be used to create custom HTML tags for use in applications. General purpose component libraries can be created as separate npm modules.

All components run under the scope of the context in which they are called. Which means you can bind model data to your component without having to pass your component any values.

For example:

<h2>All toys:</h2>
  {each toys as :toy} <!-- Alias :toy available to the component -->
    <app:toyStatus> <!-- All application components live in the app namespace -->
  {/}

<toyStatus:>  <!-- this tag says I am a component -->
  <!-- I'm using alias :toy here, defined above -->
  <span>The toy is located at {:toy.location}</span> 

If all of this “Model-Bindy” stuff is foreign to you, check out my post Working with Views, Models, and Bindings.

I don’t like the way you used a scoped alias from your view in your component. What if my component is in another file? What if I want to use a field with a different name? Is there a better way to pass values to a component?

From the derby documentation:

Literal values or variable values can be passed to components. These component attributes are available through “macro” template tags, which have triple curly braces.

What does that look like? Again, from the docs:

<Body:>
  <h1><app:greeting message="Hello"></h1>

<greeting:>
  I was passed this message as an attribute: {{{message}}}

You can also pass html to your component as well. That is a two-part trick: First, write your component with an opening and closing tag. Put the value you want to pass to your component between the tags.

Then, in your component, you use the special triple-curly bracket {{{content}}} macro-tag to reference what you passed in.

For example:

<Body:> 
  <app:fancyButton>
    <b>Click me now!</b>
  </app:fancyButton>

<fancyButton: nonvoid>
  <button class="fancy">
    {{{content}}}
  </button>

But I already knew all that. How do I make a component?

The easiest way is to just add the component to your page, as show in the simple example above. This example is taken from the derby website, and it shows you how to reference a component in a separate file:

shared.html

(This is your component, which is located in your views folder.)

<profile:>
  <div class="profile">...</div>

home.html

(This is the view that will use your component.)

 <!-- This line imports your component into the view -->
<import: src="shared">

<Body:>
  Welcome to the home page
  <!-- include component from an imported namespace -->
  <app:shared:profile>

The <import> tag at the top, used to include your component into your view, can be called with variety of parameters. For more information on the  <import>  tag go to http://derbyjs.com/#importing_templates.

Didn’t you say something about Twitter Bootstrap?

Oh yeah. Got sidetracked there.

As you can see, creating a component is relatively easy. Since I already have all the Twitter Bootstrap markup ready, I might as well create a Twitter Bootstrap Component for Derby.

To do this, all you have to do is figure out what you want to be able to customize.

boot.html

<input:>
{{{#with data}}} 
  <div class="control-group {{cssClass}}">
    <label class="control-label">{{label}}</label>
    <div class="controls">
      <input type="{{type}}" value="{{value}}" />
      <span class="help-inline">{{message}}</span>
    </div>
  </div> 
{{{/}}}

As you can see, I added bindings for {{cssClass}}, {{label}}, {{type}}, {{value}}, and {{message}}.

Why did I use a #with block to set the scope of my object being passed in? There is a bug in the derby code right now (documented here) where you can’t reference an object’s child properties with the triple curly brackets syntax. So {{{data}}} will work, but {{{data.value}}} won’t.

The object being bound to the component:

var data = function(value, label, type) {
	this.label = label;
	this.value = value;
	this.message = "";
	this.cssClass = "";
	this.type = type || "text";
};

And I call it in my view like this:

<app:boot:input data="{:person.firstName}">

Where firstName is an object like data described above.

So, in a just a little bit of markup and code, I have a great reusable component that I can use to style the look and feel of my application without having to copy and paste code everywhere.

I hope this it helps some of the fledging Derby developers out there.

BTW, code samples from this post can be found here.

Cracking the Coding Interview – JavaScript Singly Linked List

I finished my first algorithm from Cracking the Coding Interview – the almighty Singly Linked List.

This is the low-hanging fruit of the data structures I mean to tackle. However, even implementing this simple structure, I managed to somehow squeeze in a bug that luckily I caught in my testing. An unfortunate case of premature optimization. Oh well, the code doesn’t look as cool as it did, but at least it does the job.

One thing I found in reading a bit about Linked Lists on wikipedia, which I had never heard of before; Hash Linking.

The link fields need not be physically part of the nodes. If the data records are stored in an array and referenced by their indices, the link field may be stored in a separate array with the same indices as the data records.

At first I thought it was a silly way to implement a linked list; if you have an array storing your values, what value are you getting from the list? Once I thought a little more, I realized the value of the link field being stored in a separate array. You can easily re-order your list by changing the values in the array, without traversing and without touching your data. This might be a valuable solution if the relationship between items constantly changes but the size of the data remains somewhat static.

In the notes of various implementations of this pattern I’ve seen, people have commented on how they expand the array when more spots are needed. I have yet to see any information about if you shrink the array once the “list” contracts to a certain point.

The source code for the project and the tests is here.

Derby.js – Integrating Twitter Bootstrap into your Application

As I’ve mentioned in a previous post, I’m a big fan of Twitter Bootstrap.

Lately I’ve been playing been with JavaScript and Derby. I want to integrate bootstrap with the POC site I’m building, and the creators of Derby have already figured out a way to do this.

Step 1: Add a dependency to the derby-ui-boot package, which is a Derby component library based on Twitter Bootstrap.

{ 
....
  "dependencies": {
    "derby": "*",
    "derby-ui-boot": "*",
    "express": "3.0.0beta4",
    "gzippo": ">=0.1.7" 
  },
....
} 

Step 2: Update your project with the downloaded ui-boot code

This is as simple as running
npm update
in your project folder, which will read package.json, and download any missing dependencies (like the derby-ui-boot entry you just added).

Step 3: Add the derby-ui-boot component to your project.

At the top of your application JavaScript (for me, this is the file located at /lib/app/index.js), after your var derby = require("derby"); line, add the following line of code to your file:

var derby = require("derby");
derby.use(require('derby-ui-boot'));

Step 4: Profit!

That should be it for you. When you load your application up, the default twitter bootstrap css and js should have loaded. To correctly style your application, you’ll have to follow the guidelines laid out here and here.

Cracking the Coding Interview: JavaScript Data Structures

A friend and co-worker of mine (one of the best and brightest I’ve worked with) recently left our company to go work for Microsoft. Having gone through the Microsoft interview process myself (hilariously unprepared, to the enjoyment of my interviewer), I wondered what he had done to get ready for the process.

He recommended one book – Cracking the Coding Interview – which he said had been recommended to him as the bible for preparation.

Interested in what his holy grail had to offer, I picked up a copy recently. In the first couple of pages there is a chart that lists a bunch of CS staples (linked lists, trees, hash tables, stacks, queues, etc). After listing these concepts out (which every good programmer should know), it then goes on to say

These are concepts you have to understand and be able to implement.

Now, being a couple of years out of college, I realized that I think I have a handle on these data structures, I haven’t implemented any of them in code in a LONG while. And I’m sure I haven’t implemented all of them. It sounds like a fun little project, and will give me an excuse to freshen up on my data structures.

Since I’ve already done some of these a long time ago in C++, I decided this time around I’d give it a go in JavaScript.

If you want to track my progress, I’ll be putting all of the JavaScript I write here.

Derby.js – Working with Views, Models, and Bindings

In my previous post about derby, I talked a bit about how to create a model in derby and one rule you need to follow when creating models (the first two path segments should be an object).

I’m creating a test application to help me learn derby here. In the process of doing absolutely everything wrong to start I’ve learned a bit about how Derby binds to models.

Let’s say you’re got some markup like this that you’d like to bind to.

 
      <div> 
        <div> <input type="text" id="firstName" /> </div>
        <div> <input type="text" id="lastName" /> </div>
        <div> <input type="tel"  id="phoneNumber" /> </div> 
        <div> <input type="date" id="birthDate" /> </div>
      </div>

Nothing sexy but you get the idea. You can post this information into a view and everything will show up the way you’d expect it to.

If you want to bind this to a model, such as myApp.stuff.newGuy, changing the code is straight forward.

 
      <div> 
        <div> <input type="text" id="firstName"   
                     value="{myApp.stuff.newGuy.firstName}" /> </div>
        <div> <input type="text" id="lastName"   
                     value="{myApp.stuff.newGuy.lastName}" /> </div>
        <div> <input type="tel"  id="phoneNumber"   
                     value="{myApp.stuff.newGuy.phoneNumber}" /> </div> 
        <div> <input type="date" id="birthDate"   
                     value="{myApp.stuff.newGuy.birthDate}" /> </div>
      </div>

Note that you don’t have to write any js code in your /lib/ folder to create this model. The binding [the {} information in the value attribute] will automatically wire up these fields to the myApp.stuff.newGuy model.

If you want to add some default values to these fields you could accomplish this like so:

  
get('/', function(page, model, params) {
  
  //set some default values for my model
  model.set('myApp.stuff.newGuy', { firstName: 'John', lastName: 'Smith' }); 

  //render my template containing the model above
  page.render();
});

When you browsed to the page you would see John in the firstName input and Smith in the lastName input.

How would you render a similar collection of models? There are a couple of ways. To iterate through a collection of objects, you’ll most likely want to use the #each binding.

 
      {#each myApp.stuff.people}
      <div> 
        <div> <input type="text" value="{.firstName}" /> </div>
        <div> <input type="text" value="{.lastName}" /> </div>
        <div> <input type="tel"  value="{.phoneNumber}" /> </div> 
        <div> <input type="date" value="{.birthDate}" /> </div>
      </div>
      {/}

Several things to note here. First, you have to remove the id’s from the html inputs you are binding to. Each input needs to have a unique id. If you omit the id field from the markup, derby will generate a unique id for you. Otherwise you’ll be repeating the same id over and over again (and get strange behaviour as a result).

Second, in an #each binding you don’t use the full path to the model field you want to bind to (e.g. {myApp.stuff.people.firstName}), just the field with a dot prepended. (e.g. {.firstName}).

Note that the dot is very important. If you just put {firstName} as your binding, because of the automatic model creation we noticed above, you will bind to a model called {firstName} for every item in the myApp.stuff.people collection. This will show itself by the very annoying behaviour of every edit being mirrored in every row (since every row is binding to the same model).

Another way to do binding with #each is by using an alias. The documentation of creating an alias:

Aliases to a specific scope may be defined, enabling relative model path references within nested sections. Aliases begin with a colon (:), and can be defined at the end of a section tag with the as keyword.

What would this look like?

 
      {#each myApp.stuff.people as :person}
      <div> 
        <div> <input type="text" value="{:person.firstName}" /> </div>
        <div> <input type="text" value="{:person.lastName}" /> </div>
        <div> <input type="tel"  value="{:person.phoneNumber}" /> </div> 
        <div> <input type="date" value="{:person.birthDate}" /> </div>
      </div>
      {/}

Note that when you declare your alias with your each statement (as :person) you have to keep the colon for your subsequent bindings ({:person.firstName})

HTML5 ‘formaction’ attribute – An easy Modernizr test

EDIT NOTE: This no longer needs to be done outside of Modernizr. This was added to the Modernizr package about a month ago.
Link to issue

I’ve been writing some Html Forms, and in playing with submit buttons came across an interesting attribute in the HTML 5 specs: formaction.

The definition, from HTML Living Standard Doc

The action and formaction content attributes, if specified, must have a value that is a valid non-empty URL potentially surrounded by spaces.

The action of an element is the value of the element’s formaction attribute, if the element is a submit button and has such an attribute, or the value of its form owner’s action attribute, if it has one, or else the empty string.

What does that mean? It means you can have a form on your page, and supply the formaction attribute to various buttons, and each button will post the same form to a different URL!

Pretty neat, and has global acceptance in all browsers but one; Internet Explorer. Whoops.

I really want to use this functionality, so I’ll come up with a shim to replace the functionality that IE is missing. For now, the only part of this problem I’ve solved is how to detect whether or not your browser supports this feature, via Modernizr

// input[formaction] attribute
// When used on an <input type='submit'>, 
// this attribute signifies that the form containing 
// the input should post to the URL contained in the attribute 
// rather than the URL defined in the form's 'action' attribute. 
// By Matt Blair - 

Modernizr.addTest('inputformaction', 'formAction' in document.createElement('input'));