[kragen]

> The advanced answers to this question require spending a lot of time understanding string processing.

No, the advanced answers are a simple application of dynamic programming. If you've never heard of dynamic programming before, you're unlikely to invent it in response to an interview question, of course; but if you have heard of it, it might occur to you to try it on this problem.

(Actually, if you've heard of memoization but not dynamic programming, you might invent dynamic programming in response to this question.)

I think this is at the opposite end of the spectrum from your CSS example. Dynamic programming has nothing to do with string processing or with any other particular domain. There's a list of 29 significant algorithms that apply it at http://en.wikipedia.org/wiki/Dynamic_programming#Algorithms_.... It might qualify as "deep knowledge", but it's not deep domain knowledge; it's the kind of deep knowledge that would make you want to hire someone from a different domain.

[onemoreact]

Counterpoint: @Retric congratulations, you’ve reinvented dynamic programming with your O(n) solution That’d be a perfect solution.

And yes, I had zero idea what memorization or dynamic programming meant in that context. After looking it up on wikipedia it seems to mean caching intermediate steps to avoid recalculating them which seems obvious enough.