there are definitely questions where you have to think of the right general algorithm and datastructure very quickly, and then spend your time refining it for the details of the problem, but i'd argue that that's not in the same "aha!" class as actual riddles.
Well, knowing the O performance of some sorting algorithms, is not what IMHO can be defined as "we want to know how you think". Or implement, in a very short amount of time, tree algorithms.
I mean, they are not totally 'aha!' things, but they are the kind of things that you could nail one day, and be completely stuck another. And quite irrelevant to your work (as is highly unlikely that you'll ever implement it)
On the other hand, questions about how and why to use this data structure or another, are totally relevant and interesting. And shows way more that you have been using them and know what are the differences.
Again, is just my opinion (and Google can do their interview process as they like, they are obviously doing fine in getting a great team!), but my impression is that gives a lot to chance or inspiration in some interviews, and giving their process, one mistake could be all you need to be out.
