Thursday, December 5, 2013

Decoding A Facebook Interview Question


Read on Glassdoor today about this question from Facebook, thought it'd be fun.

The question:

 A message containing letters from A-Z is being encoded to numbers using the following mapping: a -> 1, b -> 2, ... etc. How many decodings of some given number.


It seemed immediately obvious to me that this was a recursion problem. So I started there. The first attempt was almost right, but missed the oddity of zeros. After accounting for those, it was just as straightforward as expected.

Here is the code: