Amazon Software Development Engineer Intern interview questions

There was posting for SDE interns on my university's job site. So I applied online via the job site to the job position. Within a week, I was scheduled for two 45-minute in person interviews on my university's campus. Both interviews were technical interviews with current SDEs. I interviewed with them and they got back to me within two weeks.

I got the interview by giving them my resume at an on-campus job fair, answering some basic technical questions right on the spot and following up by submitting my resume online that night. They were the only company that asked me actual technical questions at the fair, but I think they were using it in place of a phone screen to weed out the obviously unsuitable candidates. I got an e-mail within a day or two, asking me to sign up for an on-campus interview to take place in about two weeks. On the day of the interview I met with two separate people, each for about 45 minutes to an hour. The first person asked me a couple of basic can you actually program kind of questions, but then followed up by asking me about the performance characteristics of my implementations and asking me to improve them in time, space or both. He then asked me to design a stack data structure in my language of choice, and asked me to explain my design decisions. Finally he closed the interview by asking me whether there was anything I wanted to know about Amazon, and spending a few minutes answering my questions. The second person spent a few minutes discussing the painting on the wall, and used it as a lead-in to ask the hardest question of the interview: how would I determine whether a binary tree structure was symmetric, both in shape, and in contents. I spent a few minutes working out a solution which was in fact wrong, since it tested whether the tree was bushy, not whether it was symmetric. However, the interviewer pointed out that I was wrong, and asked me what was wrong, and what my solution actually did. Once I had answered these questions, he started asking questions designed to lead me to the correct answer, which I did eventually find. Once I had found the correct answer, he asked me some questions about the performance characteristics of the algorithm, as well as how big the data structures involved would grow to during the run. Both interviewers seemed more interested in my problem solving process/skills than in how well I answered the questions. About a day after the interview, I got an e-mail letting me know that I would be receiving an offer and asking me for a good time for the recruiter to contact me to discuss that offer. I did choose to accept the offer.