Invariant Properties

Ah, technical interviews.

It was a perfectly reasonable question but 1) we were discussing heaps so I naturally started thinking about the various things I learned in a graduate class in algorithms, e.g., how you rotate the tree as you add and remote values (read: check my copy of CLR) and 2) I’ve been studying Scala for the past few weeks and trying to learn how to “think in Scala.” We’ve covered trees and how you can manipulate immutable objects. We’ve covered Nothing (the bottom class) and how that’s different from Nil (null). So that means…

… so that means I had a nice case of brain lock. Fortunately I can babble well enough that people can still tell that I have a clue, it’s just really embarrassing to not being able to snap out an answer to a simple question.

At least I didn’t start the sample code with “def class …”!

The other fun question was synchronization. What can you say in a phone interview when you can’t see if you’ve lost the other person? For the record:

• You want to use a static ReentrantReadWriteLock if possible since readers do not need to block each other. You only need an exclusive lock on writes (and read locks so the writer knows there are active readers).
• If you don’t use (java.lang.concurrent) Locks then you should synchronize on a private static field in your class.
• You want to avoid using “synchronized” on the method or a block (without using a target) because the default behavior is to lock on the class object. This can be used for all sorts of mischievous.

Two postscripts:

First, this is one reason why I’ve become such a fan of unit testing if not outright TDD. It’s not because I think everyone writes sloppy code, it’s because the more you learn the more you realize that you’ve made assumptions. It’s a lot better to add a test case (e.g., say, can a list contain a Nothing value like it can contain a Nil/null value?!) than to check the code yourself and risk someone else making an unsafe assumption later.

Second, for the same reason I’ve become a much stronger proponent of using the standard libraries whenever possible, even if it’s not the most efficient approach. It comes back to assumptions again – the people who write the core libraries have had a long time to think about all of the corner cases. Unless it’s a real-time system where performance is the absolute top priority the milliseconds added by an inefficient call are probably better than the hours if not days spent tracking down some obscure bug. But it’s not an absolute – a millisecond here and a millisecond there and 100 concurrent users and you have a sluggish system. It’s always an engineering and management tradeoff of what hurts the least.