Google Hash Code

 

Google Hash Code

What’s Hash Code?

Ok, first things first. What’s Google Hash Code? Well, it’s a competition that Google organises yearly, where students and professionals team up and solve a real-life problem through the magic of programming languages. The programming language you choose doesn’t matter (you submit the output files) and teams can consist of one to four people. It’s pretty international, the participants can be from Europe, Africa and the middle East. The latest Hash Code event (or rather the qualifying round) happened last week on the 20th of February. And I’m happy to say - our team participated.

What Team?

So, a few months back, my friend Tom (IBM Bluemix) approached me and suggested forming a team. It sounded cool, so I found two more people - David (Kobalt Music Group) and Jamie (i6 Systems) and thus the NoTeamFoundException team was formed. We all met up in a serious environment two weeks before the actual competition and worked through a sample problem on a whiteboard, then wrote a few bits and pieces of code. It was one of the old Hash Code problems and was a real-life problem of cutting a pizza (can be found here). So we practised working together and decided that we’re sort of prepared.

What Was It Like?

Here’s what it was like on the day. The actual task was released at 5:30pm GMT and we had to submit our results by 9:30pm. So we hid away in an office with a whiteboard, David’s laptop screen being cast onto a huge TV, two 18’’ pizzas, one 15’’ pizza and some drinks. The problem presented to us was essentially a caching problem. Here’s how it went.

You have:

  • Endpoints (with information on latency and corresponding caches)
  • Caches (latency and cache size)
  • Videos (size)
  • Requests for videos (contain a popularity rating, a video id and an endpoint id).

The point is to figure out which videos to stick into which caches for maximum performance. More details here, yo.

Theory. So we decided to be organised and spend the first hour whiteboarding the solution: coming up with a general/naive approach and solution design. Design being - what kind of objects do we want to have (Cache, Endpoint, etc), what do we want to have inside those objects. Then we can spend, say, two hours coding up the solution and end up with a free hour to think of optimisation.

In practice, we’ve spent roughly the amount of time we expected on whiteboarding. Then moved on to coding it up, to keep it fair we decided to split the coding task into chunks and take turns around the laptop, so that everyone gets to play around with code. In practice it showed that if you’re not attentively keeping track of what the other person is doing - it takes a bit of time to get your bearings once it’s your turn to code. And also I think I hogged the laptop for a bit (not proud of myself, to be honest).

After a while we realized that we haven’t really designed the whole system on the whiteboard and there were gaps that we were filling as we were writing code, some gaps turned out to be bigger than they seemed in theory, others required making decisions that lead to that burning want of optimisation of existing code. So, in the end, we kind of gave in and started optimising before the naive version of the program was finished. Ultimately, I think, the combination of filling the gaps, optimising and having several people write code confused us all a bit, so we finished our v1 of code fifteen minutes before the deadline. We did manage to stick in a couple of quick optimisations (don’t bother checking anything if the size of the video is greater than the defined cache size; check if cache latency is actually better than downloading the video directly) into our solution in those last fifteen minutes though.

Did We Learn Anything?

Nope. Yes. Well, maybe. We ended up taking the place numero 1,030, out of 2,815; it’s not as bad as it sounds, top half and everything. I think overall it was a positive experience - we’ve learnt a bunch of lessons: more in-depth planning at the whiteboard is the way to go; premature optimisation sucks (who would’ve thought that all these books and blog posts were right all along?); figuring out some sort of a general code style that everyone in the team will use might have benefits. But ultimately, even if our lessons sound a bit generic - we worked on a solution as a team, we made one, we didn’t suck and we had fun in the process. I think that’s all that really matters.

If you’d like to see our 1,030th place winning quick and dirty code - sure thing. If, instead, you’d like to see the leaderboard - it’s here.