
What is the Foobar Challenge? 🧐
The Foobar Challenge is a coding challenge hosted by Google that can be completed in either Python or Java. I completed the challenge using Python. The challenge has its own server with specific, terminal-style commands. The problems are of various difficulty organized into 5 levels. Each question must be solved within a certain time limit. More time is given for the higher levels.
To read more about the Foobar Challenge, I recommend reading my previous article, which provides an overview and a break-down of the Level 1 problem.
Level 3 is where it started to get serious. Levels 1 and 2 tested the basics and took about 15 minutes to solve. Level 3 tested problem-solving skills and required hours of research. Unlike the prior levels, I didn’t immediately know how to solve these problems. I had to read the questions a few times and work out test cases on paper. Also, I had to research and practice some new concepts.
Research doesn’t mean Googling the problem name and looking at other people’s solutions. Instead, I tried to rephrase the question or search for phrases that seemed oddly specific to find relevant equations and models.
At first, I was little hesitant. Was Google tracking my search history? Would they consider this as cheating? However, as I progressed in the level, I realized these problems were mostly likely intended to force to you to look at outside material. I highly doubt Google expects developers to memorize Markov Chain formulas.
As you work through the problems, I encourage you research unfamiliar concepts especially if your solution becomes long and unstructured. These problems were designed to have elegant solutions. If you can’t think of an elegant way to solve the problem, that’s a clue that there is probably a formula or method that will simplify it. Remember, part of coding is researching the best methods.
Questions & Concepts 📚
Warning – Spoilers Ahead ⛔️
Below, I break down the questions and explain my thought process. I also provide solutions. However, I highly recommend you attempt the problem first. The best part of the challenge is the surprise and satisfaction of solving an elusive problem.
I debated not posting solutions and just explaining the underlying concepts. However, part of coding is learning how to troubleshoot and pinpointing where the code fails. Thus, I decided to post solutions so that if you’re stuck, you can see exactly where your logic diverges.
Level 3: Problem 1
Out of all the problems in Level 3, this was the hardest for me. I worked through a lot of examples on paper. The requirement to handle a 309 digit-long number seemed like a hint to try to solve this using binary numbers.
The objective of the problem is to reach one pellet with the fewest actions. The most efficient action is halving the pellets because then, n
will decay exponentially.

However, perfect exponential decay only works if n
is a power of 2. If not, eventually n
will reduce to an odd number and cannot be halved. In those cases, is it better to add 1 or subtract 1? The best action is whichever one results in a number that can be halved the most. Luckily, the binary form provides that information. The number of trailing zeros in a binary number is how many times a number can be divided by 2.
For example, consider n = 15
as shown below. The two series illustrate the two options for the first action: adding 1 (n = 16
) and subtracting 1 (n = 14
). Even though 14 is closer to the desired final state of 1, 16 is the better option because it can be halved more. As you can see on the right graph, the number of trailing zeros in the binary form corresponds to how many times a number can be halved.

To solve the problem, I first converted the input string (n
) to binary (b
) using the built-in bin
function. I used a while loop to reduce to b
until it reached 1. If b
is even, I halve it by removing a trailing zero. Halving b
as much as possible will minimize the total number of actions. If b
is odd, I choose the nearest neighboring integer with the most trailing zeros.
As mentioned, the quantity of trailing zeros indicates the how many times a given number is divisible by two. Numbers with more trailing zeros are prioritized because they allow more halving. In other words, the number with the most trailing zeros provides the most the efficient way to 1.
Level 3: Problem 2
To begin, I worked through lots of practices problems on paper. In doing so, I realized the solutions to bigger staircases consisted of solutions to smaller staircases. Solving for n
involves first solving for the smaller staircase sub-problems making this a Dynamic Programming problem.

