NPike.net - Like nailing jelly to the wall.

Fear not… I have not abandoned this project - life has just been incredibly busy, and the extension was at a level of functionality that worked for me.  To top it all off my trac (issue management) database broke with an upgrade of python and I have not been able to fix it.

Last night I setup MantisBG on my staging box, and got it working with my subversion repository that currently holds all my code.  I have begun recovering tasks from trac, and putting them into Mantis - once that is finished I will begin work on the first Milestone for GCN3  (which will be a complete rewrite of the extension, that I started several months ago but never finished).

I expect the following in the first Milestone:

• Firefox 3 support
• Basic features, completely utilizing the GData API
  • Won’t be requiring users to manually import their feed URLs anymore
• The complete rewrite of the Core code will fix many many existing bugs that plague current users (thanks for bearing with me here folks)
• Better localization
• Other then that, no new features for Milestone 1.

Bought this awesome game called Rock Band last Friday after work.  Heres the construction process after tearing into the box:

The Cat doesn’t quite know what to make of the drum set yet.

Shortly after buying the game, Jennifer’s roommate broke my drums:

I got sick of waiting for him to remedy the situation, so I fixed them myself! (brilliant)

(Yes those are butter knifes)

The finished product (after lots of black duct tape):

So I had another initial interview with a Microsoft developer this evening - this time over the Phone instead of in person.

The problem I was given to solve:

You are given an array of size N, filled with the consecutive integers from 0 to N-1. One of the integers is missing from this array. Write a function to find it and return it.

Example Array: A[] = {0,1,2,3,4,5,6,8,9,10}

My first solution was to traverse the array, and asser that each index was only 1 greater then its previous index. The ideal solution is to simply check that the value at the current index in the array, equals the index. So in the above example, A[0] = 0, and A[1] = 1, and so on.

Once you find an index that does not match the value - then the current index has identified the missing integer.

// find the missing int in an array of consecutive ints
int findMissingInt(A[]) {
	for (int x = 0; x < 10; x++) {
		if (a[x] != x) {
			return x;
		}
	}
}

While this solution works - it is a little slow if you have a ton of elements (like 1000). O(n) to be exact. Every single element needs to be visited to find our missing integer.

So Mr.A (the interviewer) asked for a better solution - one that is fast then O(n).

Below is the final solution. Which unfortunately I feel took me too long to realize - after 30 minutes on the phone I was already well flustered and starting to draw blanks on the simple aspects of life.

int findMissingInt(A[]) {
	int low, high, mid;

	low = 0;
	high = 10;

	while (high > low) {
		mid = low+()(high-low)/2);

		if (a[mid] != mid) {
			// missing integer is on the left side of the list
			high = mid;
		} else {
			// missing integer is on the right side of the list
			low = mid;
		}
	}

	// once high is < low, we have found our missing integer, it will be the high bound.

	return high;
}

Took some time this evening to spruce up the iPhone/iPod application a little bit, screenshots below!

(http://code.google.com/p/npike-touch-xboxlive/)