### The Amazon SDE Interview

Amazon recruited on campus at UMass over last fall and I was lucky enough to snag a spot after running into them at the career fair. The rep at the table quizzed me on some generic stuff, recording my answers (what is the algorithmic complexity of the best comparison sort?) on the back of my resume.

The interviews are done over several days by 4 interviewers on campus. Each one lasts about 45 minutes. In the first interview, I am randomly assigned to one of the interviewers. I was not asked very challenging questions, but we briefly went over my resume and he described his engineering department and product.

Then:

- Write the ‘merge’ function in mergesort. This needs to be linear time, and it is basically the only thing I needed to nail. He is also checking to see how familiar I am with coding; I am only given pen and paper to sketch out the algorithm.
- Describe a tree and write a few traversal methods. Find the least common ancestor of two nodes.
- The tricky one: Given an array of integers and another integer X, find if a pair in the array sums to X. This is actually a modified subset-sum problem, but it can be reduced to polynomial time by using a hash. My experience at every single company I’ve interviewed with is that a hash can be assumed to operate in O(1) worst-case time, even though it is not true in theory. The algorithm involves checking for the existence of a “complimentary” number stored in a hash for any given number in the array; if it exists then a solution exists. If not, add the number to the hash and check the next number.

I got a call later that evening inviting me back to the second round of interviews (all 3 of them). At this point it is obvious the first acts essentially as a screener. The next day, another interviewer repeated the process, talking about his product and gently bashing Microsoft (a former employer of his). I had to talk about the difference between a linked list and an array, and when I might use one over the other. For some reason the topic wandered over to the trie data structure, and the interviewer asked if this was something regularly taught at UMass, because it was a generally exotic structure. I answered no,since in fact I simply stumbled on it the day before while comparing notes with other interviewees!

My third interview was with the bar raiser. For the uninitiated, Amazon’s bar raiser is the designated interviewer who rakes you over the coals. He is tasked with ensuring that the average talent at Amazon trends up instead of down.

- How do you detect if a linked list forms a loop? For this question, my original intuition was to modify the node elements with a member that I could flip, ‘marking’ each element as I passed over it. Unable to change the data structure, the next most obvious solution is to use a hash to track which nodes have been seen. This results in O(n) time and space. He seemed satisfied with this answer; it was not until after the interview that I learned it could be done in constant space and linear time using Floyd’s “Tortoise and Hare” cycle detection algorithm (yes, of Floyd-Warshall).
- This was the hardest question of all the interviews: Given an array of integers, write a function to find the maximum number that can be obtained by summing up a continuous subsequence. The tricky part is firstly realizing that you cannot start your sum at 0, because if all the numbers in the list are negative, then your final answer will be wrong (because you will incorrectly return 0 as the largest sum). Secondly, encountering a negative number does not necessarily mean you should terminate the sequence, because it could still be part of the record sum. I struggled with this until he nudged me to the answer: the sum must be restarted whenever the running sum goes negative. Tricky question. I was also tasked with analyzing the brute-force approach to the problem, which is finding and testing all possible subsequences (hence n^2).

My fourth interviewer dealt almost entirely with design questions.

- We started off slow: code a factorial function and analyze its complexity. I did the stupid recursive method because it was easy, knowing I’d probably be asked to improve it. There are multiple approaches to optimization but I decided to memoize since it is a simple time-for-space tradeoff and is easy to conceptualize.
- The bulk of the interview involved designing a versioned filesystem in UML diagrams and explaining how it supported the requirements. The first requirement I was given was to make the versioning completely transparent, which I did by using redirectors to wrap the real filesystem objects. He kept piling on more minutiae, seemingly unsatisfied. I was growing a little impatient, each time responding that I’d simply add another data structure or pointer to my diagram to meet the requirement. Finally, he asked me how to support multiple concurrent branches at the same time, and I understood what he was getting at: he wanted me to make my system recursive! I pointed this out, scribbled hastily on the paper to illustrate, and he could not be more satisfied.

I got a call literally the same night, inviting me to a dinner sponsored by Amazon in the next few days. He gave me some BS line about how he couldn’t say whether I had an offer or not, and in fact our dinner (7 candidates and 4 interviewers) was completely filled with smalltalk and stories of Seattle weather without so much as a single mention of the interview!

I got an email a few days later with my offer, and I was suddenly overcome by a realization: if I hadn’t made the cut, why would they have bothered buying me dinner?

Just in case anyone is freaking out over not being invited to the dinner, I got an offer from them in Fall 2012 and I wasn’t invited to dinner. I didn’t even know there was one!

Ah, right – I didn’t mean to imply that this is some universal practice at Amazon. But in general one can assume that a followup phone call after going through a loop (as opposed to an email) is a very good sign.