Very good illustration, I must say. I strongly disagreed with the GP's rant about knowing O-notation, but I realized he might have faced the first type of questions a lot (e.g tell me the O-complexity of X algorithm).

My experience with Amazon was actually the opposite, but I might have been lucky. All the interviewers were very friendly and started from simple questions and went on to more complex ones. Never a "do you know concept a from language Y". In fact, one of them worked with me through the solution to a pretty tricky problem, and when we were done, he actually took a picture of my solution on the whiteboard! So yeah, it was fun :)