Having read many similar accounts of interviewing at Google I can't help but believe the two companies share the same hiring sentiment: they'd rather leave more qualified engineers on the table than risk hiring a bad one. If I were the OP I wouldn't (and it doesn't seem like he does) feel bad about it but instead use it as a determinant in viewing one's granularly-acquired skillset in contrast to the skillset involved in working at one of these gigantic companies. Its a good perspective to have regardless of if you end up working for them or not.
