@Paul Jungwirth You have the numbers 123456789, in that order. Between each number, you must insert either nothing, a plus sign, or a multiplication sign, so that the resulting expression equals [2002]. Write a program that prints all solutions. (There are two.) This is a pretty tricky problem, actually, if you don't think to use recursion. I was satisfied with pseudocode, but the Perl Mongers version was to fit the whole thing into 80 characters! There's probably a more CPU-efficient way to do this, but considering how much I'm being paid and how important time-to-market is, you would probably rather that I sacrifice CPU time for developer time, as long as the code's clear enough for somebody to optimize later; I can optimize it later when the situation calls for it. In Ruby: # Represent a nonnegative integer as a fixed-length array in base 3 (little endian), # using the symbols "", "*", and "+". # # Example: # base3(0,3) # => ["", "", ""] # base3(1,3) # => ["*", "", ""] # base3(2,3) # => ["+", "", ""] # base3(3,3) # => ["", "*", ""] def base3(n, len) symbol_space = ["", "*", "+"] retval = [] len.times do retval << symbol_space[n % 3] n /= 3 end retval end # XXX - This is slow (O(3**n)). Luckily, with a string of length 9, # we only have to do 6561 iterations. s = "123456789" s = s.split("") # Split into array: ["1", "2", ..., "9"] (0..3**(s.length-1)-1).each do |n| # iterate through all possible combinations ops = base3(n, s.length-1) expr = s.zip(ops).flatten.join puts expr if eval(expr) == 2002 end # I should get extra credit for figuring out how to indent stuff on this blog. (Hint: U+00A0)

To anyone who's trying to figure out why so many interview candidates are bad, you should read this Joel on Software article (from 2005): http://www.joelonsoftware.com/items/2005/01/27.html