Hey all! This blog post is about Google FooBar, how I got invited to it, the problems, and what happened at the end.
Invitation
Legend has it that Google FooBar is Google’s “secret hiring challenge”. You can take part in it only if you have an invitation and you if you perform well enough you may be hired! I am aware of two ways one can get an invitation :
- Google Search - Apparently, making enough programming related searches on Google can get you an invitation (as was the case with me). I have no idea regarding the algorithm which decides if you have made enough searches. I have been searching for solutions to programming problems since 2012 (okay, those searches must have been quite silly), and it was only in January 2017 that I got the invitation.
- Referral - People who have completed some challenges on FooBar get a URL which they can share with their friends to invite them to participate. Again, I don’t know how many challenges one needs to solve to get the referral link. I got mine when FooBar resumed after being down for extended maintenance for about a year.
Interface
After logging in, one is greeted with a linux-terminal like screen. help lists out the various commands that work in this terminal.
A request creates a new directory which contains the problem statement and the solution templates. The solutions can be in either Java or python. One can only have a single active challenge at a time.
At the time I was invited for the challenge, Java was, sort-of, my mother tongue :p. So I submitted my solutions in Java. The Java template for each problem had a function like this, which we were supposed to complete :
public static int answer(<params>) {
...
}
Problems
The problems were like regular CP problems. Most of them were solvable by using dynamic programming. However, at that time, I was a novice at CP and completely inexperienced at dynamic programming, and hence solving every problem was a matter of extreme pride and happiness for me.
The problems were divided into 5 levels :
- Level 1 had 1 problem.
- Level 2 had 2 problems.
- Level 3 had 3 problems.
- Level 4 again had 2 problems.
- Level 5 supposedly had only 1 problem.
I was able to sail through the first four levels easily (except problem 2 of level 3 - explained in this blog post), but I couldn’t complete the challenge as I failed to solve the only problem of the 5th level.
I had 25 days to solve the last problem, and I spent the first 10 days without much worry - I was doltishly expecting this one to be of the same difficulty level as the previous ones, which were surprisingly quite simple. As it turned out, I was very wrong. I came up with a few different ways to solve the problem, but all my solutions were essentially brute-force (with a time complexity of O(2mn)) and were naturally taking a lot of time.
When I lost all hopes of solving the problem on my own, I posted the question on StackOverflow, and even put a bounty on it! However, I failed to get an answer (the question has no accepted answer even today, because apparently the problem was a Cellular Automation problem, and my naive approach was very different from the expected solution).
Results
The status commands prints the progress of a user. For me, the output is like this :
When I cleared the third level, Google gave me an option to use the recruitme command, which supposedly shared my progress with a Google recruiter. I decided to use it at the end of the challenge. Later, since I couldn’t solve the last problem, I didn’t really expect anyone from Google to contact me. Still, hoping for the best, I used the command, and entered the information it asked - like name, contact details, education etc.
Unfortunately, I haven’t heard from any Google recruiter. Perhaps because I was still in school then - they asked this when I entered the details. Or maybe because I cheated on the 2nd problem of the 3rd level (read this blog post for details). Or perhaps because I couldn’t solve the last problem. Or maybe because Google stopped hiring through FooBar.
Whatever the reason may be, I wasn’t really disappointed. Solving those problems gave me immense confidence and the inspiration to perform better at the next opportunity I get. And of course, the invitation for Google FooBar is in itself a procurement to cherish!