Saturday, March 2, 2013

Google Code Jam Prep

  I love the Code Jam... I've done it every year since I first discovered it in grad school.  As a competitive person, I was always looking for an edge that could improve my scores.  With Google Code Jam right around the corner, I thought I'd share some of the tips I've picked up over the last several years.  Feel free to include them into your contest.

  • Optimize your work space for efficiency.
With the exception of the first round, you'll have a really limited time frame to work with, and you want to avoid as many disturbances as possible.  I like to close all the miscellaneous windows I generally keep open, save for some music and maybe a quick window for Google searches, in addition to my IDE and a window with the problem sets.  I have some water handy, and anything that could distract me during the contest hours conveniently taken care of.
  • Write your boilerplate before the contest.
All Google problems look exactly the same from an IO standpoint. You read some data from a file, perhaps multiple lines per problem.  You parse the data into their respective data types, do some real work on the data, and then output to a file a line starting with a leading number, followed by whatever answer you are going to give.  Typically, they have three problems for you to work on, so I have a project set up with all three problem classes already set up to do some generic parsing of a simple problem, and generic output of whatever you are going to solve.  With three hours available for critical thinking, these presious minutes can be the difference between a working solution and an almost finished solution.
  • Have a resource file easily available to paste in the free test data they give you
Google problems all give you some example inputs and outputs as a starting point for what your program should be able to do.  In the boilerplate code, I like having an empty text file pre-wired to be parsed as the input file of choice, which I can just paste the examples in and run against my program.  I also have a pre-wired text file for the output, already open, which automatically refreshes when I run my program.  It gives me instant feedback as I am writing my algorithms.
  • Read all the problems before you start.
This is more of a generic test taking strategy, but it applies well here.  Google assigns different points to different problems.  Typically in the first round, a score large enough to get you on to the next round doesn't have to be a perfect score... but it also typically isn't the score of the easiest problem either.  Also, I feel that reading all the problems before starting gives your mind a chance to process a bit before you jump into coding.
  • Have a plan of attack
Unless there is a very obvious optimal type answer, you'll need to think about how you are going to attack a problem before you jump into it.  The big points require optimized algorithms.  O(n^2) is the quickest way to not having a working answer.  Diagram out on a piece of paper the implications of what you want to achieve.
  • Know where to find your file I/O.
Once you download an input file for processing, you typically have around 5 minutes to upload your program's results.  The more time you are fumbling around looking for where your input file downloaded to, or wiring up your program to use it... and again finding the file your program outputs for upload, the less time your program can be crunching on the answer.  Sometimes, sub-optimal algorithms can still pass the large dataset... but usually with very little time to spare.  Seconds count here, and having done a few practice runs against Google's practice problems will help iron out the wrinkles.
  • Fuzzy test your big data sets before submitting.
This will be a new one for me this year... but it is something that I tried in the Facebook Hacker Cup.  Before attempting the large dataset, you need to know the performance pain points of your algorithm.  The best solution I've come up with is to Fuzzy Test your algorithm against the boundaries supplied in the question.  Making sure your fuzzy testing module tries various combinations on the boundaries especially, because this is where the tricks occur.


Any additional suggestions you may have about how to improve your Google Code Jam experience, I'd love to hear.  Good luck in the 2013 Code Jam!

No comments:

Post a Comment