Like most geeks, I love puzzles. I solved Google’s infamous puzzle that started with {first 10-digit prime found in consecutive digits of e}.com. I also solved one of Facebook’s puzzles, just for fun.
Today, Jonathan sent me a link to ITA Software’s hiring puzzles. It’s sexy stuff, and Standout Jobs would have some hiring puzzles too if I could come up with something particularly demented. Jonathan suggested an intriguing roman numeral puzzle. Sadly, we both realize that many people can’t even write a simple Fizzbuzz.
Ah well, back to the ITA Software puzzle. Looking at the average length of a few numbers, I estimate there’s a good chance the 51 billionth letter either doesn’t exist, or is very close to the end. Gauss would be amused.
Even if I’m wrong, brute force is obviously out of the question. It would however be nice to start from the end and have the algo run in a fraction of the time. So here’s how I start.
units = %w{ one two three four five six seven eight nine }
tens = %w{ ten twenty thirty fourty fifty sixty seventy eighty ninety }
teens = %w{ ten eleven twelve thirteen fourteen fifteen sixteen seventeen eighteen nineteen }
def sum_string_sizes(units)
units.inject(0) {|memo, unit| memo + unit.size }
end
sum_string_sizes(units)
=> 36
sum_string_sizes(teens)
=> 70
([''] + units).inject(0) {|memo,i| memo + "twenty#{i}".size }
=> 96
'twenty'.size * 10 + sum_string_sizes(units)
=> 96
# sanity check doesn't bounce, wOOt!
sum_string_sizes(tens[1..-1]) * 10 + 8 * sum_string_sizes(units)
=> 758
So for numbers 1 to 99, I get strings of total length 864. I’m certain of my solution up to 999, but I’m not awake enough to be sure I have the rest really nailed. Either way, if there’s more than 51 billion letters, there’s still a fair chunk of work to do.
Have you solved this? If so, do you want to work for Standout Jobs? 
If not, how would you go about it?
9 comments ↓
That sum function is ugly. I posted it here for you to refactor: http://refactormycode.com/codes/9
Puzzles are nice but I’d say nothing beats a total geek test to make sure you get a decent worker. Finding a solution != working efficiently in a group.
e
Sorry, no it’s not e at all. It’s either o, r, x, or t - haha!
[…] spent most of my week-end solving the ITA puzzle, while high on codeine. As I write this, I am literally shaking from withrawal. Those pills just […]
Actually, my first answer was good just as I thought. it’s because I misunderstood the second question in the puzzle that got me wrong hte second time around.
The processing for the first answer was all mental and took much much faster than designing and coding an algorithm to do it.
Statistics!
Josh - you’re actually missing ‘d’ and ‘n’ as possibilities.
Please do not post your solutions here. if you solved the puzzle, then apply to ITA and do not disclose the solutions please. Seriously, think about the disservice you would be doing to the company. If you love puzzles, then get together and do this privately. Thanks!
Dan, I can’t even apply to ITA unless I become American.
The puzzle was solved by many others as well (my solution is posted later), yet there’s still room for improvement.
If solving those puzzles is going to be your day job, cheating would be really #$%^ stupid. You’ll be discovered as a fraud in no time!
Leave a Comment