I would NOT recommend interviewing with Google without a Computer Science degree. You need to be able to look at a function and know the Big-O for it immediately. Specifically, you need to look at YOUR OWN functions and know the Big-O immediately.
I'm not sure that knowledge of Big-O is requirement for Software Test Engineer.
The worst part of the process was my fourth and final interview of the day. The guy was from Moscow, and he had a very thick accent. All of my life, I’ve had immense trouble with accents, even slight ones. My project manager at work has a thick accent from Italy, and she basically sounds like Chewbacca to me. My interview with the Moscow Guy resembled one of those satellite interviews on the news. He’d say something to me, and there’d be this long pause before I responded. To make matters worse, he told me his first question was going to be “an easy one”, so when I barely understood what he said at all, I imagine I looked like a complete imbecile. “What was that? You want me to WHAT two numbers together? Mo de ploy? Mah dah bu? Oh, multiply! Right, two times two is four. I’m obviously partially retarded.
It is Bay Area and there are no any high-tech company without people with accent.