Contact
Subscribe

Facebook Puzzles

Apr 9, 2010
Blog

Hey, it’s been a while since I posted last.  After getting certified, I felt like I needed to push my programming skill further.  That’s where the Facebook Engineering Puzzles came into play.  I completed the first two training ones last August ("Hoppity Hop!" and "Meep meep!").  I also worked on the first easy puzzle, "Liar, Liar," but was unsuccessful in optimizing the solution to meet the requirements of the Puzzle Bot.  Finally, in March I had an epiphany and realized that I was going about the puzzle all wrong.  In less than a day I solved "Liar, Liar" in PHP with 3998.623ms as my longest test case.  After that, I solved "Date Battle" in 142.191ms and "Breathalyzer" in 19167.797ms. 

Finally, I spent an entire week working on "It’s a Small World" with no success.  I did everything I could. Without giving too much away, I created a balanced kd-tree and used a kNN search but it still ended up being WAY to slow.  I’ve optimized it into the ground, everything is running as fast as PHP can get away with.  Even after code profiling, I found all of my time is spent calculating SQRT (using BCMath) and I can’t figure a way to speed that up (stupid 20 decimal places).

So I’ve taken a break, hoping for that moment of enlightenment again.

5 Comments
Tags ,

5 Comments

  1. Colin  •  May 1, 2010 @1:51 am

    Hey – just finished smallworld too. Not sure if you got this one through yet or not, but you don’t actually need SQRT. Just leave all distances as sum of the squares, since all you care about is which points are closer, not the real distances.

  2. St. John  •  May 1, 2010 @9:40 am

    Hmm. Well my implementation is using KD-Trees and to perform the KNN search I need to know the exact distance from various axises. I feel like I would need SQRT to get that number. Unless I’m looking at this all wrong. Did you use something different?

  3. Alexey  •  Aug 21, 2010 @3:17 pm

    Actually you don’t need SQRT – you need not exact distance, but nearest (it doesn’t matter if all just without SQRT calculation ;)

  4. Walter Mundt  •  Oct 22, 2010 @4:30 pm

    You don’t need exact distances, per se. You need to be able to COMPARE distances precisely. Since distance1 < distance2 if and only if distance1^2 < distance2^2, you can work entirely in squared distances. However, note that this particular puzzle is quite hard to get right in interpreted languages; the performance constraints are much less binding if you solve it in C++ or Java.

    Also, I hope nobody wanting to solve smallworld finds this page; knowing which algorithm to use is the biggest part of every puzzle.

  5. Walter Mundt  •  Oct 22, 2010 @4:32 pm

    (can’t edit): Also, if you are comparing distance to an axis in 2D, you can just do the absolute difference on the opposite axis, no squaring or square-rooting needed.

Leave a Reply

Allowed tags: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>



  • Donate

    If my work has helped you and you want to return the favor, you could purchase something for me from my Amazon Wish List or send me a donation via PayPal.

  • License

    Unless otherwise noted, all source code and compiled files published on this website are released under the terms of the GNU Lesser General Public License.