I wouldn't expect them to write the code for it, maybe some pseudo code, but a candidate should be able to talk through the problem and come to a solution for this in 10-15 minutes. It also depends on what kind of work you expect them to do. If you are building iPhone apps or doing plain old web dev, you probably don't need candidates who can solve this in <10 minutes.
I'm not surprised by your 90% no-solve stat. Candidates I interview who put Java/C# on their resumes can barely "write a function that returns true if the first letter of a string parameter is capitalized". At least half flat out can't do it.
I'm not surprised by your 90% no-solve stat. Candidates I interview who put Java/C# on their resumes can barely "write a function that returns true if the first letter of a string parameter is capitalized". At least half flat out can't do it.