Decoding A Facebook Interview Question

About:

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.

Solution:

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:

	import sys
	### Some little programming puzzle I found. Apparently Facebook asked this sometime.
	###
	### 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.
	###
	### Takes an input of numeral characters.
	input = sys.argv[1]
	def howMany( string, l ):
	if not string.isdigit():
	return "error: howMany takes strings with numeral characters"
	elif l == 0: #base cases
	return 0
	elif l == 1: #base cases
	if string == "0":
	return 0
	else:
	return 1
	elif l == 2: #base cases
	if "0" in string:
	return isValid(string)
	else:
	return isValid(string)+1
	else:
	return howMany(string[0:-1], l-1)*(string[l-1] != "0")+howMany(string[0:-2], l-2)*isValid(string[-2:l]) #recursive call
	def isValid( tail ):
	if len(tail) != 2:
	print "error: isValid takes strings of length 2 with numeral characters"
	elif int(tail) > 26 or tail[0] == "0":
	return 0
	else:
	return 1
	def decode( message ):
	if "00" in message: #any 00 invalidates the string
	return 0
	else:
	return howMany(message, len(message))
	print decode(input)

view raw numeralDecoderPuzzle hosted with ❤ by GitHub