I also want to add my 2 cents on that. I am terrible at white-board/ phone interviews but recently I think I was able to crack at it, and here are my thoughts about it:

- go to the root of the problem, run some examples by hand and try to think as a computer. e.g., I was at apple interview and there was this trick question that could be solved using a modified version of binary search. When I ran some example I kept asking myself "if I know that this element in the middle of the matrix is smaller (or larger) than X, what does that mean?"

- be very comfortable about big O notation. If necessary, be ready to present some formula.

- show that you can do the brute force solution. Sometimes the brute force solution seems very stupid (e.g., enumerate all possible subsets and find the best one), but you need to say it!

- most of all, be confident, but not arrogant. It is not the end of the world to not know something, but it is important to show what you do know!