Amazon.com Interview
November 16th, 2005
Antabuse Online Buy Erythromycin Zyban Online Buy Soma Prednisone Online Buy Lotrisone Lipitor Online Buy Lipitor Erythromycin Online Buy CoumadinI just finished my second job interview with a large American high-tech company. This time, it was [Amazon.com->http://www.amazon.com] who wanted to ask me tricky questions. And they devoted 45 minutes of their time to do it.
The interviewer was a nice young man (again, Asian) about my age. After some small talk where I, again, had to explain why I was at my fourth year of Master studies and had no Bachelor's degree (that's very weird over here), the coding questions started.
<technical>
He first wanted to ask me something nasty about pointers, which I kindly declined. He then switched to asking me about how to reverse the order of the words in a given text string. My (Java) solution used String.split(), a reversed for loop and a StringBuilder.
After the first question, he asked me how to pick two integers out of an unsorted array such that the sum of the two elements equaled a given number. Coming up with a naive dual-loop version was very straightforward, but I couldn't think of a better strategy. If someone can tell me how to do it in less than O(n^2), please post a comment.
The next question was about finding the closest common parent to two given nodes in a binary search tree. After sitting for a minute or two without being able to figure it out, trying to explain to him how to do it (without knowing it myself) and then thinking about it for another minute I finally realized that the problem was much easier if you didn't start with the two given nodes, but with the root node. So after the initial trouble, I gave him a nice O(log n) algorithm.
Finally, he asked me about how to count the occurrences of all words in a given text stream and print each word and its frequency sorted by decreasing frequency. Again, I started out with a non-optimal solution involving a HashTable and some sorting, but pretty quickly realized that it all could be done much more beautifully with a PriorityQueue.
</technical>
Welcome back. For all the technical non sense above, please forgive me.
Anyway, we ended our 45 minutes by talking about how it was to work at Amazon and some practical questions about employment. If I understood him correctly, they have a much quicker decision process than Microsoft, and if they are interested they will ask me to come to a second interview within a few days. I also asked him about what group he was working on, and he happily spent the last seven or eight minutes describing his work. 
Show this on a map.
Entry Filed under: Employment
8 Comments
1. Loriel | November 17th, 2005 at 02:38
Ännu en interview! Du är så cool!
När är det dags för Google då??
2. Tess | November 17th, 2005 at 15:06
WOW! Me impressed!
3. ano | December 30th, 2005 at 20:08
pick two integers out of an unsorted array such that the sum of the two elements equaled a given number.
You can solve this problem O (N Log N).
First Solution:
1) Sort the array — O ( N log N)
2) For each element in the array, does a binary search to find another element that sum up to the Number.
O ( N log N)
Second Solution:
You can do this in O (N) using extra memory (a hash table).
1) For each element, take the target number and subtract it from each element. Look up in the hash table if the result of the difference is in the hash. If not, put it in the hash. If you don’t have any collisions, this algorithm is O (N).
4. Henrik | January 4th, 2006 at 10:03
Thanks ano! I actually figured out the second solution the other day while thinking about it. Should have been able to think of that on the interview… but one’s brain doesn’t work the same way while being interviewed as it normally does.
5. ano | February 6th, 2006 at 14:16
The word frequency problem. you said that you can solve this elegantly using PriorityQueue. I don’t get how you can do this with priority queue. Can you please explain? Thanks!
6. Henrik | February 6th, 2006 at 16:26
The basic idea was just to have a PriorityQueue with all words in and use their frequency as key. Then, for each word in the text stream, add it to the PQ if it doesn’t exist, otherwise just update its current key (frequency). After adding all words, just print the elements in the PQ in their sorted order.
Its elegance is not in better time complexity than any other solution (you still have to sort the words at some point, so O(n log n) is pretty much your lower bound). It is more that you can use a PQ to do the sorting implicitly, i.e. you have to write less code.
7. ano | February 6th, 2006 at 19:50
Ohh! I thought there’s something about Priority Queue that I don’t know about. Usually, Priority Queue is implemented using Min-Heap. I thought Min-Heap would be a good solution. Also hashing would be good. Thank for the explanation. Good luck with your interviews!
8. Amod | March 30th, 2006 at 15:10
In fact, I believe you can do this last one in o(log.n) time but with a balanced tree like B+ tree but with 2 indices. 1 index would be for the name and the 2nd one for the frequency.
The idea is as follows:
1. Read a word from the stream. If word is in the first index just increment the frequency associated with it but then go to the other index and search for the ‘previous frequency’ (i.e. previous value for the name in the 1st index) and the name. Each of these operations are o(log.n). Now that you have found the value in the 2nd index increment that too. Now this update can be implemented as delete/insert which is again o(logn) for a balanced tree.
2. Keep doing this till the stream ends.
3. In the 2nd index(i.e. the one indexed with frequency) you will find the numbers in sorted order (ascending actually) in a linked list. Just print them out in O(n) times. If the problem is to print them in descending order it should still not be hard. I think you know how to print a linked list in reverse order in o(n).