Cracking the Coding Interview – The Tower of Hanoi and Poor Editing

I just finished the Stack section of Cracking the Coding Interview and came across an old puzzle – The Tower of Hanoi.

I struggled with solving this problem. I wrote this elaborate, strange algorithm to try to solve it (which should have been a dead give-away that I had it wrong). Ironically enough, hidden in the 20-30 lines of code I wrote were the three lines of code I needed to solve the problem.

Anyways, after beating my head in trying to solve this, I ended up going to the back of the book and looking up the solution.

And found this pile of shit psuedocode. I’ve shortened the comments, but the content is the same.

moveDisks(int n, Tower origin, Tower destination, Tower buffer) {

   if (n <= 0) return;

   //Move top n - 1 disks from 1 to 2
   moveDisks(n-1, tower 1, tower 2, tower 3);

   //Move top from 1 to 3
   moveTop(tower 1, tower 3);

   //Move top n - 1 disks from 2 to 3
   moveDisks(n-1, tower 2, tower 3, tower 1);
}

In this tiny amount of code, in over five revisions to her book, the author has managed to miss two errors.

  1. In the first line, Variables origin, destination, and buffer are declared, but then tower 1, tower 2, and tower 3 are used. Which is which?
  2. In line 5, the comment says “Move top n-1 disks”. Then, in lines 8-9, the author indicates that you move the top. Since you’ve already moved all the items in the stack but one, the bottom element, that line should read “move bottom”.

Maybe these aren’t huge issues, but since I was pretty frustrated with this problem, having to correct the solution didn’t help my frustration.

The correct code:

moveDisks(int n, Tower origin, Tower destination, Tower buffer) {

   if (n <= 0) return;

   //Move top n - 1 disks from origin to buffer
   moveDisks(n-1, origin, buffer, destination);

   //Move nth disk (the bottom disk) from origin to destination
   moveBottom(origin , destination);

   //Move top n - 1 disks from buffer to destination
   moveDisks(n-1, buffer, destination, origin);
}

I hope this helps somebody else who’s working on this problem.

Cracking the Coding Interview – Linked Lists – The Runner Technique

I’ve been going over the Linked List section of Cracking the Coding Interview and I’m realizing that almost every time I get stumped with a problem the solution is the Runner Technique (or slow/fast pointers).

The idea behind the runner technique is simple; use two pointers that either move at different speeds or are a set distance apart and iterate through a list.

Why is this so useful? In many linked list problems you need to know the position of a certain element or the overall length of the list. Given that you don’t always have the length of the list you are working on, the runner technique is an elegant way to solve these type of problems (and in some cases it’s the only solution). Here are some examples of linked list problems where the runner technique provides an optimal solution:

Where do you use it? If you get handed a linked list question, and you find yourself asking these questions:

  • How do I figure out where these two things meet?
  • How do I figure out the midpoint?
  • How do I figure out the length?

You’re most likely dealing with a problem where you need to use the runner technique.

How does it work? I’ll illustrate one of the examples above.

Given two lists of different lengths that merge at a point, determine the merge pointTerrible Branched Linked List Picture

  1. Start a node at the beginning of each list on the left.
  2. Count how many nodes each pointer encounters. (The top list should be 5, the bottom list 4.)
  3. The difference between the two numbers is the difference in length of the two lists before the merge point (the difference is 1)
  4. Move your nodes to the beginning of each list, but the longer list should get a headstart equal to the amount of difference. (so the top list would start on its 2nd element, while the bottom list would start on its 1st).
  5. Move each node forward at the same speed until they meet. Where they meet is the collision point.

Each of the links above contains code and solutions to each of the problems. I hope this example and the ones above show the usefulness of this approach.

There are also some examples located here of various linked list algorithms problems and solutions written in JavaScript.

Link

Sublime Text has rapidly become my favorite text editor. Cross platform, easy to use, great feature set. The Command Palette feature, where you can search for a feature without having to know where it is in the application, is an piece of usability brilliance.

Somebody cobbled together a great step-by-step set of directions on how to install sublime on ubuntu. I wanted to give a shout-out to them and their work.

How to install Sublime Text 2 on Ubuntu 12.04 (Unity) | Technoreply.

Setting up MongoDB to work with Derby.js

This post is going to cover installing and configuring MongoDB to use with Derby.

If you’re reading this post looking to add model persistence to your Derby application but don’t know much about MongoDB, understanding MongoDB will help you understand Derby and the model system it uses.

What’s MongoDB?

From their website:

