I was minding my own business and googling about how python implements exceptions handling, when all of a sudden, I received the tempting offer to foobar. It’s nicely done with what looks like some javascript animation, which reminded me of the scene from the film “The Matrix”, when Neo gets contacted by Morpeus. And down the rabbit hole I went…
I’m mostly a C++ programmer, as this blog should make clear. But over the past few years I’ve been getting more seriously into python. Probably the fact that C++ and python work so well together has something to do about it. I’ve been considering including some python in these posts, perhaps this will be the push I needed.
Why I did it? I love coding competitions. I used to be pretty active in HackerRank competitions, even though they used to be hosted at ungodly hours in Asia (ie. from 1-3am). So I didn’t need much prodding. I hadn’t heard about the foobar challenge before, so I approached it assuming is just for the fun of it. It also had the feel of a well constructed algo challenge.
The approach: once you receive the first challenge, you find out you can provide your solutions either in python or java. I chose python. The next important thing is to read the constraints.txt file. This explains mostly obvious things, like no io, a list of excluded libraries, and that the version is set to 2.7.13. Which is quite important. This also led me to suspect the challenges haven’t been maintained much if they’re using an older version of Python.
Timeline: Overall I spent a total of 6 weeks on the challenges. I worked on them almost exclusively on weekends, so it’s not too surprising. I think it would be possible to complete all the challenges in 2 weekends if one really were to focus and hammer them out. But where would the fun be in that?
Tips and decisions that where helpful:
- IDE: I worked out all the solutions in PyCharm instead of the foobar editor. Mostly for familiarity, but also for the next point about unit tests. It’s also easy enough to paste your solution in to the foobar editor.
- Testing: May be obvious, but add all the supplied test cases as unittests (or your favorite other python test harness). The first few questions in level 1 and level 2 are fairly easy, but as you progress to more challenging levels, it’s quite a time saver to add all the corner-cases you can think of. It will save you time.
- Recursion: I tend to avoid recursion for coding competitions since I’ve had problems before where a valid recursive solution would run out of resources while running test cases. It’s not a huge deal to re-implement, but when seconds count, minutes are expensive. Suffice it to say, I avoid it unless it’s a very real improvement and of limited loops. In this case there was only 1 solution that would have been simpler and more elegant if implemented with recursion. In hindsight, it would’ve been fun to redo it and submit it to see if it failed. If only to get a hint as to the environment in which they run the solutions.
- Global vars/constants: it appears setting variables outside of a function is not allowed in the env. It was a surprise, but at least easy enough to deduce, since the 2 visible test cases were also failing.
- Precision: For the level 5, precision really came into play. It was important to think about the decimal points, and which python types have enough precision.
- Plan: For the first 3 levels, the challenges aren’t too difficult, but they also also don’t give too many days. It’s worth making sure you request the next challenge when you have at least a few hours.
The Challenges
Here’s a short description my impressions of each level. There are a few spoilers, so don’t read on if you’re planning to do the challenge.
Level 1 was easy and probably meant as an intro to the foobar environment. You can see the format you’ll have to follow, which is 2 test cases are shown, and 8 more are hidden. You can test you solution against all the test cases and see if they pass or fail. Once they all pass, you have to submit your solution separately. This was new to me, compared to HackerRank. With HackerRank once all your test cases pass, you’re done. Seems strange to have to verify and then submit in a separate step. I thought at first this meant there may be even more test cases, and that the verify step was really just a first step. But no. Once all the verify test cases pass, you’re all set.
Level 2 was a bit more difficult, and split into 2 parts. The first part was really fun. One of my favorites, and I have to say kudos to the author of that question for its elegance. You often see these questions are fairly silly, but this was quite clever. Overall these questions covered series and arithmetic.
After finishing this level, you get a referral code you can send to a friend for them to try out.
Level 3 is split into 3 parts. The difficulty does ramp up a bit at this level.
Part 3a was another one that was quite fun. Part 3b though I hit a wall fairly quickly. It isn’t too difficult, and really there are 2 parts to it. One of them working with really big number, which is a slight difficulty in C++, but not for Python. My solution solved quite a few of the test cases, but not all. It was unclear to me if the solutions here were “timing out”, as HackerRank would tell you, or providing the wrong answer. You have 7 days to complete each part of level 3, so I put the problem away for a day as I had to get back to real life. After coming back to the problem I found a mistake very quickly. A luxury one doesn’t usually have in competitions. Part 3c was a bit tougher. However, unexpectedly, the numpy module is supported in foobar. I was planning to write the solution with numpy at first as it’s just a few lines necessary, and then implement just the needed methods afterwards. However I was surprised to see numpy being supported. I was pretty sure it wouldn’t be as the constraints mentions only standard modules, and I used a fresh python 2.7 install and I had to install numpy. I’m not complaining 🙂
The topics covered in level 3 were elements of cryptography / binary logic, matrices, and computer engineering principles, as opposed to the algebra of Level 1 and 2. Since this is meant for recruiting, it did seem to me at this point they were testing the foundation of software. Also on the topic of recruiting, once you finish the level 3, you’re prompted to answer if you would like to be contacted by a google recruiter.
Level 4
At this point, challenges allow for 15 days to complete. There were 2 challenges at this level to solve.
Challenge 4A: Topic wise, it was all about flows, and pretty obvious from the description. Some of the flow algos I remembered from a university class, on the topic of “bandwidth brokerage”. Basically network flows, but with different service levels. But I suppose bunny flows are close enough. I did however have to refer back to the CLRS and Skiena books for the first time in this challenge. Definitely among the funnest of the challenges so far, and no quirky edge test cases either 🙂
Challenge 4B: Combinations and permutations were the topic here. I way overthought this one. Perhaps on the back of the previous few topics being graphs, my first instinct was to approach it graph wise, until I broke it down and realized the first step was really the only step here. Which turned out to be high school math at that. If you’ve read “Effective Python” (I’m a big fan of the “Effective C++” series from Scott Meyers), you’ll remember there’s a section about itertools around number generators. I had mostly just skimmed the section, but went back to it for a more in depth read and found all I needed to solve it quickly. This is another challenge where python was a big help compared to say C++.
Level 5:
I spent quite a bit of time reading on this one, and barked up the wrong tree at first. Which is fine since they gave 21 days to finish level 5, which is only 1 question! The challenge description makes it clear you can’t solve it with a loop, so knew there would be a formula for the sequence. It just wasn’t a sequence I’d seen before, but I did end up reading as I said a few other chapters until I found out the right one. Turn out it’s the challenge is based on a question posed in American Mathematical Monthly, almost 100 years ago! And famous enough that if you search for the right terms online, you’ll find it very quickly. I suppose part of the challenge is learning/searching. The one hitch was around precision. It was important for this task to think about not only the decimal points, but also around the precision of each python types. Overall though, I thought the level 4 challenges were more difficult.
Level 6+:
You can keep requesting more challenges. I already started the next challenge, which appears to be of similar difficulty to level 5 as they gave 22 days to complete.
Final thoughts:
Foobar challenge turned out to be quite a load of fun, and the problems are in fact quite polished, which makes it worth the effort. I recommend you do go for it when it pops up in your browser.