How I Solved Google Foobar — Google’s Secret Hiring Challenge

7 min readFeb 11, 2021

Recently I got this message while searching “Dependency Injection” on Google. It was Google’s secret hiring challenge!

Google Foobar Message

I remember reading about this in some article, but I never thought I’d get this opportunity. I was very excited so obviously, I hit “I want to play”.

Then I was redirected to a Unix-like shell interface, including some standard Unix commands like help, cd, ls, cat.

What is Google Foobar?

Google Foobar challenge is a secret hiring process by the company to recruit top programmers and developers around the world.

This challenge has 5 levels of coding challenges, and after finishing the third level I was prompted to fill in my personal information for a Google recruiter to contact me.

The storyline of the challenge is me infiltrating Commander Lambad’s evil organization 😈, and my mission is to sabotage her plans to use the LAMBCHOP doomsday device to destroy Bunny Planet 🐇.

Braille Translation

In this challenge, I had to convert plain text to Braille dots.

Each character is composed of 6 dots in a 2x3 grid, where each dot can either be a bump (represented by 1) or be flat (represented by 0), for example:

Given the plain text word "code", you get the Braille dots:11 10 11 10
00 01 01 01
00 10 00 00

and it becomes:

100100101010100110100010

The solution should take a string parameter and return a string of 0s and 1s representing the bumps and absence of bumps in the input string.

In the beginning, I didn’t know where to start, how could I know the representation they’re expecting to get?!

I figured out that they gave me the answer! One of the test cases they gave me was:

Test cases==========Input:
(string) plaintext = "The quick brown fox jumped over the lazy dog"Output:
(string)     "000001011110110010100010000000111110101001010100100100101000000000110000111010101010010111101110000000110100101010101101000000010110101001101100111100100010100110000000101010111001100010111010000000011110110010100010000000111000100000101011101111000000100110101010110110"

I realized immediately that this sentence contains all of the letters of the English alphabet!

All I had to do from that moment was just to use this hint to create that dictionary which maps each English letter to its corresponding Braille dots representation.

Gearing Up for Destruction

In this challenge, I had to place gears on a given peg’s locations, to make it rotate. For each peg, I had to decide the size of the gear I want to place.

Oh, and also I had to make the last gear rotate at twice the rate of the first one.

I realized it’s a simple system of linear equations. Every two adjacent gears should fulfill:

first_gear_radius + second_gear_radius = second_peg_location - first_peg_location

And of course including the constraint:

2 * first_gear_radius = last_gear_radius

So…I couldn’t find a way to solve these equations without the help of third-party libraries which is not allowed.

I had to find another way. I started simplifying the equations for 3 gears, then for 4 gears, 5 gears…until I came up with this pattern for n > 2:

notations:
pX = pegs[X]
rY = radius of p[Y]sign = -1If n is odd:
r0 = 2 * (-p0 + 2 * (p1 - p2 + p3 + … + (-sign) * p[n-2]) + sign * p[n-1])If n is even:
r0 = 2/3 * (-p0 + 2 * (p1 - p2 + p3 + … + sign * p[n-2]) + (-sign) * p[n-1])For n = 2 it’s easy,
for n <= 1 it’s impossible so the answer is(-1, -1)

Bunny Prisoner Locating

The goal of this challenge is to return the number that appears in the location (x,y) in an unusual layout, which looks like this:

So as you can see — the numbers are stacked up in a triangular shape.

The position of 1 is (1,1), with x being the distance from the vertical wall, and y being the height from the ground.

I played around a little bit:

                      | 4         | 4         | 4
| 2       | 2         | 2         | 2 5       | 2 5
| 1  ==>  | 1 3  ==>  | 1 3  ==>  | 1 3  ==>  | 1 3 6

And so on…notice that each column is one element shorter than the previous one.

So to answer this we need to know how many numbers were added up until (x,y).

Let’s understand this using an example where we want to find the number at (3,4), which is 18:

| 16
| 11 17
|  7 12 18
|  4  8 13
|  2  5  9 14
|  1  3  6 10 15

Let’s start by counting the highlighted columns, which contains numbers that ≤ 18:

| 16
| 11 17
|  7 12 18
|  4  8 13
|  2  5  9 14
|  1  3  6 10 15

I came up with a formula to count each column from right to left: sum y to (x + y — 1), In our case it’s 4 + 5 + 6 = 15 numbers.

We still need to count those we missed:

| 16
| 11 17
|  7 12 18
|  4  8 13
|  2  5  9 14
|  1  3  6 10 15

The formula: sum from 1 to y — 2, In our case, it’s from 1 to 2, so it’s just 3 in total.

Together we go 15 + 3 = 18. And this is the number we were looking for!

Prepare The Bunnies Escape

Given a matrix of 0s and 1s, where 0s are passable space and 1s are impassable walls, we need to find the shortest path from (0,0) to (w-1,h-1), where we are allowed to remove one wall.

[
 [0, 1, 1, 0],
 [0, 0, 0, 1],
 [1, 1, 0, 0],
 [1, 1, 1, 0]
]

My solution was to run BFS over all possible maps, each time with one wall removed.

I couldn’t think of a more efficient way, the only improvement I could think of was to try only the maps where the removed wall was between two passable spaces (otherwise it’s redundant).

Find the access code

A “lucky triple” is a tuple (x, y, z) where x divides y, and y divides z. For example: (1, 2, 4).

Given an array list of positive integers, we need to count the number of “lucky triples” of (list[i], list[j], list[k]) where i < j < k.

My answer has a time complexity of O(n²).

We store a map that maps an element to its number of divisors from the list.

For each element num1 in the array, we iterate over all the next elements — let’s call it num2, if num1 divides num2 we perform map[num2]++.

Let’s use an example: our list is [1, 2, 4, 8].

We begin by initializing a map where for each index we store how many divisors does it have:

[ 0 -> 0 ]
[ 1 -> 0 ]
[ 2 -> 0 ]
[ 3 -> 0 ]

Now let’s fill this map, we begin with list[0] = 1:

Does 1 divide list[1] = 2? Yes! so map[1]++
Does 1 divide list[2] = 4? Yes! so map[2]++

And so on until we get:

[ 0 -> 0 ]
[ 1 -> 1 ]
[ 2 -> 1 ]
[ 3 -> 1 ]

Fast forward to list[2] = 4.

Does 4divide list[3] = 8? Yes! So first we execute map[3]++ to remember that we found one more divisor for 8.

Now we got (X, 4, 8), and we need to know how many divisors 4 got? From the map, we can learn that map[2] = 2 (because 1 and 2 divide it), so we can add 2 to the total number of tuples.

Those are the “lucky triples” we just counted:

(1, 4, 8)
(2, 4, 8)

If you’ll do the whole process you will also find (1, 2, 4) and (1, 2, 8), so in total, we got 4 “lucky tuples”.

The last challenge is related to Markov Chains, and it’s pretty complicated so I decided not to cover it.

Conclusion

I haven’t got any call from Google, so I can recommend you to do it just for fun and learning purposes!

Here’s my GitHub repository for the solutions: https://github.com/sagyas/google-foobar