Wednesday, August 13, 2008

Amazon Interview

I went through my interview with Microsoft in my previous blog entry. In this entry I plan to discuss my Amazon interview. I applied to Amazon after having visited the Silicon Valley area. I knew that I didn't want to work in that area and hoped the Seattle area would be nicer. Amazon gets tons of traffic daily and I'd been very impressed with their S3 and EC2 technologies, which I discuss here. I wanted to work at internet scale and Amazon seemed to be a prosperous and growing company.

I received an email from an Amazon recruiter not too long after submitting my resume. She described the process: two phone screens where I would have to write code over the phone and then they would fly me to Seattle. I had just come off my interviews with Google and Yahoo, so I was excited to have another opportunity ahead of me.

For my first phone screen, I was out of town, so I had to do it in my car. They mentioned I would have to write code and I shouldn't be driving. I had pulled over in a parking lot and was ready with pencil and paper when the call came. I had also turned off my car and it was about 100 degrees F outside; it was definitely uncomfortable. In this first interview, he asked me to write a binary search function for an integer array. Normally I don't describe the questions that are asked; however, in this case I don't think I'm giving away any big secrets.

I wrote a recursive binary search implementation and read it back to him over the phone. It was a bit odd to read code over the phone. I had to read out curly braces, square brackets, the whole works! When I finished reading it he asked me if line X was ok. I told him that I thought it needed a +1 to it. He said ok and then asked me why I chose a recursive implementation. I told him that I thought it would be easier to write. I tend to think recursively. He asked me what the downsides of a recursive implementation are. I told him that it requires time to push on and off the stack. I also mentioned something about stack overflow, but in hindsight that was a bit silly. The greatest stack depth you can ever have for a binary search is 32 (on a 32 bit machine). I also mentioned that a tail call optimizer would eliminate the performance penalty. I'm not sure he understood that, so I didn't pursue it. Besides, I don't know of any C++ compilers that include tail-call optimizations.

We had plenty of time left, so he asked me to rewrite it iteratively. I complied and started writing it. In the middle of writing it, I realized I screwed up the recursive version. I told him about my screw up over the phone and called myself an idiot. We both got a laugh out of that. I finished my iterative implementation, double checked it for accuracy, and read it to him over the phone. He seemed happy with that approach and I mentioned that it was easier to write than the recursive version. However, I imagine that is because I had calmed down some and the recursive version had prepped me. He asked me about some of the test cases I would run on it. I mentioned as many as I could such as element not in the array, element at each end of the array, element in the middle of the array, duplicate elements, etc... He seemed satisfied and began telling me about their team and projects. In the end he asked me if I had any questions. I only had one or two about the team and working conditions. I'm not a huge questioner, I guess.

Honestly, at that point I wasn't sure I'd be getting a call back. I had flubbed the recursive version of a binary sort for goodness sake. I mean, come on, who does that? I should have nailed that one. I was a bit disappointed. (On a side note, there is a really great article on binary search in Beautiful Code. If you don't have that book, you really should.) Since my phone screen was on a Thursday evening I had to wait until the next week to hear my results. The recruiter called and told me that they were interested in talking to me further and they would like to set up another phone screen. I was excited to be moving on to the next round!

The next interviewer also asked me a fairly basic programming question. It is one that I ask a lot in interviews and therefore quickly pounded out the optimal solution. In this case, it seemed to take him a few minutes to verify that it worked. I was a bit surprised - I figured if you asked a question you should know the optimal answer for it. It could be that he was testing me to see if I would rush to change anything, but I was confident in my answer. He seemed pleased and we moved on to talking about other things. After this interview, I was pretty confident that I would be getting to go to Seattle and after a few days, the recruiter called to confirm it.

There were a few negatives about the trip to Seattle with regards to Amazon. First, the put you in a hotel downtown, which means that you are within walking distance to everything. That's not a negative. However, they don't imagine you need a rental car, so they don't provide one. Instead, they reimburse you for taxis. Now, I appreciate being reimbursed, but it is a lot of trouble. I have to find the cash to pay the taxis, get receipts, keep the receipts, turn them in, and wait 6 weeks for the money. Honestly, it's just not worth it. Secondly, the hotel they put me in didn't have free in room internet. I wasn't going to pay $10 a day to get it, either. They did have free internet in the lobby, so I would go down there, download an Ars Digita Video Lecture and go back to the room to watch it. I will say that the staff at the hotel was very courteous and the restaurant was great, but not having in-room internet sucks. Big time.

Amazon flew me in a day before the interview, so the first day I was there I went and walked around the downtown area. I found it vibrant and clean. I went to a suggested restaurant nearby and had some really amazing food. However, it was getting late and I was tired, so I went back to my room to rest up for the next day.

The next day I awoke and took a taxi to the Amazon building. It was on 5th street South. Either that or 4th Street South. I forget. But the reason I bring it up is because the directions explicitly say that South is different from not South :) In other words, they are on different ends of the town. I'm paranoid that my taxi driver won't know that and keep repeating to him, "South, right? I mean it's a different street or something." We get on 4th Street (or 5th Street...who knows...) and it's not South and I'm repeating again "4th Street South!". Finally, he assures me that he knows where he is going and I should just let him take me there. I sit back, say "ok", and enjoy the ride. We drove by the Seattle Public Library and I am amazed by its architecture. It is truly stunning.

