Google Foobar Challenge: Level 3. Exploring binary numbers, dynamic… | by Katy Hagerty | Nov, 2023

Exploring binary numbers, dynamic programming, and Markov chains

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…