A few days ago Google Chrome opened their secret door to another world to me.

It was truly amazing and totally unexpected, literally, Chrome opened the door right from the the search field. I wish I had a chance to capture the screen at the moment of opening 🙂

By the way, if you haven’t heard about Google Foobar, look at this very good article at:

https://www.turing.com/kb/foobar-google-secret-hiring-technique

In my case, I felt a kind of “impostor syndrome”. I knew that this was a filter for potential developers, to narrow the best and non-trivial brains. However, I was absolutely not the best, probably, I just googled too much on programming topics, so Google decided to radically reduce the traffic from me by putting me into deep meditation about their particular challenges?

Anyway, I decided to have a look and use this chance to improve my Pythonic skills.

The first two levels were quite easy, I solved them without opening the theory about dynamic programming or Markov chains. But then I got stuck.

I’ve never participated in any programming competitions. When I write something, first I make the working code, then I make it work properly, and then, if needed, I optimize it. However, that was not the case with Google Foobar! Here you should think about the performance from the very beginning, otherwise, you will just not pass the acceptance!!

Here, as an example, my first version of the “ladder” challenge:

I was proud of this when started testing. It worked quite well on small ladders. However, how far I was from reality!! When I tried it with the maximum allowed in the test n=200, my notebook started to behave like taking off Boeing. After waiting for tens of minutes, I canceled the job and thought that probably Google Foobar would run it faster on their cloud servers. No way!

Then I lost hope that I could finish this challenge by myself with no help from the Internet and started to read and research how others solve particularly this challenge. I found numerous options on my lovely Stack Overflow; e.g. the most effective and obviously leading nowhere was that:

I used it as a unit test for my own and finally found that it worked on small numbers and stuck on larger, that’s why it failed the acceptance tests. I attempted to replace the recurse to nested loops, reached good results up to n=20, and then my brain finally started to smoke a little.

Here I took a big pause, finally lost hope that I could solve it by myself, and googled more about how others solve that puzzle using dynamic programming. The final solution was perfect:

I decided to prepare better for the next challenge about Mach and Facula bombs, prepared two buffers, allocated all the memory in advance, and avoided recurse. Here is an intermediate version of my code looked like:

However, it was another cannon for sparrows! These buffers were not needed at all!!

The final solution, effective, but absolutely not original, was:

I paused the challenge at Level 3. My Python definitely became better, and more effective, but Levels 4 and 5 are dangerous for my brain, I need to find a better heat sink first:)