Facebook Engineering Puzzles page. I had come across some of the older puzzles before - I vaguely remember one about movie theater seating and another about escaping from velociraptors - but just kind of ignored them. This time around, I decided to give the Liar, Liar puzzle (liarliar) a try (note: Facebook took down the original puzzle so I'm linking to another site with the description). After I scribbled some stuff on paper, I had a very satisfying "a-ha" moment when I recognized the puzzle as a 2-color graph coloring problem. After a bit of review on graph coloring and bipartite graphs, I wrote up a solution, submitted it, and successfully solved the puzzle. After that, I was hooked.
So for the next few weeks, I went on a puzzle binge, solving puzzles in between watching episodes of Lost on Netflix (I had just gotten hooked on the show as well; the show is puzzling in its own way). The puzzles were extremely fun and quite educational. I was able to brush up on some graph theory and dynamic programming, and learned about cool new things like kd-trees.
After I solved a bunch of the puzzles, I was at a nice stopping point and had the ambitious goal of writing up the solutions and putting together some kind of programming puzzle book. I didn't get too far, but I do have a decent amount of content. I've decided to go ahead and just post the various "chapters" in the next few weeks and share them with fellow puzzle lovers. Note that for some puzzles I tried to reword the problem to give it a different flavor; nevertheless, the solutions are pretty much the same.
Wednesday, September 29, 2010
Monday, September 27, 2010
Founders At Work for less than a can of pickled radish, which was a pretty sweet deal. I had heard of and read about the book from various sources, but never added it to my reading list. I'm now more than half way through the book, and I must say it is an enjoyable and worthy read. I've definitely gotten to the point where I can spot some patterns that seem to be common amongst successful start-up founders. At least, patterns which were not as apparent to me before.