Wednesday, February 16, 2011

Facebook Puzzles - It's A Small World

The It's A Small World Facebook Engineering Puzzle (smallworld) is probably one of the more difficult snack-level problems; it's also one of the funnest since the standard solution involves using a nifty data structure (note: Facebook took down the original puzzle so I'm linking to another site with the description). Even on first glance, it's easy to understand the objective of the puzzle. The input is a list of Cartesian coordinates on a two-dimensional plane, and the goal is to find the 3 closest points for every point in the list.

In fact, this problem is commonly found in applications we all use everyday. Be it location based mobile apps, mapping software, or recommendations systems, chances are you've experienced the need to find things that are "close to" other things, whether physically or abstractly. Let's dive a little deeper and see how it all works.