MongoDB (from “humongous”) is a scalable, high-performance, open source NoSQL database.

If you’ve never used MongoDB before, you should immediately go here. This is the easiest, fastest way to learn the basics of what mongo is and how it works. And it only takes about fifteen minutes. It’s even interactive to keep you from getting bored. Go give it a play.

Derby and MongoDB

Now that you have an idea about how MongoDB works, many of the conventions Derby uses for models should make sense. If you scan through the Derby Query Readme now, hopefully is makes a bit more sense (like where the term “gte” came from).

Installing MongoDB

If you still need to install MongoDB go here for downloads and installation directions.

Configuring Derby to use MongoDB

Now that you know about MongoDB, let’s get MongoDB set up to work with Derby. This is straightforward and takes about two minutes.

To add MongoDB to your Derby application, you’ll need to include the racer-db-mongo package in your project.

Update your package.json file to look something like this:

{
  "name": "potluck",
  "description": "",
  "version": "0.0.1",
  "main": "./server.js",
  "dependencies": {
    "derby": "*",
    "derby-ui-boot": "*",
    "express": "3.0.0beta4",
    "gzippo": ">=0.1.7",
    "racer-db-mongo": "*" //this is the line. Glory in its beauty.
  },
  "private": true
}

Then, at the command prompt, update your project (and download the recently added racer-db-mongo dependency) using the following command:

 npm update 

You’ll have to update your server configuration (by default in /lib/server/index.js) to use the new dependency. This requires TWO new lines of code

derby.use(require('racer-db-mongo')); // This line is new

app.createStore({
  listen:  server
, db:      {type: 'Mongo', uri: 'mongodb://localhost/database'} /* This line is new */
});

That’s all the changes you need to make to add MongoDB to your project. So why I’d bother with a blog post?

What About Troubleshooting?

Now, if you go and start your Derby application, you might see the following error:

Error: failed to connect to [localhost:27017]

Which means:

  1. You’ve installed the racer-db-mongo dependency correctly!
  2. You now need to:
    • Install MongoDB
    • Turn on MongoDB
    • OR Fix MongoDB

If you’ve forgotten to install Mongo, if you look around, you’ll probably find a link somewhere which will help you out.

Starting/Stopping/Statusing MongoDB

If you’ve installed Mongo, you have to start the service before Derby can use it. On Ubuntu, you start Mongo using the following command:

 sudo start mongodb 

Remember to stop Mongo later with:

 sudo stop mongodb 

If you’ve started Mongo, then loaded your Derby application, and you’re still getting an error, it’s possible that Mongo did not start correctly. Typing:

 sudo status mongodb 

will let you know if Mongo is running or not. If you’ve run the Mongo Start command, yet the status command is telling you that Mongo is stopped, the most likely cause is Mongo did not shut down gracefully last time it was run. You’ll have to go and repair your installation (luckily, this is pretty easy).

Repairing MongoDB

To repair your installation, run the following commands:

$ sudo rm /var/lib/mongodb/mongod.lock
$ sudo -u mongodb mongod -f /etc/mongodb.conf --repair 

The code above was taken from this great article

At this point, you should have a working copy on MongoDB along with a working integration with Derby. Congrats!

MongoDB is working great – now Derby hates me

If your application loads, but you’re getting a strange error whenever you add to a collection that looks something like this:

Error: No persistence handler for 
push(FIRST_WORD.SECOND_WORD, [object Object], 18) 

It means that you are pushing to the wrong portion on an model path. You can only use push to arrays, and arrays are not objects, and you can only use objects for the first and second words of your model path. In the case shown above, a push is attempting to be made to

 FIRST_WORD.SECOND_WORD 

which equates to

 FIRST_WORD.SECOND_WORD.push(object) 

which means SECOND_WORD is an array (which isn’t allowed).

If this last bit of explanation might have well been in Latin, check out this post. It’ll explain a little bit about how to declare models and what Derby is expecting you to do.

Unfortunately, you CAN use the second word of a model path as an array without persistence support. So this kind of bug will only surface once you’ve got MongoDB integrated with Derby.

Javascript Strings – Using Array Accessor ‘[]’ to set characters

I’ve been learning quite a bit about JavaScript in writing algorithms from Cracking the Coding Interview.

I learned something new about strings in JavaScript and how they can be accessed.

From MDN:

Character access

There are two ways to access an individual character in a string. The first is the charAt method:

return 'cat'.charAt(1); // returns "a"

The other way is to treat the string as an array-like object, where individual characters correspond to a numerical index:

return 'cat'[1]; // returns "a"

Array-like character access (the second way above) is not part of ECMAScript 3. It is a JavaScript and ECMAScript 5 feature.

For character access using bracket notation, attempting to delete or assign a value to these properties will not succeed. The properties involved are neither writable nor configurable.

I highlighted the important part. I know that strings are immutable in JavaScript, but why give me array access if you won’t let me use it?

So if you want to use the array accessor with a string, there is a way to do it, but it requires a bit of overhead.

var sentence = "this is a proper JavaScript string.";
sentence = sentence.split(""); //split into array
sentence[18] = 'j';  //changing values to lowercase
sentence[22] = 's';
sentence = sentence.join(""); //make the array a string again

Cracking the Coding Interview – JavaScript Trie

I finished my third algorithm from Cracking the Coding Interview – the Trie.

Tries are an extremely useful algorithm, if not all that well known. They can be used for very efficient spell checking, auto suggestion, as well as the sorting of a collection of strings.

This algorithm was more complex to implement than the Linked List, but a little simpler than the Max/Min Binary Heap to implement. The trie’s structure is easy to understand – it’s a word tree, where each leaf of the tree is a letter of a word. Where words share common prefixes (such as fresh and freedom), those words share a common “branch” of prefix letters, and split where the words differ.

(This image is from Wikipedia)
Trie Tree Example

The insert and hasWord operations are easy to implement. However, removal of words can be complicated due to shared nature of the word prefixes.

Insert goes something like this:
For each letter in the word:

  1. if the letter exists on the tree, go to the letter. If it does not exist, create it.
  2. If there is another letter, return to the previous step. If not, add a word terminating marker.

Here is my implementation of insert:


var trie = function() {
	this.head = {};
};

trie.prototype.validate = function(word) { 
	if((word === undefined) || (word === null)) throw "The given word is invalid.";
	if (typeof word !== "string") throw "The given word is not a string";
}

trie.prototype.add = function(word) {
	this.validate(word);

	var current = this.head;

	for (var i = 0; i < word.length; i++) { 
		if(!(word[i] in current)) {
			current[word[i]] = {};
		}

		current = current[word[i]]
	};

	current.$ = 1;	//word end marker
};

The hasWord algorithm is very similar to the insert algorithm.
For each letter in the word:

  1. if the letter exists on the tree, go to the letter. If it does not exist, the word does not exist.
  2. If there is another letter, return to the previous step. If not, check for the word terminating marker.
trie.prototype.hasWord = function(word) {
	this.validate(word);

	var current = this.head;

	for (var i = 0; i < word.length; i++) { 
		if(!(word[i] in current)) {
			return false;
		}

		current = current[word[i]]
	};

	return current.$ === 1;	//word end marker
};

Delete isn’t much more complicated, though the recursive nature of the algorithm does make it a bit of a pain. You have to go to the end of the word, and if no other letters are hanging off your word, delete from the end towards the head. As soon as you find an element that is being shared, you stop the deletion.

trie.prototype.remove = function(word) {
	this.validate(word);

	canDelete(word, -1, this.head);

	function canDelete(word, index, node){ 
		if(word === undefined ) throw "Bad Word";
		if(index >= word.length) throw "Bad index to check for deletion.";
		if(node === undefined ) throw "Bad Node at " + index + " for " + word;

		if(index === word.length - 1) { 
			//last letter
			//always delete word marker (as we are deleting word)
			return (delete node.$) && noKids(node); //if last letter of word, should be empty.
		}
		else {
			//any other letter in word
			//check child, and after child check, I am now empty
			if(canDelete(word, index + 1, node[word[index + 1]]) )
			{
				//delete me 
				return (delete node[word[index + 1]]) && noKids(node); 
			}
		}
		return false;
	};

	function noKids(node) { 
		return Object.keys(node).length === 0;
	};
};

My favorite advantage of using a trie is the ease in which a sorted list of words can be generated. All you have to do is output all the letters by Pre-Order Traversal. And sorting using a trie is fast – the worst case sorting is O(kn), where k is the length of the longest word in the trie.

trie.prototype.sort = function() {
	var word = "";
	var sorted = [];

	sortTrie(this.head, word, sorted);

	function sortTrie(node, word, sorted) {
		for(var letter in node) { 
			if (letter == '$') { sorted.push(word); }
			else { 
				sortTrie(node[letter], word + letter, sorted); 
			}
		}
	}

	console.log(sorted);
	return sorted;
};

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