Google FooBar Challenge - First Challenge

I am looking for a new job and preparing for interviews, especially technical ones. Then I received a surprise code challenge invitation from Google on Jul 26, 2020. It was a surprise as suddenly while I was searching for some programming topics in Google. Before this, I had a an invite for a general call from a recruiter in July 2019 to understand more about me and see if I fit the role that they were looking for.

I am going to record my experience the code challenge experience.

First Problem: Caesar Cipher Decryption

The Problem

Decrypt a code, 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".

There was some limitation to execution time and external Java library usage environment provided was default Java Runtime Environment (JRE) 8.

Solution

First initial thought I had was addition or subtraction of the letters to create an optimum solution. At that point I point I did not think of Caesar Cipher but bit shifting did come to my mind. After some analysis, implementing this initial idea deemed a bit tough and to save some time I went with the easiest solution I could find.

public class Solution {

 public static String solnWithStrBuilder(String x) {
        StringBuilder stb = new StringBuilder();
        x.chars().forEach(i -> stb.append(decrypt(i)));
        return stb.toString();
    }

    /**
     * Dencrypt small letters `a` to `z` only.
     *
     * First letter `a` is encrypted with the last
     * letter `z`, `b` with `y`, and so on.
     * ASCII values: https://www.cs.cmu.edu/~pattis/15-1XX/common/handouts/ascii.html
     *
     * @param encryptedVal int
     * @return decrypt char
     */
    public static char decrypt(int encryptedVal) {
        if ( encryptedVal >= 97 && encryptedVal <= 122) {
            char encodedChar;
            Map<Integer, Character> decryptKey = new HashMap<>();
            for (int i = 122, j = 97; i >= 97; i--, j++) {
                encodedChar = (char) i;
                decryptKey.put(j, encodedChar);
            }
            // key.forEach((k,v) -> System.out.println(k + "=" + v));
            return decryptKey.get(encryptedVal);
        }
        else return (char)encryptedVal;
    }
}

The above solution did the job on my local. As this this was a very rough implementation with probable reasons to refactor, it failed to pass any of the test cases.

Reflecting back on the limitation, I thought usage of StringBuilder class might have been the problem, and simple Array might be sufficient enough for the job, the change was made.

public static String solnWithArray(String encryptedText) {
        char[] encryptedCharArr = new char[encryptedText.length()];
        Map<Integer, Character> decryptKey = new HashMap<>();
        char encodedChar;

        for (int i = 122, j = 97; i >= 97; i--, j++) {
            encodedChar = (char) i;
            decryptKey.put(j, encodedChar);
        }

        for (int i = 0; i < encryptedText.length(); i++) {
            char encryptedVal = encryptedText.charAt(i);
            if ( encryptedVal >= 97 && encryptedVal <= 122) {
                encryptedCharArr[i] = decryptKey.get((int)encryptedVal);

            } else encryptedCharArr[i] = encryptedVal;
        }

        return new String(encryptedCharArr);
    }

Again the none of the tests passed. At this point I was getting a little bit frustrated because the error were not thrown back properly as the output was just tests failed list. To be honest, I had lost interest after one hour of trials and given up. I went back to my previous way. I wanted to solve the problem and any and came back to it again with less than 2 hours left to complete.

I reflected back to the problem statement and the constraints. I knew that there was other optimum solutions that would be based on my initial idea so I did search. I had never participated in FooBar Challenge before, and never herd of, I wanted to know more as I did not wanted to waste more time and continue my preparation the way I was doing before, review basics and practice code challenges at code challenges sites. It was good to know that this was invitation only, so I was motivated to continue.

Furthermore, I wanted to know about the encryption processes similar kind. I wanted to know the standards to do it. Then I came know about Cesar Cipher which I studies somewhere before. Then I started to dig more into it, gained some insights, and found a simple example to to encrypt letters as wished by another letter by Baeldung.com

        StringBuilder result = new StringBuilder();
    for (char character : message.toCharArray()) {
        if (character != ' ') {
            int originalAlphabetPosition = character - 'a';
            int newAlphabetPosition = (originalAlphabetPosition + offset) % 26;
            char newCharacter = (char) ('a' + newAlphabetPosition);
            result.append(newCharacter);
        } else {
            result.append(character);
        }
    }
    return result;

Cesar Cipher

A Cipher is a method for encrypting a message, intending to make it less readable. As for the Caesar Cipher, it's a substitution cipher that transforms a message by shifting its letters by a given offset.

Baeldung.com above code encrypts letters as necessary, but it did not decrypt. Also the letters substitution were done from letter a, which does not directly is our solution. But this provided a framework to find my solution. After some math and educated guessing, I was able to make encryption algorithm. Understanding encryption process was very important to decrypt.

Method below successfully encrypts letters as stated in the problem.

public static String solutionWithOffset(String encryptedText) {
        StringBuilder result = new StringBuilder();

        for (char character : encryptedText.toCharArray()) {

            if ( (int)character >= 97 && (int)character <= 122 ) {
                int originalAlphabetPosition = character - 'z';
                int newAlphabetPosition = (originalAlphabetPosition + 25 ) % 26;
                result.append((char) ('z' - newAlphabetPosition));

            } else {
                result.append(character);
            }
        }
        return new String(result);
    }

After successful encryption, decryption although was not straight forward, again, some educative guessing and hidden trials got the desired result.

      public static String solution(String x) {
        int strLength = x.length();
        char[] encryptedCharArr = new char[strLength];

        for (int i = 0; i < strLength; i++) {
            int character = x.charAt(i);

            if ( character >= 97 && character <= 122 ) {
                int originalAlphabetPosition = character - 'z';
                int newAlphabetPosition = (originalAlphabetPosition + 25 ) % 26;
                encryptedCharArr[i]  = (char) ('z' + newAlphabetPosition);

            } else {
                encryptedCharArr[i] = (char)character;
            }
        }
        return new String(encryptedCharArr);
    }

The above solution initially implemented StringBuilder class as in the original example that did not pass the tests. After refactoring StringBuilder with simple Array implementation, the solution passed successfully passed all the test and now I am looking forward to solve the second challenge.

Published Date: 26 July 2012

anitsh / til

Google FooBar First Challenge - Caesar Cipher #229

Checklist

Resources

Google FooBar Challenge - First Challenge

First Problem: Caesar Cipher Decryption

The Problem

Solution

Cesar Cipher