Google's Secret Foobar Challenge

The other day while googling around I came across this message: 

“Curious developers are known to seek interesting problems. Solve one from Google?” Sure, why not?  Upon accepting the challenge I was logged into foobar and presented with a greeting that told me I had managed to infiltrate “Commander Lambda’s” sinister organization.

I did some quick searching around to find other people who had encountered this, and what their experiences were with it. Turns out this has been around for quite some time —but can be quite elusive. Getting into foobar can be tricky, and there’s no guarantee you will. Luck is a major contributor to stumbling upon this, and it’s highly dependent on searching for the right programming related keyword(s). When you’re lucky enough to search for the right topic though, the page will slant a little and the banner with the foobar invite will appear at the top of Google like the one I got.

There are five levels in total. Each level contains a number of challenges. The amount of challenges increases per level along with complexity. There’s some randomness to the content prepared for each foobar invite: your level 1 might not be the same as someone else’s level 1, your level 2 may or may not be the same as someone else’s level 2 content, etc. Each challenge goes like this: you are presented with a puzzle, and you have to code up a solution that will solve that puzzle. Once you start a level, a timer starts counting down and you have until the timer ends to complete and submit a solution. You navigate through the foobar console using basic *nix like commands — if you have any experience with any of these the interface will be pretty intuitive for you. You have the choice of submitting a java or python solution for each challenge.

It seems that in its earlier days foobar was utilized as a secret hiring tool for Google to spot talented coders. It seems that it is no longer actively utilized for that purpose, however. Still, it's a fun exercise to try, and even if you don't end up getting a prize out of it, the challenges can help to sharpen your algorithmic thinking skills and get prepare you for any future coding tests and challenges you might face. 

As I get around to it, I'll post my code and walkthroughs for each level of the challenge.

Level 1: Prison Labor Dodgers

This was the first challenge I encountered and the premise of it was pretty simple:

Two lists are given to you, named ‘x’ and ‘y’, that might look like this:

x: [13, 5, 6, 2, 5], y: [5, 2, 5, 13]

Or this: x: [14, 27, 1, 4, 2, 50, 3, 1], y:[2, 4, -4, 3, 1, 1, 14, 27, 50]

In any case, the goal is to identify the unique id, or basically the number that is present in one of those lists but not the other. In the case of the two lists above, the solutions (unique IDs) would be 6, and -4, respectively.

One thing to keep in mind is that there won’t be any inherit ordering or sorting of the numbers in each list, so you can’t count on this in your solution if you intend on taking any shortcuts.

This is what I came up with for a quick & dirty solution:

def solution(x, y):

    first = x

    second = y

    if len(x) > len(y):

        second = x

        first = y

    exists = {}

    for ID in first:

        exists[ID] = True

    for ID in second:

        if ID not in exists.keys():

            return ID

First I make sure the lists are ordered and processed accordingly based on their size (larger list gets scanned first to ensure we look at all possible values). We then iterate through the second list, and check whether that number exists in our dictionary; if not then that’s our unique ID and we return that. 

I decided to roll my own implementation rather than use any of python’s features (you could, for instance, convert both lists to sets and then compute the symmetric difference of them). There are many ways you could go about this. Make sure to verify your code solution for each challenge prior to submitting it! This will indicate whether there are any test cases your code hasn’t passed — so you can go back and try to find what part isn’t working. If you wait to submit a solution only to find out it fails a couple cases, you will fail that challenge. I’ve only done 1 challenge so far and passed all the test cases… so I don’t even know yet what happens if you fail a level.

Another note: Google has test cases prepared in the background - but you don’t actually know what these are, so your solution actually has to work. Expect that google has thought of the various edge cases that could occur from your code, because they typically have, and have built those in to the tests.