Facebook Puzzles Rock!

If you want some really good programming challenges go to the facebook puzzles page. These are really neat because you can submit the answer and their email robot will automatically tell you if it is good. So far I've only solved usrbincrash and smallworld. A very evil person also described the gattaca puzzle to me and I've been trying to figure out how to solve it ever since.

From what I've seen these puzzles the very nice characteristic that it is rather easy to come up with a solution. However, that solution will run in exponential time and, thus, will not be accepted by the robot. The solutions they are looking for generally run in quadratic time. Finding these solutions is much, much harder.

If you are confronted with questions like these in an interview, the best strategy is to start by solving them using the obvious-but-slow method. Then, once that works, start to think about how to solve them faster. Sometimes this requires completely re-writing your algorithm, often you will need an aha! moment (wish there was a way to work up to those!). Other times it seems one can gradually get to the solution by adding small improvements.