Programmer Competency Matrix

Ran across this excellent matrix

http://www.starling-software.com/employment/programmer-competency-matrix.html

I plan to start using this when I interview people, it'll help.

But more to the point, I suggest that it is highly valuable as a sort of check list that we should all use to help ensure that we build and maintain our skills. I suspect it is a rare developer who is comfortable with everything in the boxes on the far right of the grid, but if you've been in the industry for ten or more years and you can't comfortably check off most of them, it is probably time to start sharpening your skills.

Pick up a new development book, write some code in a language you've never used before. Code up a few new algorithms or data structures. If that doesn't sound like fun to you, you are probably in the wrong industry.

Recursive Money Counting: Or why avoid recursion

Last post I asked this:

Question: Write an algorithm that, when given some number of pennies, will print out all the ways that this value can be represented in nickels, dimes, quarters, and dollars, but don't use recursion.

In this post, I'm going to describe the recursive version and then talk about some of the differences between the two.

As mentioned, I don't much like recursion because of the overhead and because it makes things like ugly in a debugger.

But it does often lead to easier to develop and maintain code. It is, after all, just using another construct of a high level language, like objects or inheritance or function overloading. Those all have costs, but we happily pay them because it tends to make our software faster to develop and easier to maintain.

But here is the big difference in my mind: recursion is used most obviously in the design of the algorithms we most want to execute quickly: sorting, tree traversal, etc.

Algorists tend to love recursion because it makes for tidy algorithms (think quick sort, then try to imagine it without recursion: doable, but really ugly and no good for a text book). But algorithm design is exactly where you want to pay attention to performance issues. After all, if you just wanted easy to understand algorithms, we'd all just use insertion sort or bubble sort in all cases and be done with it and we certainly wouldn't worry about using adaptive sorting algorithms.

What is the cost of recursion? Well each time we call a function, we create a stack frame with the byte code we're executing and any local variables and parameters, then we push the frame onto the stack. When we return, we have to pop that frame off the stack restore the local variables and parameters and jump back to the byte code we were executing before we started. People who write JVMs and compilers care a bunch about making this run fast, but the fastest code is the code you don't execute so it'll always take some time. How much? Lets run through the recursive method and do some comparisons to find out.

For the recursive version of this algorithm, I'm going to leave out the printCurrency and getValue they are identical to the versions in the last post if you want to see them.

  public static void startRecursiveCountPennies(int pennies) {
      int[] mInts = {0,0,0,0};
      recursiveConvertPennies(pennies, mInts, mInts.length -1);
  }
  public static void recursiveConvertPennies(int pennies, int[] currency, int currencyTypeIndex) {
      while(true) {
          if(getValue(currency) > pennies) {
              currency[currencyTypeIndex] = 0;
              return;
          }
          if(currencyTypeIndex == 0) {
              printCurrency(pennies, currency);
          } else {
              recursiveConvertPennies(pennies, currency, currencyTypeIndex - 1);
          }
          currency[currencyTypeIndex]++;
      }
  }

So what is happening here? We're creating an array to represent the total number of each type of coin (except pennies, remember we just calculate how many pennies are left over for each of the coin type sets) and we're using a pointer to indicate where in the array we are working. While the value of our currency array is less than the total number of pennies, we call increment the counter and call ourselves, then increment the number of the type of currency the pointer is pointing at, and so on.

Before we return, we reset the currency type at our pointer to zero.

When the pointer itself is zero we'll print the values rather than calling ourselves again.

As a test, I commented out the printing of the values, set some timers and ran both the recursive and the non-recursive methods with 5000 pennies each. Over and over again, the nonrecursive version ran 20% faster than the recursive version.

So there you have it. Later on, I'll write a post about the recursive vs. non-recursive string mutation method. To be titled: how I didn't get a job I wanted back in 2001.

Take home lesson:

Recursion may make for easy to read algorithms, but be mindful of the costs.

The Rolling Counter Algorithm Pattern

Question: Write an algorithm that, when given some number of pennies, will print out all the ways that this value can be represented in nickels, dimes, quarters, and dollars. And don't use recursion.

Why not recursion? First, because the solution is more elegant. Second, because I don't like recursion. For more on why, see my next post "why I don't like recursion" ... or something like that but the short answer is that it is less efficient.