Finally, we arrive at our destination. He lets me out and he pulls off after giving me a blank receipt. For that matter, all the taxi drivers have given me blank receipts. Do I fill in the amount and sign them myself? I have no idea. Anyway, I'm looking around and I don't see an Amazon sign anywhere. I'm freaking out thinking "Oh my gosh, he has taken me to the wrong street!" However, I do see a street sign and it has South on it, so I must be in the right place.

Finally, I see an entryway on the side of the building with "Amazon" on it. I go inside and speak to the receptionist. I'm about 30 minutes early, so she asks me to take a seat. Interestingly enough, as I'm sitting there thumbing through magazines, I find an advertisement for my current company, Acxiom. It had to be the worst advertisement I'd seen. It was a city-scape with a lake and the words "We make information intelligent." What does that even mean? How do I know what Acxiom does from that? I sat there for about 10 minutes coming up with better advertising campaigns. It wasn't hard. Having worked at Acxiom, I am Jack's complete lack of surprise.

A little after the appointed time, my first interviewer came and got me. He didn't say much as he walked me to the room where I would spend the rest of the day. In fact, once we were in the room he immediately asked me to code the solution to a problem. There was no introduction, soft-skills questions, or questions to make you comfortable. It was just an immediate call for action. I did well on the first question, though it took the entire time. The next interviewer had to wait outside the door a bit for us to finish up. The only odd thing was that I still have no idea what the first interviewer's name was or on what team he worked.

The second interviewer was a bit better, I think he told me his name :) However, he once again avoided any comfort questions and went straight to the coding ones. He asked a question that I put to my CS 101 students. I told him that it is a programming assignment that I give them and that it is usually a bit long to write out; however, I hoped I could do a better job than they could. Still, the program just takes time to write and it took up an entire whiteboard by the time we were done. He asked quite a few questions about it and I fixed a few bugs reading back through it. He also asked me how I would test it and I went through the various scenarios. One of those scenarios failed with my current implementation, so we fixed that as well. Then, it was time for the next interviewer.

The next interviewer asked a design question. It was a question that I had some familiarity with it as it included aspects of record linkage. In fact, I explained a few things to him from the leading edge of research that he was not familiar with. We got into a little debate about whether user click-streams could be substituted for a heuristic algorithm, but on the whole it was a good interview.

After that, it was the team's boss's turn to take me out to lunch. Amazon doesn't have a cafeteria (at least they didn't take me to it), so we went across the street to a Thai restaurant. Turns out my interviewer liked the same type of food I did and we ended up ordering the exact same thing. We talked about my experience and work history over lunch and he talked about the team. He mentioned a number of times that it was a production team and I would have to carry a pager. He wanted to make sure I was ok with that. I told him that I was and that I had done support in the past and was fine with it.

When we returned to the office, it was his turn to ask questions. His were more logic/match puzzles. At first, he started by saying "You have an array..." and I thought, "Oh boy, here we go again." Pretty much every company asks the same array question. "You are given an array with N integers. Each integer is in the range of [1,N-1]. Furthermore only one integer is repeated. How can you find the repeated integer?" I got this question and variants of it in 3 of the 4 interviews. I was getting ready to answer it again for Amazon when he threw a curve ball and asked a variant of it that I had never heard. This one was more interesting and actually fun. Now, I don't think that this type of question shows anything about the programmer other than whether or not he's heard the question before. It's kind of like the moving Mt. Fuji questions of old. However, I worked through the question, got the "Aha!" moment, and solved it. I tend to like solving those questions. Even though it didn't say anything about me as a programmer, I had fun with it.

