I do have to say that as someone who sometimes conducts technical interviews, I'm not sure I would actually give this question to an interviewee, unless I was leaving him or her alone to work for a couple of hours, because of how long it would probably take to reach an answer.
So it appears they are aware of that problem. I'm of the opinion that some "non-classical" problem is probably a better indication of skill and reasoning. Work through a known problem you had at work (which the candidate is hopefully not too familiar with, otherwise abort and try another), and see how they reason out the problem, then ask for some code that might fix it.
I do have to say that as someone who sometimes conducts technical interviews, I'm not sure I would actually give this question to an interviewee, unless I was leaving him or her alone to work for a couple of hours, because of how long it would probably take to reach an answer.
So it appears they are aware of that problem. I'm of the opinion that some "non-classical" problem is probably a better indication of skill and reasoning. Work through a known problem you had at work (which the candidate is hopefully not too familiar with, otherwise abort and try another), and see how they reason out the problem, then ask for some code that might fix it.