N independent decisions

24 Dec 2011

N independent decisions

About 5 days ago, I have an phone interview with a Twitter engineer. He asked me to:

Given a string, for example, aa-(1,2)-(4,5)-xx, generate aa-1-4-xx aa-1-5-xx aa-2-4-xx aa-2-5-xx

Now that's the n independent choices. You must either use a depth-first search or a breadth-first search.

But that's kind of boring.

This morning I've just come up with a meta-programming solution. Basically, it generates a source code with n nested loops (for n independent decisions) and run that code.

This requires only memory to hold a source code. It should run faster than a depth-first search and a breadth-first search because it's just a loop.

Now let's see my new solution:

# Given a string s statics = s.split(/\([^\)]+\)/) decisions = s.match(/\([^\)]+\)/)[1..-1].map { |unit| choices = unit[1..-2].split(",") choices } code = "" decisions.each_with_index { |choices,index| code += "[#{choices.join(',')}].each { |a#{index}|\n"; } decisions.each_with_index { |choices,index| code += 'print "' + statics[index]} + '#{a' + index +'}"'; } code += 'print "' + statics.last + '"'; decisions.each_with_index { |choices,index| code += "}\n"; } eval(code)

The code does not seem to use any large memory as breadth-first search does.

But I think nested loops need memory. It's just that we don't manage it…

An even better solution

My friend at Facebook gave me an even better solution, which is similar to BigInt implementation.

# Given a string s statics = s.split(/\([^\)]+\)/) decisions = s.match(/\([^\)]+\)/)[1..-1].map { |unit| choices = unit[1..-2].split(",") choices } counter = [] decisions.length.times { counter.push(0) } max = 1 decisions.each { |choices| max = max * choices.length } max.times { end_index = 0 while true counter[end_index] += 1 break if counter[end_index] < decisions[end_index].length counter[end_index] = 0 end_index += 1 end s = "" counter.each_with_index { |i, index| s += "#{statics[index]}#{decisions[index][i]}" } s += statics.last puts s }

That's a good one. Ok, next time, if there are n independent decisions, just use this technique.

Give it a kudos