Not difficult, per se, but unexpected: one interviewer asked me to name several different sorting algorithms and rank them by their computational complexity. Unexpected because I've never had such a discussion with a customer, no matter how technical; the question would have been more appropriate for an engineer being hired into their kernel group but the interviewers didn't seem to know the difference.
Sigiloso
see Wikipedia, Knuth, or pretty much any intro-CS text