Here are useful things to know . . .

• An algorithm to shuffle a deck of cards in place–without reading the description, can you create the algorithm?
• How to traverse an in-order binary tree
• Sorting, both in trees and linked lists
• How to color a non-planar graph such that no neighbors have identical colors (similar to coloring states on a U.S. map)
• Database schema design, especially in regard to how 3NF isn’t always the best way to create your model
• Database query design, and how the schema impacts the query
• The differences between a B-tree, B+-tree, AVL tree, and Red-Black tree
• Linked lists, doubly-linked lists, arrays, hashes and block allocated memory, hash table and hash map internals, tree maps, sets, priority queues, etc.
• How to cache data to accomodate for both most recent use order and access frequency
• Java, JDBC, J2EE, etc., very, very well

For some of this, I recommend a basic CS book, such as Loudon’s Mastering Algorithms with C (O’Reilly, seahorse book). Commit it to memory. Or at least learn the stuff in there. For the rest, I recommend three or four years or real world, intensive development, both in work and on significant home-based projects.