Overall I think it went pretty well, the first 45 minute interview I thought went spectacular, and the second one was so-so.
- Talked about previous projects, career/research interests
- Talked about Amazon, what I like about the site (recommendation system)
- Asks how I would implement the recommendation system, talk about mix of offline-online data analysis
- Talk about the pros/cons, running times of various algorithms to find the a number that occurs an odd number of times in an array. I basically went through every data structure I could think of and described how you might use it and any challenges it would present.
- Do the same thing using only an integer and the given array, I didn't figure this one out - if you XOR all the elements together, the integer occuring an odd number of times is the result.
- Code a function to count the number of set bits in a byte (did a loop with a shift)
- Now do it recursively
- Now do it faster, assuming space is not an issue (use a 256-element lookup table)
- Asked some questions about what he does, and about how it is to work at Amazon
- Pick a data structure to help evaluate a mathematical expression. I couldn't think of what was needed, but I brainstormed out loud to at least not be sitting there looking stupid.
- He suggests a tree, and we work through together how to put the expression in the tree to make it easy to compute. (This whole thing was hard to wrap my brain around because at any node there is either an operator OR a number)
- Now code a function to compute the value of the expression, and code a tree node data structure to use. I thought out loud for a while and decided to go with an in-order traversal of the tree, which turned out to be correct.
- Now consider a generic binary tree, code a level-order traversal. I knew that to do this you needed to put the elements in queue, so I started going with that. I messed up by using the queue to store the values at the nodes instead of the nodes themselves, once he points this out I finish pretty quickly.
- I ask some questions about things interns have worked on in the past, and Amazon's test strategies.
I hope that I didn't mess up the last bit too much, especially since the first part went extremely well. We'll see, I should know within the week if they are going to give me an offer or not.