Facebook Engineering Puzzles

A colleague of mine pointed me to the facebook engineering puzzles page yesterday. And I tried to give a shot to first one (the liar-liar puzzle). It took a good number of my hours today but it was fun.

And, I succeeded in first submission itself :). Here is the mail from facebook that I received:

from Facebook PuzzleBot
to g.himanshu@gmail.com
date Sat, Sep 11, 2010 at 4:45 PM
subject liarliar evaluation results
mailed-by facebook.com


Dear submitter,

Thank you for your submission of a puzzle solution to Facebook! After running your solution to liarliar (received on September 11, 2010, 12:37 am), I have determined it to be correct. Your solution ran for 2508.850 ms on its longest test case. If you have not already, try installing the official Facebook Puzzles application from http://apps.facebook.com/facebookpuzzles/ and publish a story about your solution! To publish, just go to http://apps.facebook.com/facebookpuzzles/mypuzzles.php and click on the publish link.

If you are applying for a position within Facebook, the puzzle difficulty solved will be taken into account with regards to how much time you had available to solve it (remember that Hors D'oeuvres are only tests for your benefit). I have taken the liberty of alerting our recruiting team about your success. Best of luck!

Sincerely,
-The puzzle robot

sorry, but no open sourced code this time for obvious reason. :P

[Update#1] I got the 2nd one(breathalyzer) accepted also. It took multiple submissions though :( and hence more time.

[Update(May 02 - 2011)] After a long time, yesterday I worked on Gattaca puzzle and nailed it. Regarding the timing, bot says, it took 4132.647 ms on the longest test case. My first solution was O(2^n) as I thought this was NP-hard problem which got rejected. I then followed the discussions on it and realized that this was *not* NP-hard and managed to work out the code that runs in O(n^2) in the worst case.

[Update(May 08 - 2011)] dancebattle is finished too. My first submission was accepted but longest test case time was 1108.22 ms. Then I optimized it a little bit, resubmitted and then bot says, it took 263.009 ms on it's longest test case :).

[Update(May 09 - 2011)] smallworld is done. Note that trivial O(n^2) solution does not succeed. Bot says, my solution took 9928.117 ms on its longest test case.

[Update(May 16 - 2011)] Today I received acceptance email for my solution to fridgemadness (Refrigerator Madness). Hardest part in this puzzle is to really understand the problem :). Regarding the timing, puzzle bot says, it took 362.562 ms on its longest test case.