Be very good at off-the-cuff 80% solutions to topcoder problems on a whiteboard, which I am. So much so, that when they told me to use whatever sort algorithm I wanted to, I used bubblesort on purpose, to prove a point, and got away with it. Later on, I reduced another interviewer's search problem to a polynomial equation that had integer roots when a solution existed (at which point he asked me what I'd do on an architecture that didn't have a square root or a divide function and I replied "and what modern architecture would that be?"). Which is to say their interview process is a computer science puzzle game IMO. The skills displayed here have at best a loose correlation with one's engineering skills, and that non-correlation shows up like crazy in their codebases (but Steve Yegge already covered that far better than I can).
In my case, it only took one round for me to get the offer which I (unfortunately) accepted (but the tale of my 4 godawful months at google thanks to naively letting myself get blind-allocated into the wrong team is a different story).
Google is a great company, really it is. I know lots of relatively happy people there, but focusing on the interview process is a mistake. The real challenge is to get yourself hired onto a good team by resisting all the pressure they exert to persuade you to jump into the blind pool, which is a recipe for russian roulette. The solution, which in retrospect I smack myself for not doing the due diligence to find out, is to insist on getting allocated to and speaking with your future team as a condition of accepting an offer. Do not compromise on this point.
Later, after talking with an engineering manager and getting agreement to be assigned to one team, they tell me I'll be working for some other team as if our conversation never happened. It's almost as if the attitude is that I should be lucky to have been offered a job and I should be happy with whatever I'm given.
The time to negotiate teams is after you get an offer. If you have any sort of negotiating leverage at all, you can probably exert some influence there. Basically, multiple managers "bid" on Nooglers, and then the manager from the highest-priority focus area gets him, modulo some input from the prospective employee himself. When I was hired, I was told I'd be working on Google Search, but the recruiter also said that if I didn't like that there were multiple managers in GMail and Apps that also wanted me, and I could go there.
In general, your goal should be to avoid getting marginalized. Typically, the highest-priority projects go to the best managers, who try to surround themselves with the best engineers, so your experience will be noticeably better on a high-priority project than a low one. The disgruntled Xooglers I know typically left because they got assigned to somebody's pet infrastructure project who somehow got headcount for a team of 3 or 4 but then has no idea how to run a software development project successfully, and no support for their ideas outside of their team. The happiest Googlers tend to be people in core Search, Ads, infrastructure (eg. MapReduce/Bigtable teams), research, or Chrome. These departments tend to feature large groups of loosely-knit, largely self-organized teams, and very hands-off management.
It could actually be a good thing that you ended up getting reassigned; it usually means that someone from a higher-priority area noticed your resume and swooped in with a bid. But you should be able to talk to the new prospective manager, or at least someone on his team. Every good manager I know will be happy to talk to a prospective Noogler that they want on their team if it means the difference between having them accept the offer or not.
BTW, I've noticed an interesting pattern where the culture of a focus area depends a lot on the first employer of the founder/SVP for that focus area. Search culture is Stanford culture. Chrome (which started from a bunch of ex-Firefox people) has a very open-source culture. Android culture is Apple culture with some Googliness thrown in (Android founder/SVP Andy Rubin worked at Apple for his first job). Google+ culture bears an unfortunate resemblance to Microsoft (Social SVP Vic Gundotra previously was in charge of .NET for Microsoft). Apps culture is a hodgepodge from various other companies (most apps were acquisitions). Infrastructure culture bears a strong resemblance to Bell Labs culture (former infrastructure SVP Bill Coughran was a VP at Bell Labs). I suppose the resemblance makes a lot of sense, and I wonder if other large companies have a similar effect.
It is amazing how quickly a company's ecosystem can change when you bring in a big name from a different environment.
Unfortunately, two days into working at google, I was informed that my entire team was going to physically relocate in a few months and leave me with an 80-mile commute each way. So I said that was unacceptable and ended up with the third project, which I've already described elsewhere.
Do not let them do this to you. Hang tough.
What did I win?
well, you can reduce any computable problem to that form
Whether it is a fast algorithm depends heavily on the sizes of the first and last coefficients, as you have to factorize them.
You should have gone with bogo sort to really stick it to them :) (http://en.wikipedia.org/wiki/Bogosort)
"Next step - we sort it".
"It doesn't matter. You just sort it. I'd use the inbuilt sort function".
"OK, but we still want to know you can sort a list."
"OK ... sigh ... what algorithm? Quicksort? Bubblesort? Mergsort?"
"We don't care."
"Um, OK, if you want me to roll my own sort algorithm, but don't care about performance, let's do it this way ..."
The best alternative I've heard about is something like a trial period, internship, or culinary "stage." That's a big investment for both parties to make without even finding out if someone can write and debug a simple program to solve a well-defined and familiar problem.
This is kind of silly, and the candidate decided to be a smart-ass and rub it in by demonstrating a really bad algorithm.
They should ask "well, what do you think the trade-off should be? Given that, what's the best algorithm you know for this set of trade-offs?".
Interviewing is hard to get right, because it's confrontational. Bad candidates want to fool you. Looking at the total system, the best bang for your buck is getting better candidates to apply. I've met very few managers who do anything other than a piss-weak job at getting good resumes onto their desk. They often throw a rough job description to a some liberal ars major in HR, who puts the ads up then tries to prune down the candidates who's buzzwords don't match the requirements.
Interviewing doesn't have to be confrontational. When we're trained, we're told that our job is to get the candidate to show us their best side. That aligns with the interests of both good and bad candidates. It's just that good candidates will be able to show us a really good side, while bad candidates simply don't have that ability. Then it's up to the hiring committee to set a really high bar and only accept candidates that have demonstrated it.
My answer: I'd change the hardware