Connor's Blog

[1/5] Google Foobar Challenge

Last weekend something particularly interesting happened. I was searching for something in Google and the results page animated in a way I’d never seen before. The search page has easter eggs that you can trigger with phrases like do a barrel roll or askew, but what I searched wasn’t anything notable or worthy of an animation. If you’re interested what I searched, it was key expansion. Try searching it yourself and maybe you’ll get it too!

It looked kind like this, sadly I didn’t get a screenshot of my own:

Image courtesy of a user on reddit.

The results page split in half and a bar appeared. It said You're speaking our language. Up for a challenge?. Of course, my curiosity wouldn’t let me turn this down. I clicked I want to play and was taken to another site at foobar.withgoogle.com with a UNIX-y web shell. I did some research and apparently this is an invite-only Google interview/hiring process triggered by searching programming or computer science related terms. The algorithm to be selected isn’t exactly known these days but I think it’s random choice if your query is in their list.

Anyway, the shell displayed a basic introduction and how to request challenges. There are five challenges to complete in order and each one can be started with the request command. It creates a new directory containing a file explaining the task and two solution templates.

Task 1

I lost my screenshot of the first task and the shell doesn’t allow you to see what you’re already completed, but luckily an absolute legend has archived a lot of the Foobar challenges on GitHub. The one I got was called I Love Lance and Janice.

You’ve caught two of your fellow minions passing coded notes back and forth - while they’re on duty, no less! Worse, you’re pretty sure it’s not job-related - they’re both huge fans of the space soap opera “Lance & Janice”. You know how much Commander Lambda hates waste, so if you can prove that these minions are wasting her time passing non-job-related notes, it’ll put you that much closer to a promotion.

Fortunately for you, the minions aren’t exactly advanced cryptographers. In their 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.

Write a function called solution(s) which takes in a string and returns the deciphered string so you can show the commander proof that these minions are talking about “Lance & Janice” instead of doing their jobs.

Input:
    Solution.solution("Yvzs! I xzm'g yvorvev Lzmxv olhg srh qly zg gsv xlolmb!!")
Output:
    Yeah! I can't believe Lance lost his job at the colony!!

Inputs:
    Solution.solution("wrw blf hvv ozhg mrtsg'h vkrhlwv?")
Output:
    did you see last night's episode?

The task is essentially to write a “decryption” algorithm for a very simple variant of Caesar cipher. Not particularly difficult and I’d say it’s a fair task to give for an interview. Foobar allows submissions in either Java or Python - I went with Python.

Two approaches came to mind straight away. Since the range is quite small (a-z) you could write a lookup table and it wouldn’t be too horrible. Depending on other factors it could even be the best solution. That’s why pure algorithmic exercises in interviews are shit, you have no context on how the algorithm will be used so how can you design an appropriate implementation? But I digress.

The more appropriate solution I think is to use a bit of maths. What Google’s probably looking for is the realisation that you can lookup each character in the ASCII table and do a bit of maths with it.

Everything between a-z is contiguous in the ASCII table.

>>> ord('a')
97
>>> ord('z')
122

To make things easier we can break it down and “decrypt” a single character.

Writing it out like makes it pretty clear that you just need to subtract the offset from the position of z in the ASCII table and then of course turn it back into a character.

The algorithm to decrypt a single character can be expressed as:

chr(ord('z') - (ord(CHAR) - ord('a')))

The task specifies that all characters outside of a-z like spaces and punctation should be left alone. Pretty easy requirement to satisfy once again because we can test if each character is between a-z in the ASCII table.

I pulled this together in a few minutes outside of Foobar because it doesn’t have a REPL and the editor kind of sucks. Maybe they don’t want you to do that? Not sure.

START = ord('a')
END = ord('z')

def solution(x):
    new = []
    for char in x:
        if ord(char) >= START and ord(char) <= END:
            new.append(chr(END - (ord(char) - START)))
        else:
            new.append(char)
    return ''.join(new)

This could be boiled down into a single list comprehension but this isn’t a code golf challenge and I imagine anybody reviewing my code is looking for clarity, not conciseness.

START = ord('a')
END = ord('z')

def solution(x):
    return ''.join([
        chr(END - (ord(char) - START))
        if START <= ord(char) <= END 
        else char
        for char in x       
    ])

This was kind of fun and kept my mind busy for 20 minutes or so.

Fin

I’m not sure if I’ll do the rest of the tasks yet because I don’t intend to work at Google and I have other things to be doing. Unfortunately there is a time limit and I only have two days left to finish the second task before I forfeit. It’s a bit more complicated and digs into perfect binary trees - that’s something I’m not very familiar with as a non-grad infrastructure guy - but I’d like to give it a go.