## Wednesday, April 27, 2011

### 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.

## Tuesday, February 22, 2011

### 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.