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.

Comments

Post a Comment

Popular posts from this blog

Gotchas with DBCP

I had to make use of DB connection pool in one of the applications that I was implementing. Since I am new to Java, everyone in the team was suggesting why don't you make use of Commons DBCP. Being a fan of reuse, I decided to make use of DBCP and started reading about the parameters that are exposed so that I can customize DBCP to fit my needs. While reading through the available configuration parameters , I was thinking, "I don't need to check the connection to be bad on every borrow or return. It is sufficient if I check for being bad only when the connection is sitting idle in the pool." So I set the testWhileIdle to be true and set the validationQuery to be "SELECT 1 FROM DUAL". I was thinking that the configuration that I had was the optimal for the situation in hand. But one thing I overlooked was, the default value for the testOnBorrow is true. So the moment you set the validationQuery to be any non-null value, every connection you borrow from the po
Read more

A note on Java's Calendar set() method

Remember that the Calendar's internal fields include year, month, date, hour, minutes, seconds, milliseconds and time zone. Whenever you are calling a set() method with multiple fields, like set(year, month, date), it will not affect the rest of the fields. Remember that there is no set() method with multiple fields available to set the milliseconds. If you would like to set the milliseconds, you must use set(Calendar.MILLISECOND, value). Likewise, if you are planning to set all the fields, its a good idea to reset all the fields using clear() method. This will clear milliseconds as well. Most of the times, millisecond field may not be of interest to you. But if you are going to use the UTC milliseconds, by calling getTimeInMillis(), then make sure you set the right values for milliseconds as well.
Read more

The mysterious ORA-03111 error

Recently one of the applications that I developed started throwing exceptions, that had the following message: SQL state [72000]; error code [1013]; ORA-03111: break received on communication channel When I googled around, I couldn't come across anything useful. Sadly enough most of the sites just showed the documentation for that error, without any explanation from anyone experiencing that issues. So here you go, with the best possible explanation that I could come up with. My application sets two things on the connection that is throwing this exception: It sets the fetchSize to be 2500 rows It sets the query timeout to be 10 seconds The database server and the application are separated over a long latency network (actually there is a NetEm box that emulates the long latency between these two boxes) which has a latency characteristic of 50+/-5 milliseconds. This is the whole setup. It is important to understand how the timeout is handled by the Oracle client (in my case JDBC clien
Read more