Steve Yegge wrote a loooong post with tips for finding a job at Google.
He gave all sort of tips, most of them self-explainatory (you should know about Hashtables, Algorithms etc).
But there was one golden advice:
Don't let the Interview Anti-Loop get you down.
But what is the Interview Anti-Loop?
Every single employee E at any company has at least one "Interview Anti-Loop": a set of other employees S who would not hire E.
The solution is simple:
"The bottom line is, if you go to an interview at any software company, you should plan for the contingency that you might get genuinely unlucky, and wind up with one or more people from your Interview Anti-Loop on your interview loop. If this happens, you will struggle, then be told that you were not a fit at this time, and then you will feel bad. Just as long as you don't feel meta-bad, everything is OK. You should feel good that you feel bad after this happens, because hey, it means you're human.
And then you should wait 6-12 months and re-apply. That's pretty much the best solution we (or anyone else I know of) could come up with for the false-negative problem. We wipe the slate clean and start over again. There are lots of people here who got in on their second or third attempt, and they're kicking butt.
You can too."