If true, that'd make it an awesome interview question. After all, the professed goal of these kinds of questions is to see how somebody thinks and approaches programming problems. If they flop around without a clue, it's then the interviewer's job to start them on the right track. Surely any competent programmer should be able to come up with some kind of a iterative solution and then have an intelligent discussion about how it could be improved.
(I don't think it's an awesome interview question in practice though, too many people do already know how to do it.).
Now, it's entirely possible that I shouldn't work wherever you work but I think this is a terrible question to ask. The experience of 'flopping around without a clue' during an interview is both unpleasant and massively distracting. My experience so far as both interviewer and interviewee is that seeing how someone responds when freaked out is only useful if the job involves being in that state most of the time.
The only reason somebody should be flopping around with such a softball question is if they for some reason think that they're being asked to find a near-optimal way of computing square roots. The only reason the candidate would be allowed to get stuck in a dead end for a long period of time is if the interviewer doesn't know what he's doing. But I see absolutely nothing wrong with asking questions of this general type.
And again, I do not think this is a good interview question. I just think it's bad for a different reason than the original poster claimed. Which was that it's supposedly not solvable even by top engineers unless they've recently implemented the algorithm.
(I don't think it's an awesome interview question in practice though, too many people do already know how to do it.).