Skip to content

Codejam

Codejam is here again. It is a test in devising algorithms against the clock, open to all-comers world wide. It was supposedly started by Google as a way of trying to select good programmers to work for them, or at least of providing a more objective measure of candidates’ abilities than the usual interview process. For the first few years they subcontracted the process, but now they handle it in-house. The main contest is once a year. There are four rounds:

Qualification round
Round 1
Round 2
Round 3
Finals

The finals are held in a Google office, typically in a different city each time. Google pays travel expenses for the top 25 from Round 3 to attend. The other rounds are online.

The qualification round is easy. It typically lasts about 24 hours to do problems for which one would normally be allowed less than 45 mins each. This time full marks was 90 and the pass mark (for moving to Round 1) was 25. 20,595 advanced to Round 1 and another 4867 scored something (plenty more entered but either did not compete or failed to get anything right).

The top 1737 got 90
the next 2 got 84
the next 85 got 79
the next 34 got 74
the next 6 got 71
the next 572 got 66
the next 27 got 65
the next 2 got 63
the next 457 got 60
the next 6682 got 55 (including me)
the next 6 got 54
the next 33 got 50
the next 80 got 49
the next 5 got 47
the next 878 got 44
the next 2 got 43
the next 16 got 41
the next 605 got 39
the next 7 got 38
the next 681 got 36
the next 21 got 35
the next 3 got 33
the next 2 got 31
the next 73 got 30
the next 195 got 28
the next 8384 got 25
the next 3 got 22
the next 18 got 20
the next 64 got 19
the next 2 got 17
the next 1315 got 14
the next 13 got 11
the next 42 got 8
the next 3410 got 6

There are usually 3 or 4 problems. Each has a page or so of description, always precise, but often not particularly easy to follow. In most cases you are then given two datasets, a small and a large. The idea is that you write your program (in more or less any computer language), then download the small dataset, run your program on it and submit the output to be marked (the downloading, running and submission must be completed in 4 mins). You then get either nil or full marks. If you get nil, you can keep trying (each time with a different dataset).

You then do the same with the large dataset, except that this time (A) you only get one shot, (B) you get longer to submit (9 mins? I cannot remember), and (C) it is not marked until after the contest is over. For each submission you have to submit your code as well as your output. In principle, they can check your code as well as your output, although in practice that only seems to happen in the event of suspected cheating or maybe in the final.

Any correct algorithm usually works for the small dataset, but for the large dataset, the algorithm usually has to be reasonably efficient. Sometimes code which works fine for the small dataset is too slow for the large one.

Google expected the last question to be the hardest, but actually qu 3 was the hardest. I wasted 3 hours failing to solve it. Maybe I would have solved it if I had stuck at it for another hour or so (and I had another 6 hours before the deadline), but I had to go off somewhere else. The bunching on 55 suggests I was not alone.

From Round 1 onwards, there is time pressure. But Round 1 is held at three different times of day to suit those in different time zones. Moreover, Round 1A, 1B and 1C are held on different days, so anyone prepared to put up with unsocial hours effectively has three shots at getting into Round 2. They happen at weekly intervals, starting next Saturday. Last year I got through Round 1, but with depressingly low marks and did not even attempt Round 2. So this year my goal is to reach Round 3. We will see. I certainly got off to a bad start.

Post a Comment

Your email is never published nor shared. Required fields are marked *