Ke Colin Zheng

I am always a big fan of puzzles. And the fact that I’m graduating and hunting for jobs gives me the best reason/motivation for cracking them. 

I was checking the Facebook Puzzles today. Facebook engineers have done a great job motivating their puzzles. Well, for someone with a computer science background, some of their puzzles are clearly classical CS problems. 

“It’s A Small World” problem has another name in CS: the k-nearest neighbor problem. Instead of checking with every datapoint, the solution to the problem could be accelerated by limiting the search to certain regions only, which can be achieved with KD-tree. ANN(approximate nearest neighbor) is a good example of such approaches. 

“User Bin Crash” problem is a classical dynamic programing problem. Once you follow the DP approach to nail down the metric, the break-down and the initial value, it’s a shoe-in DP problem. 🙂

Now that I have done the “snacks”, I’ll start thinking about the harder ones…

btw: I’m not providing any solutions to the puzzles, just my 2 cents on how to crack them. 🙂

This entry was posted on Wednesday, October 22nd, 2008 at 9:12 pm and is filed under Technology. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.