The next interviewer was to assess my C++ and OO design skills. He asked me stock C++ questions, which I answered without difficulty. He then posed a coding question that was really more about interface design than actual coding. I had to do things like make sure my constructor was correct and write operator + in terms of operator+=, etc... I wasn't familiar with the domain (and told him so), but in the end I came up with a solution. He told me that it was the same solution he came up with when he first attempted the problem. However, he had to do it in a production setting, not an interview setting. I felt like coming up with the same solution as my interviewer was a good thing, so I was ok with that.

The final technical interview of the day was another design question. It was with this question that I had the most trouble. It was a question that was directly related to how they track and update pricing information. I tried to use a database to help solve the problem. I'm not sure if this was the right approach or not as it really constricted me. In the end, I came up with a pretty pathetic solution to a very complex problem. I don't think either the interviewer or I was happy with it. It was the one interview that I sucked at :)

After that was supposed to be the boss of the second team I interviewed with. However, he was out of town so he sent a sub :) This person described his team and the other team that I was interviewing for. I asked a lot of questions trying to distinguish the teams. I don't know that I ever could distinguish between the two teams, they were so similar. The only difference I could gather is that one was also responsible for a new framework.

After not getting the team structure sorted out, I was on to the final meeting of the day. It was with the human resources person. He and I chatted about a few HR matters and then he showed me to the lobby where they called a taxi for me.

On the whole, my experience with Amazon was just "OK". They were obviously not a "tech" company. Their dress code, lack of free drinks, and general frugality said that they were a retail business. The employees were smart, but seemed a bit like "cowboys". Their plans were overly ambitious and I wondered about their success rate. I'd also read online about how hard they worked and how little they were rewarded for it. Now, I certainly don't believe everything I read online, but it can't help but color your views.

In the end, I thought that Microsoft would be the better choice. I've never worked for a "true" tech company and the search space was very exciting. I really enjoyed visiting Amazon and I'm sure it would be a fantastic company to work for, but in the end the prospect of working for Microsoft was too good to pass up.

Well, I hope you enjoyed this second installment of my interviews and be sure to look for the third (Yahoo!) and fourth (Google) installments.


Frank McCown said...

Congrats on the new job at Microsoft! I'd be very interested in talking with you about your work on Live Search once you've been there for a little while. You may have seen that I taught a search engine class last spring.

On your interview you discovered the 1st Law of Hotels: the more expensive the hotel, the more they nickle-and-dime you. $10 per day for an Internet connection is pretty standard at the nice places.

Anonymous said...

Hey...great post! Wanted to run something by you. I have an upcoming interview with Amazon and it says on their website that "a suit and tie won't impress anyone here". I know they have a casual work environment, but didn't know if that should hold true for interview attire as well. The HR person who I have been working with said that business casual attire would be appropriate. May I ask what you wore and what your thoughts are on how to dress for an interview at Amazon? Thanks much!

Tanton said...

I wore business casual attire and would recommend wearing that. Good luck!

David said...

Did Amazon make you an interview? Do you remember how long after your interview the contacted you?

Tanton said...

Hi David,

I did receive an offer, but I don't remember exactly when. It was less than a week after the interview.

mingming said...

Really nice sharing of the interview process and some really brilliant insights!

Erika said...

Hi Tanton,

Great post! Came across your blog when researching interviewing with Amazon. I had my second phone screen last Thursday night, curious to see how long they took to get back to you for coming to Seattle?

Tanton said...

Hi Erika,

It took a few days (2-3) for them to get back to me. However, that depends on a lot of factors (like did the recruiter go on vacation and how fast does the interviewer send email, etc...).

Good luck on your interview!


Nghi said...

Thanks for the story!!! It definitely give me an insight of Amazon interview process. Now I'm all nervous but at least know what I need to prep for. :)

towardsjourneyman said...

Sorry for posting in a older blog post. But i dont think that you can do a tail recursion optimisation on binary search as you would definitely need the stack context.

Michael Angelo Rivera said...

Damn, technical interviews are my weaknesses, right now i am an Android Applications developer and i am thinking i will have my first Skype interview with them (the mobile team of amazon) so i hope they are going to be different.

J said...

Thank you for sharing your experience. I have an interview with Amazon tomorrow , not like how yours went. 2 45-minute interviews on my college campus. I just started practicing my comp sci knowledge tonight too... D: