Cracking Google's Foobar Challenge 
Tags: programming, google, tutorial, challenge
Published: 2020-08-28 10:26:59


I've recently finished Google's coding challenge, [Foobar](https://foobar.withgoogle.com/). This has honestly been a really fun programming game, and I wanted to share my experience!

### What is it?

Foobar is a invite only coding challenge hosted by google. The prize for completing? A chance to be recruited. Once you pass a certain level, you have the option to submit your solutions and personal info to a google recruiter. Getting an interview isn't guaranteed however and not everyone gets a response from the recruiters. However I'd recommend not to focus on that too much and just have fun. If you really want to apply to Google, there's usually easier ways. 

### Great, where do I sign up?

Since this is invite only, directly going to the [foobar website](https://foobar.withgoogle.com/) won't help as there's no registration option. There's two ways you can get an invite.  

1. Getting an invite directly from google. This actually isn't super hard, you need to search for certain keywords like "arraylist java" or "mutex lock" on google multiple times to trigger the invite mechanism. The full mechanism is explained [here](https://codeforces.com/blog/entry/50841). 

![Up for a challenge](https://dev-to-uploads.s3.amazonaws.com/i/bombyiecs858mcl4jlz6.png)

2. Get an invite directly from someone who is already participating. Each participant, gets a maximum of two invites upon completion of certain levels in the challenge. So if you know someone who's already doing the challenge, you could ask them as well. 

### The Story So Far

Upon starting you are greeted with a unix shell  interface. You can interact with the shell using standard unix commands like "ls", "cat" and "cd". You find a journal entry at the very beginning which explains the situation to you. 

![Starting](https://dev-to-uploads.s3.amazonaws.com/i/gy83yo2s1thux4cjh7kc.png)

<div align="center">
  <font size="-4"> A bunny themed Star Wars fanfic story that you have to code your way through. Sounds too good to be true ;)</font>
</div>


### The programming challenges

In order to progress in your mission you need to perform a slew of programming challenges, from fixing Commander Lambda's wardrobe to rescuing bunny prisoners from the space station. These challenges are divided into 5 progressively more difficult levels. The tasks are similar to ones you find in competitive programming websites. Foobar especially has a lot of Dynamic Programming and math problems. A brief description of the levels: 

1. **Level 1**: 1 problem.
2. **Level 2**: 2 problems. Upon completion, invite a friend.
3. **Level 3**: 3 problems. Upon completion, option to provide information for recruitment by Google.
4. **Level 4**: 2 problems. Upon completion, invite another friend.
5. **Level 5**: 1 final problem. 

The solutions can be submitted in Java and Python 2.7 (yikes!). There's even an integrated code editor you can use. In my experience, the difficulty starts ramping up around level 3. However, difficulties tend to vary even amongst problems from the same level. One of my level 3 problems was about Markov Chains and it took me over 2 days to finish, whereas I finished the rest of level 3 in a few hours. 


### Grand Finale

At last, you've bested Commander Lambda's evil plans, rescued all the bunnies and saved the galaxy! You are now greeted with a mysterious encrypted message. What could it be?
![Encrypted](https://dev-to-uploads.s3.amazonaws.com/i/qv4rizubvgqqi7k069si.png)
After some next level ~~hacking~~ googling, I found out it's a simple XOR encryption. The message is XOR'd with my google username and then encoded to base64. So you can decrypt it by reversing this process. Let's use a python script to do just that

```python3
# Script source: https://vitaminac.github.io/Google-Foobar-Decrypt-Message/
import base64
from itertools import cycle

message = "L0YAHA0qFhseRk1uQVQOHCwSHEpNTXMCHAUCLBIPGARKdFtTTgs6Bw0IDAgwRl9JSSwVDgITGSdG U1NObhoGDhMIMAgRBQtuX0hKAA48CBYfCyQWBhlGTW5BVBwAJRwLBgQJc01TThwoEQoEFR5zQUlJ SToSDghGQXRGFQYBblNSTUYaPQ9SThM="
key = bytes("TasinIshmam", "utf8")
print(bytes(a ^ b for a, b in zip(base64.b64decode(message), cycle(key))))

# Output: 
# {'success' : 'great', 'colleague' : 'esteemed', 'efforts' : 'incredible', 'achievement' : 'unlocked', 'rabbits' : 'safe', 'foo' : 'win!'}
```

##### Advice

* **Take your time**. Google gives you plenty of time to finish each problem (Over 20 days in case of the level 5 problem). So there's no need to hurry, research the problems thoroughly and design a optimized solution. 

* **Know thy standard library**. For a lot of the combinatorics type problems, the python standard library was absolutely godsend. Don't code up functions that are already provided by Python/Java's standard library.

* **Take a break between problems** There's no time restriction between problems, so you can take as much time as you want before requesting a new problem. Some of these problems need a lot of time to finish, so don't rush in requesting new problems unless you're sure you have the spare time to invest on it.

* **Do Foobar to learn, not for a job** Foobar probably isn't the most efficient way to get a interview at google. It's completely uncertain if and when a recruiter will respond. So instead of worrying about that, do Foobar to learn, that way you'll be under a lot less pressure.

### Conclusion
Foobar is a great way to dip your toes into the world of programmatic problem solving. The whole thing is set up in a way so that you can learn as you go. I personally learnt a lot about Markov Chains, Backtracking and Cellular automata while doing these problems.

And if you need some more motivation, here are all the bunnies you'll be rescuing ;) 

![Bunny Gif](https://dev-to-uploads.s3.amazonaws.com/i/mbhmvwbyhjg95sl0ntsw.gif)