Google Foobar Challenge. What You Should Know
I’ve just passed the Google Foobar challenge and wanted to share my experience and some useful tips. If you don’t know what it is, there are a couple of articles online that describe it in detail, but I wanted to avoid repeating the obvious things and concentrate on my own experience.
What is Google Foobar Challenge?
This is an online challenge by Google in which you have to solve several problems of increasing complexity. Successfully solving the problems could get you to an interview at Google. To participate in this challenge, you have to:
- either get a referral link from someone who’s already participated and successfully solved at least some of the problems,
- or get a random invitation from Google while using Google search to look up some programming-related topics.
I’ve been coding for 16 years, and I search for programming-related information on Google multiple times every day. I’ve only gotten the invitation just a week ago while searching for something as simple as “python try except”. The logic they use to determine if you’re worthy to take a challenge is not clear. But you’ll know it when you see it.
The challenge consists of 5 levels and 9 problems distributed among them (1, 2, 3, 2, and 1 respectively). If you make it to level 4, you’ll be asked to provide your name, email and phone number, so that a Google recruiter might contact you in case they have a position to match your skills. I can’t say whether your chances are higher or not if you solve all challenges, but I would hope so.
I also don’t know whether your interview process will differ in any way from the one initiated by a regular self-application. After all, you’ve already invested quite a lot of time into solving their programming challenges, do you really need to go through it all over again on excruciating face-to-face interviews, solving the same problems under significantly heavier time pressure? (Actually, my bet is you do, but I don’t know for sure.)
What kind of problems should you expect?
Looking at the other reports of people solving Google Foobar, the problems seem to differ, but they are all tied into a story about subverting some malicious space operations involving fluffy minions. Think Star Wars with bunnies.
Quite a lot of textual background is given for every problem, so it may sometimes take a while to “translate” the task into an abstract algorithmic problem, like the ones you see on LeetCode.
I won’t quote any particular problems, as this would be unfair. But I’ll hint an the general level of complexity and some of the mathematical and computer science concepts I had to use and/or study to solve the problems.
Level 1. There’s a very basic problem accessible for anyone who’s ever written at least some algorithmic code. You find similar problems on LeetCode within the “Easy” complexity category. Should take you around half an hour, but you get a timer as long as 7 days. My task was related to implementing a simple decyphering algorithm.
Level 2. Two more complex problems, also 7 days to complete each. You can find such stuff among the “Medium”-level problems on LeetCode. One of my problems was related to sorting strings using a non-trivial ordering condition, another involved tricky manipulation with a two-dimensional array. Again, no special knowledge was required, only careful implementation of a straightforward algorithm.
Level 3. 3 tasks, also 7 days to complete each. This one took me a while. Starting from this level, the tasks are more similar to the “Hard” section of LeetCode. This was the most complicated level for me. There were 3 tasks in total, and they required some knowledge of dynamic programming and graph theory.
The first problem on this level took me the most time in the whole challenge. I honestly tried to solve it without googling even for some basic theory. Eventually, I gave up and started reading up on graphs. As soon as I stumbled upon the concept of absorbing Markov chains, I was able to quickly come up with a solution.
The second problem was related to finding the shortest path in a labyrinth, but with a certain twist. Check your understanding of BFS — this is an important concept to grasp for various interview tasks.
The third one was a typical dynamic programming task. However, I implemented a brute-force solution just to try it out, and, surprisingly, it passed all tests, so I didn’t bother re-writing it with lower complexity. I honestly believe you shouldn’t spend time over-engineering code until you have a good reason to do so. Not sure how this solution will rank among the Google recruiters, though.
Level 4. Tasks on this level were surprisingly easier than on the previous one, but the time to complete each was 14 days. Although these tasks did require the same or deeper level of knowledge in computer science, they were somehow more straightforward than Level 3.
Another problem was related to combinatorial distributions and was quite tricky to understand, however, writing out some examples on paper allowed me to notice a proper pattern and quickly come up with a solution.
Level 5. The time limit was 22 days. There was a single task which appeared to be deeply mathematical. I suppose one could intuitively come up with a solution, but just to put this into perspective, the theory behind the problem revolved around such obscure mathematical concepts as the Beatty sequence and Rayleigh Theorem. I solved it by reading up on those concepts and coding the algorithm from the mathematical explanation. Probably one programming concept that helped me significantly was knowing the BigDecimal class in Java that implements calculations with arbitrary precision.
All in all, the whole challenge took me a week to complete.
How to know why your code fails?
That’s the trick, you can’t know this for sure. Your code is run against several test cases, two of them are given to you as examples, all the others are hidden. You don’t know what data was used for the hidden test cases, and you don’t know why they’ve failed.
The reasons could be:
- compile error: in such case likely all test cases would fail;
- runtime error (array index out of bounds, null pointer exception, stack overflow are the usual suspects);
- wrong result (check more different inputs). Actually, first thing you should do when starting on a task is to import a testing framework like JUnit and cover your solution with tests.
- time limit exceeded (think about your code complexity and how to reduce it);
- you’ve misinterpreted the task. Read it once again carefully and check for any assumptions that you may have made, that were not stated in the task. For instance, I spent hours debugging one of the solutions, assuming that the input two-dimensional arrays were always square, but they weren’t.
Why does my code run locally but fails in Google Foobar?
I’ve solved the challenges in Java, so I can give you a few hints on typical Java failures:
- You’ve replaced the class name or the method signature with the wrong one. In Java solutions, the class should be named
Solutionthe entry method should be
public static, have a name
solution, and have a return type and argument types according to the task description.
- You’ve added a package declaration to your class. The package for Java solutions should be the default one (no package declaration).
- Check that your imports are correct.
- The Foobar Challenge uses Java 8, which is pretty ancient. Check that you don’t use any Java features that are not available in Java 8. If you use IntelliJ IDEA to write your code, use a proper language level and JDK distribution.
Some more tips
- Cover your solution with tests right from the start! Apply TDD when possible.
- Task descriptions and code templates sometimes have bugs in them.
- When you know the proper theory, some problems transform from insurmountable intuition-based challenges to trivial but tedious tasks. Don’t be afraid to google for theory. Do not google for solutions, though.
I’m writing this article while my impressions are still fresh. Solving these problems was sure a lot of fun, and I’ve learned some new concepts which I wasn’t aware of before. So even if I won’t get a call from a Google recruiter, I think this was time and effort well spent.
One interesting twist after solving the final challenge is that they offer to notify you by email when future challenges are available, whatever that means. But whenever this happens, I’m game. Definitely.