Only recently a friend of mine narrated an interview tale. I don't exactly remember the precise question, but apparently he was asked to solve a problem in 30 mins(Two problems is what interviewer expected him to solve in an hour). One of such problem apparently he couldn't solve it in the time complexity the interviewer expected him to. Though he got some solution working in an hour.
He later on went and googled it and apparently the algorithm couldn't be solved unless you knew about Suffix Automata(http://codeforces.com/blog/entry/20861)
Long story short, these days apparently without everyday exposure competitive programming exercises(spending hours every day on sites like codeforces, SPOJ and hackerrank) there is no way you can clear interviews.
Reminds me of the Aho-Corasick string-matching algorithm.