Wednesday, October 25, 2006

Another chapter in Programming Pearls

Managed to steal some time to read another chapter in Programming Pearls. As always, it was truly a refreshing experience.

Here is a question that I wanted to share:
You are given a huge array of unsorted numbers (32 bit integers) in a file. Let us say there are 4 billion numbers in that file. It is obvious that some numbers are missing (why?). How will you find out the first missing number?
Provide your answer(s) with explanation about space and time complexities.

Yesterday it was Top Coder Single Round Tournament 324. But they had made a typo when they announced the results. Instead of "SRM 324", they had announced the results with title "SRM 234." I managed to answer the 250 points and 1000 points problems. And I successfully challenged a 250 points solution as well. Still I don't know why my ranking went down, instead of going up. You can view my ranking here.

No comments: