# Google Foobar: a Post Mortem

#### This report of Google Foobar's death was greatly exaggerated

Two new problems were added on . Other two problems were added on .

So, what was1 Google Foobar about? I still don't know. Some said it was an hiring push for Python developers. Others claimed that Google was looking for cryptanalysts. There's even someone who proposed that it was an elaborate marketing ploy for the recently released "The Imitation Game" movie.

I won't talk in this post about how to get in, or what does it look like, since excellent articles were already written about these topics. I will instead describe the problems I encountered, the techniques I used and what I learned. I will also discuss a few conjectures I have about Google Foobar.

## The problems

Google Foobar currently consists of 30 problems articulated in 8 levels, where level $$i$$ contains exactly $$i$$ problems, except for level 8, which for now only has six. Problem difficulty does not always increase with the level: it does until level 5, then, when all the hard problems are gone, we get all the easier problems that we didn't solve before.

Since there's still people playing, I won't spoil their fun by posting the exact problem statements or their solutions. On the other hand, several problems are well-known, therefore discussing their solution should do no harm.

For example, one of these problems asks to calculate the number of integer points within a triangle, and this problem is solved in this Stackoverflow thread by rederiving Pick's Theorem for triangles.

Another problem asks how much water gets trapped in a given landscape, represented by an array of integers. This is a classical interview question, also solved on Stackoverflow.

As you might know, this problem has a solution that does 3 passes over the landscape array $$A$$. If you were to implement a simpler solution that does $$\max(A)$$ passes you'd discover that Google Foobar times out.

In fact, the possible input size almost invariably acted as a strong hint for the accepted time complexity. An input in the order of the millions would usually require a linear algorithm, while inputs in the order of the tens would imply some kind of brute-force or exponential algorithm.

Choosing the right algorithm and implementing it correctly were usually enough to advance to the next level. In some cases I needed a little bit of profiling: this just meant to run

\$ python -m cProfile solution.py

to identify and fix the bottleneck. In most cases the problem was solved by adding a very naïve memoization cache. For example, I frequently used this method to compute the binomial coefficient $${n \choose k}$$:

Sometimes this was too slow, but adding a memoization dictionary made the method fast enough. For example:

This was all that was needed to pass the vast majority of puzzles. A few puzzles required either more advanced mathematics or, in my case, a little bit of cheating.

## The difficult problems

In my opinion, three problems stood out for difficulty: undercover_underground, zombit_pandemic and grid_zero.

The first two asked to calculate the number of graphs having certain properties. In both cases, an explicit formula was out of question, but the problems could be solved by finding a recursive formula and applying it (usually with a memoization dictionary).

It's interesting to note that both problems can be solved using the techniques of Analytic Combinatorics, hinting that somebody behind Foobar has an advanced mathematics background.

I almost ran out of time on the last one. It essentially asks to find the minimal number of buttons to press to turn all buttons off in a variant of the Lights out game, in which pressing a button will flip the state of all buttons in the same row and column (including itself).

I tried everything I could with this problem, as detailed in this Mathematics StackExchange question, but I only managed to implement a brute-force algorithm that solved correctly 4 out of 5 test cases.

With only a few hours left, I resorted to... unorthodox strategies. I knew that the answer to a test case was a number between 1 and 225, so I submitted fake solutions until I determined the answer to the missing test case. Then I incorporated the fake solution in the rest of my code, hoped that Foobar was using the same test cases for verify and submit... and they did.