March 2014

Book: Programming Interviews Exposed

In my preparation for potentially taking on a general software developer role, Programming Interviews Exposed was recommended to me on several occasions and hence gave it a shot. It’s not too bad a read, and would most likely recommended it in the future, despite is having a few glitches; at the very least, it serves its purpose as a good source of concrete problems to solve.

Overall the book has the decent “Wrox feeling” I remember from way back in the days of secondary school reading Professional ASP.NET and Professional C#, and later Beginning Visual C++ 6 in the early university days (fond memories of a world opening up): on the surface the paper feels the same, even a few pages with faded print, and the contents is the same easy-to-read-yet-with-good-substance. It contains some good non-technical advise as well, so for its price I don’t see why anyone looking for a job in this area (and perhaps a bit rusty in the practical areas of computer science) shouldn’t pick up a copy.

The trees do not grow all the way into Heaven though, as the Danish saying goes, and there are a few place with room for improvement; for the interested here’s my two cents.

First of all, the writing follows the idea that the reader could have come up with every step of reasoning the authors take by just thinking the right way (and not letting much room for the use of prior knowledge). When coming up with a proposal, this approach may seem a bit strange yet it still teaches you the tricks. However, in analysing a solution they often skip arguments that could potentially teach you something. As a concrete example, the two-pointer solution for detecting cycles in a linked list (page 60 in the third edition) seems more like a useful trick to know than something I would have come up with in an interview situation; fair enough I’ve now learnt it. However, they give no argument to the claim that it has a linear running time; while I may not see the obvious, coming up with a proof was a useful exercise, taking me a car ride and the use of modular arithmetic to find. In short, you’ll need to look elsewhere for brushing up on proving and analysing algorithms (go Cormen et al.!).

Secondly, the given solutions sometimes seem to ignore standard mathematical thinking, and simply brute force their way through, in turn making it more confusing (at least to me) than it has to be. One concrete example is the problem of generating all combinations of characters in a string (page 116 in the third edition), which has a simple mathematical formulation in the form of the power set that also leads to an easy recursive implementation. Yet they do not follow nor mention this approach, instead doing a lot of hand-waving to end up with something that works but leaves me less certain about its correctness (their solution leaves out the empty string for instance, which may or may not be an error, but at least we know when the goal is a well-known concept such as the power set).

Thirdly, they do not always follow the official Java code conventions, which honestly seems a bit silly after several companies have highlighted the importance of this during interviews. For instance, the following code (page 93 in the third edition):

public void foo(String str) {
    int i, length;
    Character c;

    length = str.length();
    for (i = 0; i < length; i++) {
        c = str.charAt(i);
        // do first scan ...
    }
    for (i = 0; i < length; i++) {
        c = str.charAt(i);
        // do second scan ...
    }
}

goes against both the advise on initialisation at the point of declaration (length) and declaring local indices within their for-loop (i). Although a bit contradictory, it also goes against the advise given in Effective Java (Item 45 in the second edition) of not declaring a variable before use (c). To me, rewriting the code to this:

public void foo(String str) {
    int length = str.length();
    for (int i = 0; i < length; i++) {
        Character c = str.charAt(i);
        // do first scan ...
    }
    for (int i = 0; i < length; i++) {
        Character c = str.charAt(i);
        // do second scan ...
    }
}

seems both safer and easier to follow.

That was a lot of bashing actually; let me just make sure to express that overall I enjoyed reading the book, and almost all problems in it are interesting and with an entertaining side; of the latter I especially liked the pancake sorting algorithm. So, getting a copy is not a bad idea!

If curious, my programming solutions are available at the progin project on GitHub.

First Lomography X-Pro Slide 200

As disappointed as I was when I learned that the X-Pro Chrome from Lomography was not out of stock but in fact out of production, as surprised was I when an email popped in about a month ago saying that their other slide film, the X-Pro Slide, was now back in stock. I soon after grabbed a copy from the store, shot it, and went to pick up the prints today.

