The world’s leading publication for data science, AI, and ML professionals.

My Google Foobar journey

Level 1 – getting the invitation.

WALK-THROUGH

Level 1 – getting the invitation.

FooBar Completion Screenshot ( image by author: Pratick Roy )
FooBar Completion Screenshot ( image by author: Pratick Roy )

Index

  1. My Google Foobar Journey : Level 1- Getting the Invitation. (This one)
  2. My Google FooBar Journey: Level 2.1 – Elevator Maintenance.
  3. My Google FooBar Journey: Level 2.2 – Gearing Up for Destruction.

How it started

The year was 2016–2017ish. I was a young computer science college student, who desperately wanted to be a developer. I loved to code and build stuff, and I equally hated doing MCQs (Multiple Choice Questions).

To me MCQs are an anathema to everything engineering should be. To do well in MCQs, you must memorize a thousand shortcut formulas, learn to apply tricks instead of applying concepts, and religiously avoid trying to answer the hard problems, all in an effort to answer as many easy problems in as little time as possible.

Now I was still in school, but to me logically it seemed that,

As an engineer, my job description is to take a sufficiently large, difficult, and ambiguous problem, learn, unlearn and relearn concepts, in order to break it down into smaller simpler problems, giving it more and more shape over time, until I have a good clean solution to the core concept of the problem, and its many surrounding edge cases.

Looking back with hindsight, I deem my younger self to be spot on with this analysis.

However, all college placement job interviews would invariably begin with MCQ rounds, so I think you can well gauge my paranoia of not making out of college with a job offer in hand.

Then one fine day, as I was fiddling away at some block of code, I probably got some error, or needed to look up some syntax, and as I Googled, the browser contorted to show me this message

FooBar Invitation ( image by author: Pratick Roy )
FooBar Invitation ( image by author: Pratick Roy )

Now, being someone who codes for fun, I wanted to play, but by the time the screen animations took place, I had already clicked on the first stack-overflow link. I fervently hit the back button, but no luck.

I was distraught. I realised the gravity of the error I just committed. I knew from previous reddit thread reads, what this challenge was about. It was Google FooBar Challenge[1]. I had just got an invitation, and I managed to squander it.

Now, If you are unaware of what this challenge is all about, simply put it is Google’s invite only secret hiring process. Once invited, you get to solve coding challenges, and if you complete it, you get a shot at a direct interview with Google. Moreover, the standard barriers of ridiculously strict time limits and the inability to use the internet, that are the patent of most online coding challenges and interview processes do not apply. You are given copious amounts of time to read, understand, research, tinker with and solve the problem.

If it isn’t obvious already, this was just the sort of challenge I was pining for. And I had messed up my one chance at seizing it. Being a stoic however, I managed to quickly get back up and laugh about how big of a klutz I was.

And that was that, life went on as usual, and then with a mix of luck and hard work, I managed to crack an internship opportunity at Amazon, giving me 6 months to prove my mettle in a real world software development setting. Another shot at playing my kind of game.

I know there might be a bit of survivorship bias talking here, but Seneca had once said,

Luck is what happens when preparation meets opportunity.[2]

And this time I was prepared and didn’t make any stupid mistakes. Since then, I have been an Amazonian, and super proud of it, and the memory of the challenge that got away slowly began to fade from memory.

How it ended

Then about a few months back almost 4 years since that fateful mis-click, as I was again stuck on some code, and was looking to leverage the wisdom of developers who have solved the problem before me, my browser again contorted to show me a familiar message.

FooBar Invitation ( image by author: Pratick Roy )
FooBar Invitation ( image by author: Pratick Roy )

And this time I didn’t repeat the faux pas. This time around the stakes were lower, I didn’t need the job interview anymore, but I wanted the challenge. I said I wanted to play and I was in.

And that brings me to last weekend, when I submitted the code to the last question. The challenge that had once got away was finally complete.

And Now The Journey

Have you ever taken a trip that you have been planning for a long time, building it up in your head, only to be disappointed when in the end you get there. This was not one of those journeys.

We are a species of storytellers, and fooBar makes you the protagonist in a story to infiltrate and dismantle Commander Lambda’s evil organisation, where all you have are your wits about you to save your bunny comrades.

And along this journey, you will learn as you go. From Markov Chains, to Cellular automata, there are so many fascinating ideas and concepts that the challenge exposed me to.

If you get the invite, and you like to code and like a challenge I’ll strongly recommend you take FooBar up on the offer.

One other point to note, if you are comfortable with python, it might make a lot of sense to go with it, as the standard library will provide you lots of useful functions. I personally used Java, as I am more comfortable with it, and frankly I am not a big fan of Python. Maybe someday I’ll write a post on aversion to python. If so I’ll link it here.

This post is now getting too big for my taste, so in the next few posts, I’ll go through the challenges 1 by 1, highlighting the learnings and insights that I gleamed from this challenge.

But before signing off, let’s solve Level 1, Question 1.

Level 1

Question 1 : Re-ID

There’s some unrest in the minion ranks: minions with ID numbers like "1", "42", and other "good" numbers have been lording it over the poor minions who are stuck with more boring IDs. To quell the unrest, Commander Lambda has tasked you with reassigning everyone new random IDs based on a Completely Foolproof Scheme.

Commander Lambda has concatenated the prime numbers in a single long string: "2357111317192329…". Now every minion must draw a number from a hat. That number is the starting index in that string of primes, and the minion’s new ID number will be the next five digits in the string. So if a minion draws "3", their ID number will be "71113".

Help the Commander assign these IDs by writing a function solution(n) which takes in the starting index n of Lambda’s string of all primes, and returns the next five digits in the string. Commander Lambda has a lot of minions, so the value of n will always be between 0 and 10000.

  • Test cases – Input: Solution.solution(0) Output: 23571

Input: Solution.solution(3) Output: 71113

At its heart, the challenge here is to compute a long series of primes. And anytime you face this challenge, your goto algorithm should be Sieve of Eratosthenes[3]. I was pretty sure Sieve would do the trick, but I had forgotten exactly how it worked, so I fired up a Youtube video to get a refresher. With that, let’s build the solution.

So, once the Sieve function is in place, all we need to do is

  • Slightly modify the Sieve function to produce a concatenated list of primes.
  • Calculating the substring from this list from index to index + 5, as essentially this would give us the next 5 dights from the string of primes after the index. This is exactly the output ID commander Lambda is looking for.
  • Furthermore given the constraints, this list needs to be at least 10000 + 5 numbers long. So with a bit of brute force checking, finding out all primes until 206412, will be good enough for our use case.

And that’s it. If you are interested in how I solved the other challenges, check out my repo.

GitHub – pratickRoy/foobar: My Foobar Journey

In future posts, I will be going through the key insights/learnings for the solutions from the other questions I solved. I’ll link them here. To be notified of the same, consider following me on medium and subscribing to get an email of the same sent straight to your inbox! 😊

Click Here To Subscribe 🙂


Sources, Footnotes & Further Reading Links


Related Articles