By Bartholomew Furrow, Software Engineer
In Mountain View and in offices around the world, Googlers are spending their 20% time to get ready for Google Code Jam 2011, preparing algorithmic problems for the 10,000 or more contestants who we expect to compete in our Qualification Round this Friday.
A good Code Jam problem has a story to ground it in some version of reality: soccer, ninja and messages from alien cultures have all served admirably. Cushioned by the story, the core of a Code Jam problem is an algorithmic puzzle whose solution needs anything from a few lines of code to a deep understanding of flow algorithms or number theory.
 |
| The ninja in the middle is solidly grounded in reality. |
Anyone at Google can create Code Jam problems, which means that our methods for inventing them vary wildly. One author might come across a real-life situation, think about what algorithm would solve it, and base a problem on that; another author might think about how to make a problem out of a video game. Sometimes a problem author will start with an algorithm and concoct a problem that it solves. We also really seem to like inventing weird situations on chess boards.
With the story and the problem chosen, our work is only partly done. The problem has to be stated in such a way that it will be clear, even for an audience from 125 countries. At least three engineers work on each problem’s statement: that group includes at least one native English speaker to make sure the grammar is all correct, and at least one non-native English speaker to make sure the language is clear enough.
The toughest part about setting up a problem like this is verifying that contestants got it right. In Code Jam, we do that by providing contestants with an input file full of test data. They send back their program’s output, which should be the answer to the input file’s question. The hard part is deciding what goes in that input file: we need edge cases, plenty of average cases, and a good number of cases that make sure the contestant’s code is fast enough. To create all of those, we generate some cases by hand and others pseudo-randomly. We’ve been known to generate a test case or two out of ASCII art, or as a creative-writing exercise.
Finally, we solve the problems ourselves. We require at least three solutions made by different engineers, and sometimes we have those engineers write solutions that we know to be wrong – just to make sure our test data catches them out.
The end result of this process is the kind of problem we’re proud to ask our contestants to solve. In 2011 more than any other year, we’re excited about the creativity of our colleagues and the problems we’re planning to pose. We hope you’ll enjoy the problems from the other side – and if you’re a great software engineer, maybe come help us write them in 2012.
You can register for Google Code Jam 2011 at http://code.google.com/codejam, and you’ll see the first problems of the year in the Qualification Round this Friday, May 6, starting at 23:00 UTC. For even more details about how we get problems ready for Code Jam, you can read our official problem-preparation guide.
Bartholomew Furrow spends 80% of his time at Google finding ways to eliminate bad search ads, and the rest on Code Jam. Programming contests introduced him to Computer Science, to Google, and to his wife.
Posted by Scott Knaster, Editor
No comments:
Post a Comment