Thursday, December 30, 2010

What Rejection Means For You (Hint: Nothing)

With the Great Silicon Valley Talent War of 2010 (infographic) raging on between Google and Facebook, many engineers are undoubtedly dusting off their resumes and considering taking a stab at getting in on a piece of the action. Some may consider the escalating efforts at getting engineering talent to be a bubble, but there's no reason why talented engineers shouldn't get in on a piece of the action while the going is hot. Google's reputation as an employer is nothing short of legendary, as there have been hundreds of articles written about the Google work culture, benefits and perks, and the hiring process. If Facebook's trajectory remains on course, it will likely join Google at the top of the totem pole of coveted Silicon Valley employers.

Thursday, December 23, 2010

Hacking The Padlock

While I was at the gym a few weeks ago, a couple pretty silly thoughts came to me that I thought were interesting enough (at least to me) to jot down. Most gyms provide lockers for personal storage, sans the actual padlocks. As I turned and spun my trusty old Master Lock combination padlock, I realized that these padlocks are actually 97.5% less secure than they're made out to be.

From what I can tell, the common padlocks used by most people are more or less the same. These Master Lock-style combination locks were also used for the hallway lockers I had during grade school. The locks have a combination of 3 numbers, and the sequence of actions required to unlock the lock are: spin the lock clockwise past the first number 3 times, spin the lock counter-clockwise past the second number 2 times, and finally spin the lock clockwise directly to the final number.

Sunday, October 24, 2010

Doublets - A Word Puzzle Game

Doublets is a word puzzle game invented by Lewis Carroll where the objective is to turn one dictionary word into another by changing one letter at a time. At each step, one letter may be changed, and the resulting word must be a valid dictionary word.

For example, to turn "milk" into "wine", "milk" changes into "mink", "mink" changes into "mine", and "mine" changes into "wine". Each intermediate word is a valid dictionary word. If we are given two arbitrary words, how do we determine the minimal number of intermediate steps needed to transform one word into the other?

Monday, October 18, 2010

Currency Arbitrage In 99 Lines of Ruby

A few months ago, I had the crazy idea of writing some code to automatically detect currency arbitrage given current foreign exchange rates. The brilliant plan was to (1) develop this evil-genius program (2) unleash it upon the market (3) and profit. Okay, not really, but the thought did cross my mind when for some unknown reason I was reminiscing about homework problems from my introductory data structures class. One of the problems involved looking for currency arbitrage in a graph of exchange rates, albeit it was a simplified exercise in depth-first search. The actual problem involves looking for a sequence of currency exchanges (a path in the graph) that starts at a given currency and ends up with more units of that currency than we started with. This problem is straight out of CLRS, and there are various solutions to it floating around on the web. Nevertheless, I decided to give it a go and see if arbitrage situations can really be found using real-world exchange rates.

Wednesday, October 13, 2010

Facebook Puzzles - User Bin Crash

The User Bin Crash puzzle (usrbincrash) is a quick and fun puzzle to solve (note: Facebook took down the original puzzle so I'm linking to another site with the description). After reading the problem statement, it should be easily recognizable as an inverted instance of the knapsack problem. The fact that there is a weight requirement is a dead giveaway. Unlike a burglar trying to maximize the value of the stolen goods in his knapsack, you're trying to minimize the cost of the goods being thrown out of the plane. Although the knapsack problem is NP-complete, it can be solved in a straightforward manner using dynamic programming.

Of course, it would be no fun to simply reveal the solution. Instead, I've decided to formulate the problem in parable form with a tropical theme. Hopefully, it'll help provide a more intuitive understanding of the knapsack problem. If you've been following along with my posts about various Facebook Puzzles and are interested in trying some of them out yourself, getting a good handle on dynamic programming will prove to be quite useful.

Saturday, October 9, 2010

Facebook Puzzles - Dance Battle

As I set out to solve the Dance Battle Facebook Engineering Puzzle (dancebattle), I realized that it was really just some sort of game (note: Facebook took down the original puzzle so I'm linking to another site with the description). It had alternating turns, repeatable moves, moves represented by non-negative integers, and was zero-sum. After some digging around, I realized that it was just a thinly-veiled version of a game of dominoes.

Naturally, it seemed fitting to present the solution to the puzzle in the form of the game it was modeled after. I had never played dominoes before, but I knew what the basic game pieces looked like since dominoes sets are among some of the more popular swag that certain companies like to give away at college career fairs. Nonetheless, I exercised due diligence and did some research on the game. Thus, I present to you Dance Battle, played out in the form of dominoes.

Wednesday, October 6, 2010

The Lego Minifigure Collector's Problem

I recently attended BrickCon and had the pleasure of listening to a very entertaining talk about Lego Minifigures. For those not in the know, Lego recently released a set of Lego Collectible Minifigures. Apparently, the collectible minifigures were made available for only a limited time, and come in "mystery" packages that don't show the minifigures inside, just like a pack of baseball cards.

In the Lego lovers circuit, these things are currently selling like hotcakes. The speaker at BrickCon likened the minifigures hysteria to a virus in that the collectible minifigures are like "small infectious agents." Lego fans are doing everything they can in order to collect every figure in a series.

Saturday, October 2, 2010

Facebook Puzzles - Gattaca

Continuing with my Facebook Engineering Puzzles series, here's the writeup for Gattaca (gattaca) (note: Facebook took down the original puzzle so I'm linking to another site with the description). The original problem statement is interesting in that it has a computational biology twist, but it's really a weighted interval scheduling problem in disguise. This one took me a while to recognize, even though I was barking up the right tree by looking for an optimal substructure that would lend to a dynamic programming solution. Ultimately, the key to the problem is that the order of the gene predictions is important, and is part of the solution.

For this writeup, I reformulated the problem in a more "classic" interval scheduling manner. I think treating the DNA strand as a timeline and the gene predictions as time intervals is a good way to gain an intuitive understanding of the problem and the solution.

Wednesday, September 29, 2010

Facebook Puzzles - Liar, Liar

A few months ago, I stumbled across the 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.

Monday, September 27, 2010

Founder Patterns

A few weeks ago I ventured into the depths of Redmond in search of ingredients for making pickled pork noodle soup. There also happened to be a Goodwill store next door. After perusing the used books section, I came across a pristine copy of 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.