Google Software Developer interview questions

A Google recruiter contacted me (I never applied for any positions in Google). Within a week I had my phone interview which went very well. They decided to skip the second phone interview (at least that's what I was told) and invited me to the NY office for in person interview. In person interview lasted the whole day with me talking to 6 people and having a lunch with a team. I found the office to be super cool and fun atmosphere and people were very nice. They questions asked were fairly reasonable. What threw me off was recruiter stressing several times that Google's approach to interviews is very academic. I was more technical then academic (I thought) and spend the next week reviewing algorithms and data structures and such. I was told at the end that I have very strong professional qualifications, but my knowledge is more academic and were looking for somebody with more hands on experience (after me throwing theory at them left and right). At the end I think I overdid it. I think you need to find a good balance if you want to get hired.

I initially submited my resume online for the position of Software Engineer at Google. About 2 months after, I received a call from HR asking me if I was still looking for a job, and if I was interested in a position at Google. I said yes and listed a number of positions I was interested in: Research Scientist, Software Engineer and Used Design Scientist. Two days after the call I received an email stating that my resume will fit the position of Software Engineer and was scheduled a technical phone interview 3 days later. The interviewer was nice and polite. I gave a first answer to the puzzle but he wasn't really satisfy with the answer. I got stuck for 20min and didn't get much help from the interviewer. The interview last 45min. I was given 10 minutes at the end to ask him question about his job, the life at Google, etc... Then he hang up the phone in a manner that let me knew I wouldn't go through the next step... Two days after the interview I received and email from the HR stated that I was rejected.