Here Goes Nothing .. First Two Interviews [1/13/11]

I received an email asking to set up two phone interviews with Amazon.com.  This took me by surprise because I had just started applying for summer internships.  I was, however, extremely excited to be interviewing with Amazon

My first interview went well.  I was asked about general coding and data structures as well as how to reverse a string in place.  Easy.  Then I was given questions on efficiency and big Oh.  Finally I was asked to set up a deck of cards using classes and give the appropriate methods and variables.  

I was a little bit less excited after my second interview but couldn't get the thought of Seattle, Washington off of my mind.  The second interviewer asked me more detailed questions.  The first major question was to read in a list of 10,000 numbers [0,100] and then output the numbers missing from the range 0 to 100.  I initially came up with a binary search tree, later realizing that a hash table would be a better solution.  The next question was to read in a dictionary file and then output all of the words that are anagrams.  An anagram is a word that uses the same letters as another word (e.g. stop,post,tops,etc.).  My initial solution was a map with the key being a sorted word and value being a list of the words which match the key after being sorted.  I realized after, that again, a hash table would be quicker if the hash function was made so that no two keys could be indexed at the same location.  My initial solutions were verbalized but I was asked to complete the programs, syntactically correct, and submit them within an hour.  This was probably the easiest part of the whole interview process.