I applied online and was contacted by a Google recruiter approximately two weeks later. She set up two back-to-back 45-minute phone interviews for me.

My first interviewer was 15 minutes late and seemed very disinterested. He asked me to implement something that I'd describe as very difficult, and which I couldn't find online later. Regardless, I think I did an alright job.

The second interviewer asked me more standard interview questions. I arrived at the optimal solution for the first question and figured out a solution for the second question. The interviewer seemed to like me.

This was one of the more standard questions.

You have stairs with N number of steps. You can take either one-step or two-step steps. How many ways can you climb the stairs?