Google FooBar First Challenge
Solving Caesar Cipher
In this post I will share my experience solving the first Google FooBar Challenge
.
While doing some search on Google, I received an invitation to participate in a code challenge by Google. I had no previous idea about it, frankly never heard of it. I accepted the invitation and I was redirected to FooBar. After log in, a CLI
with the instructions about the challenge and how to request a challenge was provided. The challenge had to be solved within 2 days.
The Challenge
Decrypt a code where every lowercase letter [a..z] is replaced with the corresponding one in [z..a], while every other character (including uppercase letters and punctuation) is left untouched. That is, 'a' becomes 'z', 'b' becomes 'y', 'c' becomes 'x', etc. For instance, the word "vmxibkgrlm", when decoded, would become "encryption".
Constraints for the solution:
- Java 8
- Limited execution time
- Prohibit usage of third-party libraries
- Parallel processing disabled
- Character limit to around 3000 (I don’t remember exactly)
Initial Thoughts
The rough idea I could come up after the analysis was:
- Manipulation of the ASCII value of the letters
- Simple maths, addition/subtraction, on numeric value of letters
Since converting this idea into a concrete algorithm was taking longer than expected, I moved to another solution.
First Attempt
The next simplest design for the solution I could come up with consisted of the following data structures:
HashMap
to store the encrypted letters and easy access of decrypted lettersStringBuilder
to store the deciphered text- Use Java 8 new method
String.chars()
API
1public static String solnWithStrBuilder(String x) {2StringBuilder stb = new StringBuilder();3x.chars().forEach(i -> stb.append(decrypt(i)));4return stb.toString();5}6public static char decrypt(int encryptedVal) {7if ( encryptedVal >= 97 && encryptedVal <= 122) {8 char encodedChar;9 Map<Integer, Character> decryptKey = new HashMap<>();10 for (int i = 122, j = 97; i >= 97; i--, j++) {11 encodedChar = (char) i;12 decryptKey.put(j, encodedChar);13 }14 return decryptKey.get(encryptedVal);15}16else return (char)encryptedVal;17}
The implementation provided desired output in the local environment but it failed to pass the tests.
Second Iteration
I reflected back on the constraints and refactored the code to use more primitive data structure:
- Replaced
StringBuilder
withCharacter Array
1public static String solnWithArray(String encryptedText) {2char[] encryptedCharArr = new char[encryptedText.length()];3Map<Integer, Character> decryptKey = new HashMap<>();4char encodedChar;5for (int i = 122, j = 97; i >= 97; i--, j++) {6 encodedChar = (char) i;7 decryptKey.put(j, encodedChar);8}9for (int i = 0; i < encryptedText.length(); i++) {10 char encryptedVal = encryptedText.charAt(i);11 if ( encryptedVal >= 97 && encryptedVal <= 122) {12 encryptedCharArr[i] = decryptKey.get((int)encryptedVal);13 } else encryptedCharArr[i] = encryptedVal;14}15return new String(encryptedCharArr);16}
But again the solution did not pass! At this point I was getting a little bit frustrated because there were no proper errors thrown. The output was just a list of failed tests. I lost interest after around an hour and I went back to my previous preparation method, solving challenges from other sources.
Third Iteration
The next day I went back to the challenge with around 3 hours remaining. To make sure the time spent here would be worthwhile, I did some search to know more about the challenge. Only then I realized that the challenge was invitation only, and was used by Google for recruitment. Those were good enough reasons for me to continue, but then I was seriously running out of time.
Then I searched for similar problems and solutions to find answers to these questions:
- How to encrypt a letter by another
- What are the standard encryption algorithms
A simple example by Baeldung answered my queries.
1StringBuilder result = new StringBuilder();2for (char character : message.toCharArray()) {3 if (character != ' ') {4 int originalAlphabetPosition = character - 'a';5 int newAlphabetPosition = (originalAlphabetPosition + offset) % 26;6 char newCharacter = (char) ('a' + newAlphabetPosition);7 result.append(newCharacter);8 } else {9 result.append(character);10 }11}12return result;
“Any fool can know. The point is to understand.” - Albert Einstein
Knowing that standard encryption algorithm used was Caesar Cipher
, I wanted to understand more that led to Cryptography, Cipher and more.
Keeping in mind that the time was limited, I skimmed the contents.
A **Cipher** is a method for encrypting a message, intending to make it less readable. **Caesar Cipher** is a substitution cipher that transforms a message by shifting its letters by a given offset.
Baeldung's post also made me realize that understanding of the encryption process was important to decipher. Therefore, based on Baeldung's framework, I created an encryption system that generated the cipher from the challenge.
1public static String encrypt(String textToEncrypt) {2StringBuilder result = new StringBuilder();3for (char character : textToEncrypt.toCharArray()) {4 if ( (int)character >= 97 && (int)character <= 122 ) {5 int originalAlphabetPosition = character - 'z';6 int newAlphabetPosition = ( originalAlphabetPosition + 25 ) % 26;7 result.append((char) ('z' - newAlphabetPosition));8 } else {9 result.append(character);10 }11}12return new String(result);13}
After generating the exact cipher, It was pretty much easier to write a program to decipher.
1public static String solutionWithOffset(String encryptedText) {2StringBuilder result = new StringBuilder();3for (char character : encryptedText.toCharArray()) {4 if ( (int)character >= 97 && (int)character <= 122 ) {5 int originalAlphabetPosition = character - 'z';6 int newAlphabetPosition = (originalAlphabetPosition + 25 ) % 26;7 result.append((char) ('z' + newAlphabetPosition));8 } else {9 result.append(character);10 }11}12return new String(result);13}
I submitted the solution then again it failed.
Time <10mins!
Accepted Solution
Refactored the code:
- Replaced
StringBuilder
withCharacter Array
.
1public static String solution(String x) {2int strLength = x.length();3char[] encryptedCharArr = new char[strLength];4for (int i = 0; i < strLength; i++) {5 int character = x.charAt(i);6 if ( character >= 97 && character <= 122 ) {7 int originalAlphabetPosition = character - 'z';8 int newAlphabetPosition = (originalAlphabetPosition + 25 ) % 26;9 encryptedCharArr[i] = (char) ('z' + newAlphabetPosition);10 } else {11 encryptedCharArr[i] = (char)character;12 }13}14return new String(encryptedCharArr);15}
Yay! All Tests Passed. Time <2mins.
Solution Submitted.
Review
The next day I reviewed the solution and recalled the overall process. Phew! It was a close call.
I wanted to refactor the submitted code as it was done in a hurry. And prior to refactoring, I wrote Unit Tests
to make sure that all the methods will work as before. Those tests did not need to be extensive covering all edge cases; neither should have many use cases, the solution had already passed Google's test cases.
Previously, I had an interview with Google in July 2019. It was more of a casual talk I had with a nice lady to see if I fit the available role at a certain location. Unfortunately, it did not work out.
I am grateful for both opportunities but I have enjoyed this experience more may be because I'm more of a code person.
Thank you Google!
If code is a better language to you then please find more at Github.
Solving Caesar Cipher