There are a few things I have to add, but they are relatively minor:
- Apply test taking techniques: in particular, if you suspect that your answer is too complex to fit into the white board, chances are, your entire approach is wrong. It'll take a very cruel interviewer to ask a coding question that cannot be solved in the space provided. And as Steve says, come prepared to write code! If you were hiring a juggler, you would expect a demonstration of his juggling. No excuses!
- Do not panic if you bomb one interview. I've seen folks do badly on one interview and then fall apart completely when if they pulled themselves together and stayed calm they could have done much better. Panic doesn't help you solve problems.
- There are really only a limited number of data structures in widespread use: hash-tables, linked lists, binary trees (and balanced versions of such, including skip lists and treaps), heaps, on-disk data structures such as B-trees, and arrays. Learn them all, and learn to apply all of them. If one data structure doesn't fit, try another one. An interesting phenomenon I've seen is that a lot of candidates spontaneously invent tries in an interview, but few even know what it's called. In practice, tries are rarely used.
- Be honest. If you don't know something, say so. Pretending you know something is a good way to ensure that you get dinged for it! One of my Google interviewers asked me to write some SQL, and I replied that I didn't know any. It didn't hurt me, as she switched to a different question altogether. Any attempt by me to brazen it through, however, would have been cause for concern.
- If you're sick, reschedule for your interview, and reschedule it far enough later that you will be well by the time you show up. An interview that you care about should not be done with your brain at 50% or even 75% capacity. I know any number of people who tried to tough through their interviews sick, and it showed in their performance.
I will close with an amusing interview story: When I applied for a job with Pure Software as a fresh graduate, my interview went like this: the CEO, Reed Hastings (they had only about 10 employees at the time) asked me to meet him at the Software Development Conference. When I arrived there, however, I discovered that contrary to what he had told me, there was no badge to get into the conference for me waiting at the registration. So I hustled a bit and talked the conference registration desk into letting me in as a Pure Software Employee. When I got to Pure's booth, I found Reed and his first interview question was: "How much money would you like to get paid?" It turned out that he had deliberately not provided a badge for me, and had decided that if I could sneak my way into the conference, I was a worthy hire.