How I passed the Foobar Challenge by Google
I was wandering around Google trying to find solutions to my problems when my browser went chaotic and suddenly my screen turned into a bash terminal. At first, I thought I got hacked and now it’s time to pay or lose my PC. But then, it introduced itself as the Foobar Challenge and invited me to participate. Naturally, I was up for an adventure, so I signed in.
What is the Google Foobar challenge?
Google Foobar is an invitation-based hiring challenge. We do not have any information on who gets invited, and what you need to do to get invited. The only thing clear is that:
- You need to use the Google Chrome browser
- You need to be curious about computer science, software development and IT
- You need to get lucky
The challenge consists of 5 levels, each a unique experience. This challenge is rumoured to be a part of the hiring process of Google, and solving the challenge can give you a chance to be recruited by Google. After Level 3, you are offered to leave your contacts (linked in and so on) and allow your code to be seen by a recruiter in Google, giving you a chance to be contacted.
However, one should not be treating the Foobar challenge as a means to get hired, but instead appreciate the nice and interesting challenges, a comfortable UI and boast their achievements
My Journey through the Challenge
Level 1 & Level 2
The first 2 levels I would consider as introductory, for someone who practices on Leetcode or has a background in math and/or computer science.
In level 1 I got a basic string transformation problem. The task was to transform a string by reversing its letters with the following rule:
a -> z, b -> y, c -> x and so on.
- After making a solution, you have an option to verify your solution against the tests. There are 10 tests in total, and the first 2 tests are given in the problem description.
Level 2 was a bit more challenging. I received a BFS/DFS problem and a math problem. Those problems took a bit more time but still were pretty manageable on the spot.
Level 3
This is where the fun begins. It consists of 3 problems and all of them were head-scratchers. One thing I really liked about these problems is the descriptions. All the levels from 1 to 5 are telling a story about you rescuing bunnies from an evil corporation managed by commander Lambda. For example, Here’s the problem description for the first problem of level 3:
Bomb, Baby!
===========
You're so close to destroying the LAMBCHOP doomsday device you can taste it!
But in order to do so, you need to deploy special self-replicating bombs
designed for you by the brightest scientists on Bunny Planet.
There are two types: Mach bombs (M) and Facula bombs (F).
The bombs, once released into the LAMBCHOP's inner workings, will
automatically deploy to all the strategic points you've identified
and destroy them at the same time.
But there's a few catches. First, the bombs self-replicate via one of two
distinct processes:
Every Mach bomb retrieves a sync unit from a Facula bomb; for every Mach bomb,
a Facula bomb is created; Every Facula bomb spontaneously creates a Mach bomb.
For example, if you had 3 Mach bombs and 2 Facula bombs,
they could either produce 3 Mach bombs and 5 Facula bombs,
or 5 Mach bombs and 2 Facula bombs.
The replication process can be changed each cycle.
Second, you need to ensure that you have exactly the right number of Mach
and Facula bombs to destroy the LAMBCHOP device. Too few, and the device
might survive. Too many, and you might overload the mass capacitors and
create a singularity at the heart of the space station - not good!
And finally, you were only able to smuggle one of each type of bomb - one Mach,
one Facula - aboard the ship when you arrived, so that's all you have to start
with. (Thus it may be impossible to deploy the bombs to destroy the LAMBCHOP,
but that's not going to stop you from trying!)
You need to know how many replication cycles (generations) it will take to
generate the correct amount of bombs to destroy the LAMBCHOP. Write a function
solution(M, F) where M and F are the number of Mach and Facula bombs needed.
Return the fewest number of generations (as a string) that need to pass before
you'll have the exact number of bombs necessary to destroy the LAMBCHOP, or
the string "impossible" if this can't be done! M and F will be string
representations of positive integers no larger than 10^50. For example,
if M = "2" and F = "1", one generation would need to pass, so the solution
would be "1". However, if M = "2" and F = "4", it would not be possible.
Languages
=========
To provide a Java solution, edit Solution.java
To provide a Python solution, edit solution.py
Test cases
==========
Your code should pass the following test cases.
Note that it may also be run against hidden test cases not shown here.
-- Java cases --
Input:
Solution.solution('4', '7')
Output:
4
Input:
Solution.solution('2', '1')
Output:
1
-- Python cases --
Input:
solution.solution('4', '7')
Output:
4
Input:
solution.solution('2', '1')
Output:
1This problem is a logical problem. There are no high-level algorithms that can help you here. Instead, you use a pen and paper and simulate the process described in the problem. Of course, you cannot put a full simulation of the process for the solution, because of the 10⁵⁰ constraint. Thus, you find a pattern that you can, then, model in a way to reduce the computations needed for the final result. For example, we can observe that if the number of bombs of each type is equal (that is, m == f), a solution does not exist. That is because, on the previous iteration, one of the values was 0, which means it cannot replicate to produce the other bomb.
Overall, this level took me some days to complete, but it was much more fun and I started getting really into it.
Level 4 & Level 5
In level 4, I was given 2 problems to solve, and both of them were pretty advanced. Without going too much into detail (for other people solving the problems), one of the problems involved a Max-Flow implementation and another problem involved Johnson’s algorithm for all-pairs shortest paths and the Bellman-Ford algorithm for finding negative weight cycles in the graph. I had to look up a lot of things in order to properly implement them. There are also a lot of caveats in the required output format that you need to take into account. For example, I spent 2 or more hours debugging a test case, where, turns out, I was returning [3, 4, 1] when I should’ve sorted the result and returned [1, 3, 4] (example made up)
One thing to note that the constraints are not very tight a lot of the times, so starting with a brute force solution and then looking for ways to optimize it is not a bad idea, also provided that for these problems you are given a lot of time.
I have to admit, that Level 5 was beyond my comprehension. It consists of only 1 problem, but that problem looked impossible to me. It involved knowing the simulating of the cellular automaton and predicting the potential previous states of a given state. I was looking up so many things that I cannot call the solution “mine” to be honest, but, nevertheless, it was a fun read and I am glad I got this far, but I did not have the time and patience to read so many things to solve this level.
Conclusion
After the levels are finished, you receive a Congratulations message (which is encrypted, of course, so gotta work a bit more). You also receive invite links that you can use to invite your friends to solve the foobar challenge (I am unaware if the people invited by the links get the invites of their own, but I assume they do not)
Very happy to invest my time into these problems, they really gave me a perspective of how much I know and how much I am still yet to learn and grasp. Hopefully, everyone who is invited to do these challenges finds joy and passion in programming and problem-solving.
Happy coding!
