[marssaxman]

Maybe that's how it works at Amazon and Apple, but that wasn't my experience when I interviewed at Microsoft (twice!), Google, or Facebook. They weren't especially complex algorithm problems, either (how complex can it really get, when you're doing it on a whiteboard?). You just have to be able to think your way through a problem and explain what you're doing as you go; you should know what assumptions you're making about the limits of the problem, what you might do differently with different assumptions, and what kind of performance characteristics you should expect with those tradeoffs. There were definitely some complex design problems, especially during the Google interview, but I have really never experienced anything like the supposed "gotcha" coding interviews people stress out about so much.