I really struggled with cumulative nature of this problem. While I understood how smaller staircases contributed to larger ones, I couldn’t figure out how to account for the two step staircases. For example, when n = 7
, I saw how n = 3
was part of the solution, but I didn’t know how to account for other two-step staircases.

As an exercise, I simplified the problem and just tried to find how many staircases existed for a given height and n
. In other words, I took the graphic above and put in table form.

As I filled out the table, I figured out the algorithm. For each cell, I subtracted the staircase height from n
. Then, I took the remainder and visited that column (n = remainder
). The sum of that column equals the number of solutions. In some cases, the remainder was enough to build 1 step. To account for those cases, I added 1 along the diagonal. See the green numbers in the left figure below.

For example, when n = 8
and staircase height = 5
, the remainder is n = 3
. The 3 column contains two solutions: staircase height = 3
and staircase height = 2
. Thus, for n = 8
with staircase height = 5
, there are two solutions.
This method works, but it could be more efficient. Instead of visiting each cell in a column, the table could be structured so that rows represented the max staircase height. For instance, max staircase height = 3
would be the sum of the solutions for heights 1, 2, and 3 for a given n
. The purple numbers below represent this cumulative approach. Now, finding the solution involves visiting just one cell.
Note how the figure below includes a n=0
column. This way, the column index number equals the n
value. This small change drastically simplifies the code.

Level 3: Problem 3
After reading the problem, a couple of phrases jumped out at me. I searched for terms like "fixed probability state" and "probability state transitions" and eventually came across Markov Chains. Since there is guaranteed a path from each state to a terminal state, this is an absorbing Markov chain. A terminal state, also referred to as an absorbing state, means it is impossible to leave that state (i.e. zero probability of going to another state).
I never heard of Markov chains so before I started coding, I did my research. Here is a great overview of Markov chains.
The transition matrix, P, for an absorbing Markov chain with t transition states and s absorbing states is the following:

The transition matrix can then be used to find the fundamental matrix:

The fundamental matrix provides lots of information. But in order to solve the problem, one more matrix must be calculated:

In M, the rows represent starting states and the columns represent absorbing states. The value at M[i][j] is the probability of being absorbed by terminal state j if starting at transition state i. Thus, the number of rows in M will be determined by the number of transition states and the number of columns equals the number of terminal states.
First, I had to find the number and locations of the transition and absorbing states. Then, for the transition states, I had to convert the integers to fractions.
Given the following input:

The code above transforms it to:

Next, I need to calculate the I and Q matrices to solve for N. Since I couldn’t use libraries, I brushed up on matrix operations like dot product and matrix inversion.

Now, I need to solve for R.

Now that both R and N are solved, I can calculate the probability matrix, M.

Now, M must be formatted to match output specifications. Only the first row is needed since the question only asks for the probabilities when starting from state 0. As you can see above, M is in fractions. To format the answer as an array of integers representing the numerators of the probabilities, I needed to find the least common multiple. The LCM will be the common denominator among the probabilities.

The trickiest part of this problem ended up being the fractions and relearning matrix operations. Like I mentioned in my Level 1 article, this challenge is very specific about what type of outputs it will accept.
Here’s the solution in full.
Conclusion
At the end of the level, I was given the option to submit my contact info for a Google recruiter. However, that was over a year ago, and Google has yet to reach out.
Overall, I felt these problems were designed to test more than just basic coding skills. Solving these types of problems proves you can develop solutions despite tricky edges cases and memory constraints. Ironically, I found the problems to get easier as the level progressed. However, with each new problem, I also started to work smarter, not harder. I reread the problem. I paused and drew out some examples on paper rather than immediately start coding the first thing that came to mind. And, most importantly, I used existing resources to learn new concepts and brush up on old ones.

Thank you for reading my article. If you like my content, follow me on Medium.
Connect with me on LinkedIn, Twitter, or Instagram.
All feedback is welcome. I am always eager to learn new or better ways of doing things.
Feel free to leave a comment or reach out to me at [email protected].