Some questions for you:
What are your weak areas/blind spots?
What kind of programming do you do?
Where are you located?
>>What are your weak areas/blind spots?
I do trees, hash tables fairly well. When it comes to arrays, I usually do well when brute force takes O(N) but optimal solution is O(logN). I do badly when brute force is O(N2) but optimal is O(N). Even in interview, I know I should look for O(N) solution, I do get the general solution right but I fail to get the specifics wrong. For example, most O(N2) solutions include two for loops. You tend to redo a lot of work if you run two loops. But figuring out a subset of indices which do not need to be computed, one must come up with a O(N) solution. This somehow, I fail, consistently.
Graphs are a hit or miss. I do dynamic programming well most of the times.
>>What kind of programming do you do?
I work on a major mail provider's middleware team. I write Java web services code in a distributed environment. My service talks to storage system, notification system etc. Most of the work involves designing and implementing algos for rate limiting, for fetching and caching data from storage system etc. Work also involves scaling to involve increased load etc.Day to day work is all Java. Write REST API code +unit tests + integration tests and then deploy. Worked on compiler frontends before(C/C++).
>>Where are you located? SF Bay area. But I am looking coach from anywhere in the world! Email in Profile.
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.)