I've quite enjoyed the two CodeSprints that I've done so far. The questions have been challenging, but interesting and fun. During the first CodeSprint, I had a lot of trouble with my answers being algorithmically correct, but too slow to complete in the allotted time. Here are three things I've learned that have helped me reduce timeouts this time around:
- Eliminate unnecessary looping or recursion. You almost always can't brute force the solution (if that's not what the problem calls for), or you will time out. This is by far the biggest thing. If you can't figure out how to get rid of looping, take a step back, maybe go work on another problem, and see if you can think of a different algorithm to solve it. This is the most transferrable to the real world of my three things. You really can't afford those extra CPU cycles.
- Print your answer once. IO is slow. If you're calling a print function several thousand times (or more), that can really take its toll over the course of the program. Instead, store your answers and just print them out at the end. This lesson is also transferrable to the real world, especially if you're doing web development; DOM manipulation is slow, so you should try to make big changes all at once rather than making a bunch of small changes.
- Cache recursive computations. Some of the problems are just begging to be solved by recursion over a small data set (at least compared to the memory they allow you to use). That said, if you try to just have your program execute the computation each time, it will not be fast enough. For CodeSprint, it is almost always worth it to make the memory/cpu time tradeoff, and cache the computations you've already done. In the real world, where there may not be as much repetition among the computations, or if memory is at more of a premium, it may not be as efficient to cache things.
I hope these help! Good luck with your last ~13.5 hours!
(A note on languages: I have noticed that for some slow algorithms, implementing it in a different language (say, going from Ruby to C) did allow more test cases to pass. However, I am very confident that InterviewStreet picked the language-specific timeouts so that all the problems can be solved in any language, if you have the fastest algorithm.)