What is the best way to prepare for these sorts of interviews? I've been following the steps Steve Yegge recommends: http://steve-yegge.blogspot.com/2008/03/get-that-job-at-google.html and have been reviewing my college notes on data structures, algorithms, and theory. I've also worked my way through "The Algorithm Design Manual" which I recommend.

I'm not sure this preparation has been helpful for these sorts of questions. For example I recently had an interview about designing a scalable system and my solution involved thread pools, sharding, producer/consumer queues, and non-blocking I/O. I have some general understanding of those topics, but no deep knowledge. I was thinking of reviewing my notes from my distributed systems class, but it mainly covered topics like distributed mutual exclusion, and the byzantine generals problem.

Any ideas on how to better prepare?

In case you are wondering, I graduated with a Bachelors in CS a few years ago.

Thanks!