dimator | head

I love programming interview questions. The last cool one I got was the following:

Find the missing number out of an array of 999,999 elements, with the numbers from 1 to 1,000,000 randomly distributed in it, with one missing number.

There are different methods, of course, and I was asked to successively give a better answer, along with space and time complexity.

(If you want to figure this out for yourself, stop here.)

Method 1
Use quicksort to sort the array in place, traverse to find the missing number.
Time complexity: quicksort is O(n lg n), space complexity: already allocated.

What if we had infinite memory resources? Could we improve the run time?

Method 2
Allocate another array of size 1,000,000 elements, initialized to some sentinal value. Starting at array index 0, use the number in the original array as an array index into the new array, and store the number in the second array. What we’ve done is simply created a hash.
Traverse to find the sentinal; the location is the missing number. Initialization, population, traversal, each run O(n), space O(n).

What if we only had enough memory to fit 1 other number? Can we still find the missing number?

Method 3
Just sort in place with one integer at a time, swapping number at arr[i] with contents of arr[arr[i]]. If arr[i] == i, i++. Continue until whole array is sorted. Now traverse as before to find the missing number. (It turns out this method is not entirely error free, as certain inputs would give the wrong answer, but it demonstrates the point.)
Time complexity O(n), and traversal to find missing number, O(n). Space: just one temporary variable.

Pretty nice. Any other methods? I’m sure there are others, but the most elegant one (that I did not think of) was as follows:

Method 4
The sum of all the numbers from 1 to n has a closed form:

So, sum all numbers in the array, and subtract from the above to find the missing number. How clever! Stuff like this gets me going.

Well, I guess I’ve gone long enough without being a little introspective and talking about my blog. I bring this up because I am shocked and amazed that some of my friends read my words, and actually like what I have to say. I guess the reason I started doing this was to sort of collect my thoughts, keep track of ideas, and improve my writing ability. The ability to write effectively is a skill I would like to have, mainly because I see myself writing in some capacity in the future (it could only be software or API documentation, but still).

When friends send me email about my blog, I like to point out that they can do it too. You don’t have to pay to start a blog, and it’s a good way of getting your thoughts out of your brain, which serves to better organized your thoughts in your brain. I usually point them to Blogger, but there are many more free services.

A couple nights ago, I went to an open telescope event at the local university. The had a couple of big telescopes pointed at the Moon and Jupiter. It was pretty dumb.

Don’t get me wrong, I think astronomy and cosmology are immensely interesting. The problem I had with the event was that I remember seeing the same images of a tiny Jupiter, with 4 moons orbitting it, with the same 3″ amateur telescope that I had when I was younger. What’s the point of these expensive, huge (about 15″ in diameter) telescopes, if I could see the same detail (lack of detail) at home? The guy running the telescope even told me that basically, these types of telescopes are good for the Moon and Jupiter only.

I guess my rant is that, if you are interested in this sort of stuff, save your money. Even those big, fancy auto-pointing deals don’t see much more detail. Click here, and after a few hundred sub-clicks, you’ll learn a lot more, and you’ll see many more amazing pictures.

Wouldn’t it be cool if you could see where in the world people were working on Wikipedia? What I picture is some mix of Google Maps (or anything else that would give a top view of the world), an IP address geopgraphic locator, and some live Wikipedia stats. You could watch the map in real time, seeing little popups appear as people checked in changes to articles.

What sucks is that rcdumper, the live Wikipedia stats thingy, has been disabled due to high load. (I don’t even remember if it displayed the IP addresses of changes anyway.)

Wow, Google opening their Google Maps API was a great thing. Gmaps Pedometer is one of many hacks that are popping up. With it, I can show you the jogging route I take.

More and more companies are opening up their systems in the form of such APIs. They’ve realized that there are creative people out there with time on their hands. Some APIs are opened for profit, such as Amazon’s or eBay’s, but it’s also good to see people like Google and Yahoo doing the same, simply for the sake of spawning cool new services.