I found Facebook's puzzle page the other day. While it has some very meaty challenges, it also has a couple of trivial ones. These easy puzzles are there to allow you to make sure you can submit solutions (I'm not consistently getting mine to run but I'm hopeful that turning off "Always send Windows-friendly attachments" in OSX Mail will do the trick).
One easy puzzle is called Hoppity. Essential you count up from 1 to a specified number and follow these rules
- For integers that are evenly divisible by three, output the exact string Hoppity, followed by a newline.
- For integers that are evenly divisible by five, output the exact string Hophop, followed by a newline.
- For integers that are evenly divisble by both three and five, do not do any of the above, but instead output the exact string Hop, followed by a newline.
This very simple program is typically written with a few if then else's, though you could also simulate a bitmask and use a case statement:
As soon as I'd written it I started wondering: can I optimize this? I mean, this is Facebook we're talking about. Endless scale. So if they offered a Hoppity function on the main page, you bet they'd have to make it run fast! :-)
Looking at this program it's clear that the output should repeat every 15 counts. Here's a Mathematica plot to illustrate this where I've replaced Hoppity, Hophop, and Hop with 1, 2, and 3 respectively.
So if you're ever interviewing at Facebook and you're given this problem (which would be surprising, I agree), you can offer this optimization to make sure the Hoppity feature doesn't take down their servers when they release it to all their members :-)
Pre-computing is always useful!