A friend and co-worker of mine (one of the best and brightest I've worked with) recently left our company to go work for Microsoft. Having gone through the Microsoft interview process myself (hilariously unprepared, to the enjoyment of my interviewer), I wondered what he had done to get ready for the process. He recommended one book - Cracking the Coding Interview - which he said had been recommended to him as the bible for preparation.
Interested in what his holy grail had to offer, I picked up a copy. In the first couple of pages there is a chart that lists a bunch of CS staples (linked lists, trees, hash tables, stacks, queues, etc). After listing these concepts out (which every good programmer should know), it then goes on to say
These are concepts you have to understand and be able to implement.
Now, being a couple of years out of college, I realized that I think I have a handle on these data structures, I haven't implemented any of them in code in a LONG while. And I'm sure I haven't implemented them all.