So I’ve gotten wiser since my surprise with the X-Pro Chrome. I now know that X-Pro stands for “cross processing“, and that this means using different chemicals during development than those originally intended. Handing in the Lomography film the other day was hence less shameful since I now understood what the woman behind the desk was saying and could respond with “you’re absolutely right, it’s a slide film for E6 processing, but would it be possible to have it developed in C41 anyway, for effect?” — won’t dwell too much on whether that’s cool or nerdy though.

I was a bit suspicious about the outcome for at least two reasons. Firstly because I’ve since learned that the X-Pro Chrome might have been a repackaged Kodak film of unmatched quality, and secondly because both the seller and various online galleries hinted that the photos will have a strong citrus tint. In the end though, they turned out much better than expected and I’ll probably head to the stores for some more soon.

Again I like the vivid colours, especially the orange/red shades as in Dissidi, Red and White, Child’s Play, and Fake Roof. The blue sky in most of them is not amazing, but looking at the negatives it might have been because I over-exposed too much. Lastly, what happened in Weird Red remains a mystery for now, as no extra filter was used nor was the lighting different.

The Ten Minutes After Enlightenment

I had a job interview earlier today, which didn’t go completely awful, yet didn’t go terribly well either. During the interview I only found a simple solution to one of the problems and then the ten-minutes-after-enlightenment happened: what you should have said pops up in your head just after the interview is over. Sometimes it may take a book or an internet search for this to happen, but in these cases it seems to be because of nerves settling down and the brain starting to work again, fortunately. Why? Well perhaps a methodology can help, by extending the offline preparation phase a bit.

What happened? Well, I was asked to come up with an algorithm for computing a certain result, and the only viable thing that came to mind was a brute force method (not completely unexpected by the way, as important exams have earlier been seen to make my brain strike and confusion taking over — one might assume it to be different after 18+ years in the educational systems, yet here we are). This is obviously not the best solution, but when nothing else presents itself I’ve found earlier that coding this naive approach often leads to an insight that in turn yields an improvement, sometimes simply in the form of a better understanding of the problem and the objective.

So, I started coding the naive solution, hoping something better would show up along the way. Unfortunately it didn’t, and I even managed to mess up the coding despite the fact that I’ve used the same programming pattern numerous times, not least in my functional programming. At that point desperation kicked in, a dark well opened up in the ground, and the universe decided to test my ability to catch helping hands while tumbling towards a deep bottom. The usual stuff. Fortunately though, my interviewer was very kind and basically put out a platform for me to fall on. I made it up the well again, and by then time ran out and the interview ended (with me having goosebumps, a mild shaking, and the urge to play the guitar loudly).

And then it happens. Less than ten minutes later, after having first summoned a ringing in my right ear and next looked out the window from the back of my armchair, a better idea that I wish we could have pursued occurred to me: a data structure could have helped (a radix tree in this case), at the very least by providing a space/time trade-off. But the interviewer is now long gone and this is for your enjoyment only.

This insight may of course have been just around the corner independently of the interview ending or not, yet my point here is that in my state at the time it seems unlikely: the problem, I suspect, lies more in not being in your best working state than in the problem being too difficult for the time frame.

So, how to improve? Given that it’s difficult to just stop being nervous, one thing I’ll try for the next one is to improve my methodology. More concretely, I’ll keep with me a list of the most commonly used data structures:

  • hash table
  • (doubly) linked list
  • heap
  • binary search tree
  • radix
  • etc.

and if needed, go over them asking How could the problem be solved using one of these? Similarly, I’ll try with a list of important problems (and good algorithms for them):

  • sorting
  • breadth-first search
  • max flow
  • etc.

in the hope that a suitable reduction could be enough. And last but not least, it may also pay off to keep a list of the most common programming techniques:

  • tail recursion
  • dynamic programming
  • greedy
  • etc.

in case nothing else yields.