Just as the parent post said: Interviews are hard because there is extremely low correlation between what is asked in Interviews and actual job work. I firmly believe the system of asking stupid algorithmic trivia is hackable and should be hacked because it is a broken rotten system that keeps incredibly amazing hackers out. There has been a ton of stuff said about interviews so I will keep this brief:
1. Get a github account, publish code, keep a social media profile etc. At the very least, this gets you interview calls.
2. People are not that creative with tech questions. Even Google (at least these days) asks you questions that come out of a textbook. So go through one, say like Skiena's Algorithm Design Manual and solve all the problems on a white board. This sucks a ton because when I sketch out code for a project, I never go do it on a whiteboard. The trick is to get to the stage where you can mentally compose the main blocks of the problem in your head and then writing down the answer on the whiteboard. This means that when you hit the whiteboard with the engineer staring at you from back, you know pretty much what way you want to go at the problem.
2.1. Statistically speaking of the countless interviews I have done, I think a large proportion of questions have been on trees, graphs and dynamic programming. I feel like this is because "some people" think that these are exotic enough that solving these problems have some correlation with smartness. Again, solve a few problems from any textbook on these or maybe go through the TopCoder tutorials on the matter and they start getting as easy as a day to day programming problem.
3. Accept the fact that people are paranoid about false positives and don't really care about false negatives. Sometimes if you have a bad day, it is not you.
4. Someone mentioned this before but interview more. Talk to people you like, you hate and people whom you have no intention of working with. This will help you get over your insecurities and make you realize that interviews are just a game: You will get more confident, and believe me, that helps. (This is just like dating, the more you do of it the more you get better ;-)
4.1 Organize your interviews so that your dream bets are towards the end of your process by which time you will have done so many problems, attended so many behavioral interviews, talked to so many people that you will be absolutely amazing!