The reason Google has a reputation for hard interview problems is that before they came around, the standard technical interview was "So, $NAME, tell me about what you did at your last job". They were one of the first silicon-valley companies to have technical interviews, and so it frightened all the unqualified candidates who couldn't just coast in on good conversation skills.
Before Google, the company with a reputation for impossible interviews was Microsoft. Like Google, I strongly doubt that their questions are anywhere near as difficult as the rumor stream claims.