Two coding interview questions done badly, for different reasons

2013-11-18 (Updated: 2021-11-07)

Concurrency , Interviewing , Java

In my recent job search I was asked very few coding questions. Not sure why not—I was interviewing for individual contributor roles as per usual. Anyway, two coding questions stand out for basic errors I made. One was at the whiteboard, one was a “homework” problem.

The whiteboard problem had a very simple statement: Code, in Java, a breadth-first search, but switch the traversal direction at each level. A nice twist on a typical problem! I did it by inserting a sentinel into the standard queue of pending nodes. Using a Java Queue<Object> I inserted an (arbitrary) Integer as the flag, but it would have been just as reasonable to use a Queue<Node> and insert the tree root as sentinel. Remember to check for termination: if you’ve just dequeued the sentinel then if the queue size is zero, you’re done. Very short and sweet—but wrong! It hit me like a ton of bricks as soon as I drove off! It doesn’t traverse alternate levels in different directions, but only the nodes of alternate levels in different directions. Bungled! The error, my fault, was that I didn’t fully work things out, with an example, before I started coding. Had I, I would immediately have caught my error. In my defense, the interviewer and I were under very tight time constraints-it was a screening interview, it started late (scheduling mishap at their end), and we did a bunch of design questions first. On the other hand, he seemed very happy with the solution: he complimented it and said I would be invited back for a full loop (though I bailed on that for unrelated reasons). (Anyway, the correct solution. which immediately followed my shocking realization, is here.)

Now, what is it that you should never do with an interview homework problem?

That’s obvious: Don’t use it as an opportunity to try something new, that you’ve never tried before. E.g., a new software package or library feature. You just want to code it quickly and correctly and return it to the interviewer ASAP. Naturally, though I should have known better, that’s exactly the mistake I made with the second question I’m going to talk about.

The question was very nice—and nicely ill-specified. That is, incompletely specified. Simply: it was to provide two programs, one which would shuffle a deck of cards on request, and a UI the display the shuffled cards and request a new shuffle. You should be able to have as many instances of the UI going as you want, and they should all display the same deck of cards at all times, and any instance can request that a new shuffle should be performed, which all instances would then display. The concurrency nuance is that when a UI instance starts up it should get the current deck (without a shuffle), and never be out of sync. The interviewer requested two executables he could run.

So the basic concurrency situation is simple: Polling is out. A shuffle request could happen at any time so there’s no good polling rate or schedule that you could determine. Each instance needs to connect to the server and the server needs to broadcast all shuffle requests to all connected instances. But an instance can connect at any time and need the current deck. The solution to that is to run all requests through a single queue which can have two kinds of entries:

(Current Deck, callback address) – send current deck to requesting client
(Shuffle) – shuffle, save as current deck, and send to all connected clients

(The shuffle is obvious and I don’t need to explain it.)

So the only thing left is to pick the client/server technology, which was deliberately left unspecfied. The simplest and easiest—straight socket connections—I rejected for the stupid reason that it was “too simple”. Wrong! It was the right choice: it deals with connections to clients automatically, the sockets are full duplex, and the messages sent in each direction are extremely simple. REST doesn’t fit because REST doesn’t do callbacks. I didn’t want to bother with old-fashioned SOAP or XML-RPC, so I said to myself, “self, this is exactly what RMI was invented for, let’s use that”. I had never used RMI before.

Well, that was a major mistake. I’m sure RMI works fine in any of the standard containers: Tomcat, Jetty, whatever. But I didn’t want to tell the interviewer he needed to set up a container for the service. I wanted two standalone apps. (Actually, two standalone jars with suitable scripts to run them from the command line.) But unless I missed finding the magic blog post somewhere, RMI is a major PITA to set up to run without a container. The biggest problem—a major fail for Sun, unconscionable IMO—is that the Sun/Oracle supplied service/object broker for RMI, rmiregistry.exe, has no debugging or logging facilities whatsoever. You’ve got to get your classpath set exactly right and the class files for server and client (in a callback situation, each needs the other’s proxies) in the right places, or you get ClassNotFoundException. And, from rmiregistry.exe that is all you get!! An exception with nothing else to pinpoint what your configuration error is.

I see now that the principal benefit of the common Java containers, if you use RMI, is that they configure RMI for you in their own way and help you debug your problems!

Anyway, between configuration issues (classpath and policy files) it took me over a day to do this simple interview homework. I was so mad that RMI (an old technology by now) wasn’t working I just dug in and kept at it instead of starting over with sockets. To mollify my embarrassment I went overboard with a design doc. And to drive this lesson—never experiment with new technologies when responding to an interview homework problem—home for myself, I am herewith posting this post and the code and documents I wrote. Enjoy!