This year we took part in the Google Hashcode competition. This is a yearly competition where teams of 2 to 4 participants have to solve a real-life optimization problem.
It starts with a 4 hours online contest, with thousands of teams participating worldwide. The top 50 teams then move on to an offline phase in Dublin.
We were happy to organise a Hub in our Grenoble Office and had a lot of fun amidst pizza slices and coding. Cherry on top, we also reached a unexpected rank. Let’s see how it played out.
Before the event
A training subject is available online for the participants to get acquainted with the type of problems they might encounter. Practicing on it allowed us to extract from the experience some tools that did the boilerplate job to interact with the scoring system. We quickly identified that it was key to be able to launch our algorithm on all the test cases in parallel with a single click. Additionally we also introduced a mechanism that allows different algorithms to generate solutions that are saved only if they increased our score. Thanks to that it was easy to write optimization algorithms that can loop trying to enhance the current solution.
We also shared the same git repository, ensuring we were able to share code quickly between team members.
go Go GO!
With a decent preparation, we were eagerly waiting for the subject reveal on the event livestream. Once the clock reached 6.45 PM, the problem was unveiled: this year’s subject was about optimising the behaviour of a fleet of taxi wrt incoming ride requests.
Our first focus was to read carefully the subject, and make sure we all understood every detail. Once we were all on the same page regarding what we needed to achieve, we started thinking about the problem modeling. Usually, the concepts the problem involves are quite simple to model in any modern programming language, and this part was pretty straightforward. This quick brainstorm over, we knew we had to start splitting the tasks to be as efficient as possible. While a team member was in charge of the parsing of the test cases inputs and solution generation, the two others would throw their thoughts on a white board, trying to come up with the best algorithm possible.
Once the parsing / submission parts were done, we quickly implemented a greedy and simple algorithm just to ensure everything was working fine. A few bug fixes later, we could submit our first solution, get our first ranking, and get ready to climb the leaderboard. Validating those early parts was for sure an important step, as it gave us a certain advantage compared to the teams that waited the last moment to submit something. At this point, we already had spent one hour of the 4 allowed to us.
With 3 hours remaining, we had no time to waste. As every engineer knows, speeding up a program is just a matter of spawning threads, so we started parallelising our work. Two of us would try to iterate on our algorithms, exploring different approaches to solve the problem, while the last one focused on improving our last submitted solution to try and get a bit more points. The final score being the sum of the best scores we got for each of the test cases, working in parallel was great because we could test different algorithms faster and select the best performing one for each test case. Moreover, people thinking in different ways meant someone could come up with a solution particularly appropriate for a specific test case, thus, improving our score.
A couple of slices of pizza , a ton of commits and a lot of submissions later, the leaderboard froze one hour before the end of the event. At this point, we were ranked 72nd out of around 5000 teams, and entered the final sprint with a good hope to make the cut. We did our best to improve our final algorithm, as we felt it was too late to come up with something radically different. With a few tweaks, we were able to gain some points. Two minutes before the end of the event, we submitted our last solutions, hoping this would be enough to enter the top 50.
Spoiler: it was not . Our final rank ended up being 92nd worldwide (5th among French teams), which was both disappointing and satisfying, as we fell just a tiny bit short from the qualification, but way above our expectations as this was our first participation to the event. Overall, we had a lot of fun, and we did not see the time fly while coding in a stimulating atmosphere.
Lessons learned
If you want to aim at the top ranks, you need to come prepared. Having a project already set up with pre built utilities to handle the input parsing and solutions submission saves a valuable amount of time, and will allow you to focus on your algorithm itself.
Hashcode is a sprint, and saving 30 minutes to 1 hour makes a difference. Most of the best performing teams were able to submit a valid dummy solution a few minutes after the contest started.
Don’t be too ambitious from the start: we feel that we were successful because we were able to submit a simple solution early, and then iterate on it.
Using the judge system as a feedback loop to test your intuitions early and fast is the way to go.
And last but not least, preparing through the year by participating to coding challenges will help you come up with the right responses to the questions the problem raises: a lot of algorithms or thought processes can be reapplied to a diverse set of problems this kind of contest typically offers.
With the experience earned from our first participation, we will definitively try to do even better next year!
Resources
https://hashcode.withgoogle.com/
https://hashcode.withgoogle.com/2018/tasks/hashcode2018_qualification_task.pdf
Post written by:
From L to R : Cedric Reymond – Software Engineer R&D, Gregory Riberon – Snr DevLead R&D & Gabriel Restori Soares – Software Engineer R&D.
-
CriteoLabs
Our lovely Community Manager / Event Manager is updating you about what's happening at Criteo Labs.
See DevOps Engineer roles