Before I get into this question, I’m going to discuss the rolling counter algorithm pattern for which this blog post is named: This pattern is often useful in interviews (almost as useful as the "just model it as a graph and traverse it or find the spanning tree" pattern) and usually ends up tripping me up, especially when I fail to recognize that I need to use it rather than (say) a bunch of nested for loops or worse: recursion. Maybe it trips you up too. Hopefully this post will make the pattern clear enough that it’ll stop tripping you and me up.

BTW: any time someone asks you to print the set BLA{…} where condition FOO holds true, you should think of this pattern. Ill try to make the why clear later.

You should think of a rolling counter as being analogous to the odometer on a car. As you’re driving the first roller of the odometer increases one mile at a time until you drive past nine miles. At this point, rather than increasing that roller to 10, it goes back to 0 and increments the second roller. Then you go back to incrementing the first roller for another ten miles. Eventually you have to increment the third roller, and so on. Until you run out of rollers, but you've usually replaced your car by then.

In code, you first, initialize the counter (note that if you are using java as I am, you'll get the initialization to zero done for you).

int[] mRollingCounter = new int[length];
for(int i = 0; i < mRollingCounter.length; i++) {
mRollingCounter[i] = 0;
}

Now the code to roll the counter:

int mCounterPointer = 0
while(mCounterPointer < mRollingCounter.length) {
mRollingCounter[mCounterPointer]++;
if( rollcondition() == true) {
   mRollingCounter[mCounterPointer] = 0
} else {
   break;
}
}

That is all there is to execute a single increase of the counter. The critical bit is the rollcondition() function. It is what tells the odometer that we've tried to roll past 0009 miles and should increment the second roller to 1. Or that you've tried to roll past 0099 miles and you need to increment the third roller.

We start with the first element of the counter and increment it. (This is equivalent to the odometer going from [0][0][0][0] to [0][0][0][1].) If this change triggers the counter rolling condition, set that element back to zero, move to the next element of the counter and continue. (this is what happens when we’re already at [0][0][0][9], first we go to [0][0][0][10] and since any element being greater than 9 is a roll condition for an odometer, we set the counter back to [0][0][0][0], move the pointer one over, and again increment to [0][0][1][0] at which point we break.

If this isn’t clear, code it up in your favorite IDE and play with it for a while (full code sample is below for the lazy) until you understand it or you can just TRUST ME and memorize it to be spit out in your next interview. Your choice, but I’d suggest understanding it.

So implementing an odometer isn’t that interesting but other things are. For example, if you can write a non recursive string permuter with this (ie, given a string of characters, print all the possible re-arrengements of characters). Or something to spit out all the possible ways that 50 cups of beer can be represented with various imperial units. I’m going to now get into the question that I started this post with.

 public static String[] mLabels =
     {"Nickles", "Dimes", "Quarters", "Dollars"};
 public static int[] mUnitBases = {5, 10, 25, 100};

 public static void convertPennies(int pennies) {

     int mCounterPointer = 0;
     int[] mRollingCounter = new int[mUnitBases.length];

     while(mCounterPointer < mRollingCounter.length) {
         printCurrency(pennies, mRollingCounter);
         mCounterPointer = 0;
         while(mCounterPointer < mRollingCounter.length) {
             mRollingCounter[mCounterPointer]++;

             if(getValue(mRollingCounter) > pennies) {
                 mRollingCounter[mCounterPointer] = 0;
             } else {
                 break;
             }
             mCounterPointer++;
         }
     }
 }

 public static int getValue(int[] currency) {
     int mTotalValue = 0;
     for(int i = 0; i < currency.length; i++) {
         mTotalValue += currency[i] * mUnitBases[i];
     }
     return mTotalValue;
 }

 private static void printCurrency(int pennies, int[] currency) {
     for(int i = 0; i < currency.length; i++) {
         System.out.print(String.valueOf(currency[i]));
         System.out.print(" " + mLabels[i] + " ");
     }
     System.out.println(" and " +
         (pennies - getValue(currency)) + " pennies");
 }

And there you have it.

Take home lesson:

Any time you need to iterate through all the permutations of a thing, consider using a rolling counter.