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.
