Google Foobar Challenge – Python

This weekend I dedicated both days to attempting the Google Foobar Challenge. For those unfamiliar with the Challenge, it is a secret invite only challenge that is triggered randomly when you search programming related search terms. For me it was triggered with I googled ‘headless chrome’.

I was a quite surprised when this happened, as I had never heard of this. After a bit of research my curiosity turned to excitement, as I was told people who successfully complete the challenge get invited to do interviews at Google for a job. I asked my programming friends if they had ever heard of this and it was news to all of them. I showed a couple of them a youtube video talking about it and the term ‘Markov Chain’ came up as an example question. They were mentioning how they hadn’t done matrix math questions since uni. I certainly hadn’t and me also having just used python for just a week, wondered how far I could get doing the challenge. I have uploaded the questions I was asked and my python script answers to Git, so if it fancies you can read them in full there.

The challenge is divided into 5 levels, with a fun narrative of you infiltrating an evil organisation and bringing them down from the inside. From what I can tell is each level has a number of challenges equal to its number. So level 1 had 1 challenge, level 2 had 2, etc… After you beat level 3 you get to provide contact information to Google and they will contact you when they feel like. But from what I heard the further you go into the challenge the better your chances for an interview.

Challenge 1 (Level 1)

The first challenge talked about a cake with M&M’s around the border. With the task to be figure out the maximum number of slices you can cut the cake so that every piece has the same pattern of M&M’s.

I should have realised at this point that the challenges were all related to making algorithms. Which makes total sense as Google’s bread and butter comes from making algorithms. I really loved advanced and extension maths in high school and so was really keen to give these questions a crack. But as we will find out later you really need to have a strong understanding of maths at a university level to finish the challenge.

The trick I employed for this challenge was to use factors. If the cake is going to be cut into pieces with equal number of whole M&M’s, then it can only ever be cut into whole number of pieces which can only be factors of the number of M&M’s on the cake. Once I had the factors I looped to cut the cake into these equal parts and checking if the cut pieces were the same as the others. If you started by checking the factors from the smallest ones first you will be able to get the answer for the maximum number of cakes you can cut.

Challenge 2 (Level 2)

The second challenge talked about workers at this evil organisation having to give each other a salute every time they passed. With the task to figure out the number of times a salute is given if certain number of workers are walking in a hallway.

<<>><… is an example of a hallway with the symbols showing the way the workers are walking.

I found this question a bit more straight forward than the cake one. Instead of doing a count on the number of salutes each worker would take, I decided to count each worker that was walking to the right, and everytime a worker walking to the left came up I added my current total of walking right workers to the salute total.

Challenge 3 (Level 2)

This third challenge talked about finding the ID’s of workers based on where they sat in the office. But instead of things being simple, ID’s were based on a zigzag pattern. Like imagine shading a piece of paper starting from the corner and zigzagging with bigger and bigger zigs and zags. The challenge being if we were given the coordinates of the worker in x and y find what ID they would have.

Despite this question being the hardest to comprehend what they were asking for (this is kind of why I have a preference for chats and interviews from clients instead of getting requests being written up), my code for this was the shortest.

I wrote down the pattern on a piece of paper and then saw if there was a pattern in the numbers emerging in the left most y column, sure enough there was. And then I saw for a pattern in any corresponding x row for a picked y. Yep, also a pattern there. Once you created the formula for these two patterns it was very straight forward to code up and submit.

Challenge 4 and 5 (Level 3)

This was the level where my maths education met its walls. I had spent the whole of my Saturday on completing Level 1 and Level 2 challenges. And even though it was relatively easy to find the answers for the questions to these challenges on the internet, I didn’t want to submit plagerised work, simply to face more questions where I didn’t understand the math.

The math for understanding Challenge 4 was okay, as it involved running through an example and making logical choices. Challenge 5 funnily enough was exactly about Markov Chains, which is the exact same concept that my friends had commented on from watching the videos about the challenges. I spent a majority of Sunday trying to figure out if there was another way I could answer the question without using Matrix maths… but alas I might need to enroll into university level math classes if I ever want to comprehend the answers to these challenges.

Thanks for reading! If you come across any other fun challenges like this on your travels, let me know 🙂