Binary String Decryption Via Bottom Up DP

This question is primarily lifted from TopCoder, but has been extended slightly. It is, however, very similar to a question I've seen at Amazon as well and the pattern (bottom up dynamic programming) is highly useful for interviews and, occasionally, for real life problems.

Suppose you want to encrypt a string of digits in some radix (binary works well, but the astute reader will realize that this implementation will break down with any radix greater than 4) by traversing the string and for each digit, adding the sum of its adjacent digits.

So 111101 becomes 233201

Algebraically described, encrypted[i] = source[i - 1] + source[i] + source[i + 1]. Where the string is assumed to be padded with 0's before the start and after the end.

Or, setting i to i - 1 and rearranging: source[i] = encrypted[i - 1] - ( source[i - 1] + source[i - 2] ).

Since there is no encrypted value of -1, source[0] can be anything available within the specified radix, so we'll try to decrypt based on each possible value of source[0], eg: 0 - radix - 1 and check that each computed value of source[i] is valid for that radix.

so our recursive definition is

source[0] = {0,1 ... RADIX - 1}
source[1] = encrypted[0] - source[0]
source[i > 1] = encrypted[i - 1] - source[i - 1] - source[i - 2]

    public String[] decode(String in, int radix) {

        String[] mResults = new String[radix];

        for(int i = 0; i < radix; i++) {
            mResults[i] = decode(in, radix, i);
        }

        return mResults;
    }

    private String decode(String in, int radix, int startValue) {

        char[] mString = in.toCharArray(); //
        int[] mEncrypted = new int[mString.length]; //encrpted
        int[] mDecrypted = new int[mString.length];
        //int[] mP = new int[mString.length]; //original
        //bottom up dp
        for(int i = 0; i < mEncrypted.length; i++) {
            mEncrypted[i] = Integer.parseInt(String.valueOf(mString[i]));
        }

        int mPreviousPrevious = 0;
        int mPrevious = 0;
        for(int i = 0; i < mEncrypted.length; i++) {
            
            if(i == 0) {
                mDecrypted[i] = startValue;
            } else {
                mDecrypted[i] = mEncrypted[i - 1] - (mPrevious + mPreviousPrevious);
            }
            if((mDecrypted[i] < 0 || mDecrypted[i] >= radix)) {
                return "NONE";
            }
            mPreviousPrevious = mPrevious;
            mPrevious = mDecrypted[i];
        }
        //now check to see that the last one makes sense
        if( mEncrypted[ mEncrypted.length - 1 ] != mDecrypted[mEncrypted.length - 1] + mPreviousPrevious) {
            return "NONE";
        }

        return intArrayToString(mDecrypted);
    }

    private String intArrayToString(int[] intArray) {
        StringBuilder mBuilder = new StringBuilder();
        for(int i = 0; i < intArray.length; i++) {
            mBuilder.append(intArray[i]);
        }
        return mBuilder.toString();

    }

So, what is the quick and dirty for solving something like this in an interview:

For any function F(x) that can be define with constants and F(i) where i is always less than X:
1. Define the function. Eg: F(x) = input(x - 1) - (F(x - 1) + F(x - 2))
2. Cache the values of F(x) as you compute them (though only as many as you need, in this case our mPrevious, and mPreviousPrevious)
3. Define the base cases and either initialize the cache, or check for them in a loop (we checked for them so we didn't have to do additional logic to catch the cases where the array is one or two digits long.

The rest is just string manipulation which you should be able to do in your sleep.

When I find some more time, I'll do another one of these for calculating the Levenshtein Edit Distance for two strings. A classic!

By the way, I doubt this is secure encryption so please don't kick my ass if you happen to be a security aficionado.

Quickie: Binary Printing

This one is probably about the right size for a phone screen question. I've seen this as print a binary string, print a decimal string, and print a hex string. They are all good and it shouldn't take someone more than a few minutes of thinking and a few minutes of scribbling to get it done.

    public static String printme(int i) {
        StringBuilder mOut = new StringBuilder();
        
        while(true) {
            if(i % 2 == 1) {
                mOut.insert(0, "1");
            } else {
                mOut.insert(0, "0");                
            }
            i = i / 2;
            if(i == 0) {
                return mOut.toString();
            }
        }
        
    }

For the reader: code up an integer representation without using ten else-ifs or java's automatic integer to string converters. Just append chars.

Quickie: String Reversing

An oldie but a goodie (actually, not a goodie, but I'll talk about that at the end). This question is often phrased in two parts:


First: Write an algorithm to reverse a string.


This should be pretty boring to you. Just start at the ends of the array and swap each element until the ends touch. I find keeping a start and an end counter to be easier to code on a whiteboard. Some people like to just increment a single counter for the start and calculate the end pointer from the length of the array. Probably a slight performance hit that way, but I wouldn't no hire someone for it.

        int mStart = 0;
        int mEnd = mChars.length - 1;
        while(mStart < mEnd) {
            char mTemp = mChars[mStart];
            mChars[mStart] = mChars[mEnd];
            mChars[mEnd] = mTemp;
            mStart++;
            mEnd--;
        }

So the second part of the question is: now reverse the order of the words in the string without reversing the words themselves so that a string "this is a test" would convert to "test a is this".


I'm not a fan of this for two reasons: First, half the candidates have seen this an know the trick. Second, for those who haven't seen it, it requires a flash of insight. Anything that requires a flash of insight just tests whether the candidate is lucky enough to have insightful flashes durring interviews. I'd rather see something test coding skill, algorithmic reasoning, grasp of recursing, anything like that. Just not luck.


But whatever, someone is probably going to ask you this question someday so here is the answer: reverse the string once, then reverse each word again. So first you make "tset a si siht" then you reverse that to "test a is this".

         int mStart = 0;
        int mEnd = mChars.length - 1;
        while(mStart < mEnd) {
            char mTemp = mChars[mStart];
            mChars[mStart] = mChars[mEnd];
            mChars[mEnd] = mTemp;
            mStart++;
            mEnd--;
        }
        
        int mLastWordStart = 0;
        int mLastWordEnd = 0;
        int mCurrentLocation = 0;
        while(mCurrentLocation < mChars.length) {
            
            mLastWordStart = -1;
            mLastWordEnd = -1;
            while((mCurrentLocation < mChars.length) && 
                    (mChars[mCurrentLocation] == ' ')) {
                mCurrentLocation++;
            }
            
            mLastWordStart = mCurrentLocation;
            
            while((mCurrentLocation < mChars.length) &&
                    (mChars[mCurrentLocation] != ' ')) {
                mCurrentLocation++;
            }
            
            mLastWordEnd = mCurrentLocation - 1;
            
            while(mLastWordEnd > mLastWordStart) {
                char mTemp = mChars[mLastWordEnd];
                mChars[mLastWordEnd] = mChars[mLastWordStart];
                mChars[mLastWordStart] = mTemp;
                mLastWordEnd--;
                mLastWordStart++;
            }
            
        }

There it is! Variations of this that I've seen include a question about how to flip a bitmapped image which is represented as a two dimensional array of pixels. The solution (which I'll leave largely to the reader) is treat each line of the file as a string to reverse and reverse them once. You could also probably do some cool pattern based conditional flipping by combining the word-by-word string reversal with the bitmap question.

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.

Distributed Sorting

So you've got a pair of servers (I'll call them servers A & B) and each of them has an array of strings in random order. You are to find a way to sort the strings such that if you lined the arrays up server A first, server B second, this combined array of strings would be sorted. That is to say: all the strings are sorted and the higher strings are all on server A and the lower strings are all on server B. These arrays take up most of the storage on the servers and your network connectivity between servers is mediocre.

