I've heard that during Noam Shazeer's Google interview, he was asked how to implement a spelling corrector. He described a scheme for statistically verifying queries against logs of what other users have typed. The interviewer (Paul Buchheit IIRC) quickly realized that his solution was better than what Google was using at the time. Noam was hired and asked to implement his interview question in production, and the resulting algorithms form the basis of the spell corrector that's used on Google today (though I hear the code was completely rewritten a few years ago).
Always better to ask unsolved problems with than solved problems in an interview. I wish Google still interviewed this way, instead of toy textbook homework problems.
