Maybe it's just your misfortune for being in the Bay Area, but...

Google exists. Knuth's TAOCP exists. In such a world, why do interviewers expect you to be able (under pressure at a whiteboard) to come up with the optimal algorithm? How much of the work that you do actually depends on finding O(N) rather than O(N2) solutions?

I think that you are unfortunate in the companies you are interviewing with, not necessarily in your interview skills or knowledge.

Can you fix it by studying? Maybe, with a lot of effort. It might be as easy to find companies that interview with a different approach, and interview there. (Note: Not easy, but as easy.)