How do you accomplish this with the lowest network traffic?

The naive solution is pretty simple given these constraints and looks like this:

First, sort all of the strings on each server locally.
Then compare the last string on A to the first string on B
If A[last] > B[first], swap them, then resort the strings locally on each server.
Otherwise, you are done.

So what is the cost (worst case where n is the number of keys per server):

Your local sorts are free since we don't care about those.
If you have to compare every single key, you'll make 2n comparisons.
And so the cost will be 2n * the size of the keys in network traffic + a small amount of overhead to open and close the connection if we use http or similar.

Great! So lets say you have a million ten character strings on each server. How long will this take? Twenty megabytes in a fast data center? A few seconds at most, totally reasonable.

And then things start to get interesting.

So... now we should consider the speed of the whole system, data transfer _and_ local sorting. A smart candidate will have already thought this far ahead, if they are accustomed to thinking about everything in terms of big O. But then it is easy to fall into the trap of thinking that network speed is so much slower than things that happen in memory that we can forget big O in situations like this. We'll see that we can't.

So, ok, we've got a good sorting algorithm O(n ln n) or maybe even O(k n) if you take advantage of the shortness of the strings to be sorted. Great, so we do that. Then, in the worst case we have to move all the strings to different servers, so that is n. AND we're resorting the strings again which should cost O(n) with each string we move across so we're looking at O(n^2).

So what does n^2 mean here? Well if we have fast memory, we can get each 10 char key out of memory in around 100 ns. So lets say (10^6)^2 * 100 ns. If I'm doing my math right here, that comes out to over 27 hours. So we spend a few seconds streaming data across the wire because we managed to minimize network traffic but we spend 27 hours resorting arrays of strings.

At this point, the fix should be pretty obvious. Move all the strings that you need to move, then sort them. But how do we know which ones to sort?

Well here is the trick, obvious to some, not obvious to others: for every string on server B that is lower in value than the lowest string on server A, we can move that string from B to A, and at the same time move the lowest string from A to B.

Think of the keys as arrays on both servers. Set a pointer at the end of the array for the first server (ie: the highest key on the lowest server) and a pointer at the start of the array on the second server (ie: the lowest key on the highest server). As long as the key at the pointer on the first server is greater than the key at the pointer on the second server, we need to swap the keys. Here is a worst case example (with single letter keys for simplicity):


After each swap, we move the pointers (the first server's pointer moves left, the second server's pointer moves right) and again compare the keys under the pointers.


Again, as long as the key at the pointer on the first server is greater than the key at the pointer on the second server, we need to swap the keys.



When we're done, we'll again have an unsorted array of keys on each server, but we can guarantee that all the right keys will be on the right servers. From here we can just resort the servers again, and we'll be done.

Take home lesson:
1. Even though moving data around a datacenter takes a while (20 ms to send a couple k around a data center) moving data around in memory still costs some time: 1/2 a ns for L1 cache kits, 100 ns to hit main memory. Yes, orders of magnitude difference, but:
1. O(n^2) is almost always worse than O( n ln n) even when the operations described by n^2 are much, much faster.