Nicholas Pike

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;
}