1.) Basically everyone who gets hired at Google feels that way at the beginning, right on up to Larry Page. He tells this story occasionally about how when he got into Stanford, he kept walking around for a month or so terrified that he was about to be "found out" and that Stanford would ship him home and rescind his acceptance. And then when Google started becoming popular, he was afraid that it was taking too much time away from his studies, so he tried to sell the whole thing for < $1M.
The two things the interview process is really looking for is a.) How do you react when faced with a challenge? Do you dig in and attack it, or do you flinch and go away? and b.) Do you really want to work at Google? Things like big-O notation and coding skills are important, but if you really want to, you can pick them up on your own.
Incidentally, this is the same criteria YCombinator uses, except that instead of "do you really want to work at Google?" they ask "do you really want to found a startup?" It's a pretty handy mindset to develop in general.
2.) I felt the same way, and then discovered it was nowhere near as bad as I expected. There're a bunch of pretty autonomous small groups working at Google, often on pretty cool things. One trade-off is that the more important your work is to the company, the less autonomy you have, yet the more important your work is to the company, the greater the resources you have at your disposal and the greater the financial and career rewards.