Sunday, August 26, 2007

My Amazon interview experience

I was surprised to receive a mail from Amazon asking me for an interview. I had just applied to Amazon at the Dice career fair at Linux world and I did not expect a call from them after the initial talk I had with the software development manager at the fair. All excited with the email, I scheduled my interview for the nearest possible date. After some initial confusion I got a surprise call on my mobile - while I was in my friends car and in the middle of a traffic light! I had to reschedule my interview to some other day and again I made the mistake of scheduling it for the nearest possible date. I had no preparation and I was still doing my internship at Verisign. I scheduled my interview for the next day after my last day in Verisign and so I had only one evening to prepare for the interview :(. With so little time I managed to grab a book on Data structures to revise a few data structure fundamentals. After going through a few concepts I was bored and wished for more time! I then thought of revising a few of my Java concepts and grabbed a Java book which I had never touched before. The book was Practical Java and seemed to be really nice. I went through a few concepts like pass by value in Java and a detailed discussion about that including . After saturating myself with a few Java concepts I thought I will do a context switch and listen to some data structure lecture from Berkeley webcast. Unfortunately some of the streams lacked quality audio and I had to skip a few lectures. Then listening to some lecture and just slept off. I woke up at 11 am and was greeted by an engineer from Amazon. He started with some basic Java questions and I was happy that I could answer them...but then I had to deal with questions I did not know or did not remember :(. Here is the complete interview for everyone else searching for a job and preparing for an interview:

Question1: What is a final class in Java?
Answer: I was delighted to hear this question and gave this answer - A final class
cannot be inherited. The final keyword is overloaded in Java - a final class cannot be extended, a final method cannot be overridden and a final variable cannot be changed.

Question2: Difference between Abstract class and interface:
Answer: I said interface can have only method declaration whereas an abstract class can also have a method definition. The interviewer extended the question and asked me what is the difference between a pure abstract class which cannot have method definitions and an interface - I gave him the generic difference between an interface and class saying that multiple inheritance is possible with interface and not with a class. The interviewer again asked me if there is any other difference. Not able to think well at that time I said I don't know and said that I will prefer interface for my implementation.

Quesion 3: Difference between HashMap and Hashtable
Answer: I thought about it and said I know both are the same since I have used Properties which is a Hashtable and it is similar to HashMap.
After googling I saw that the difference is Hashtable is not synchronized and it supports null for key values.

Question 4: Difference between ArrayList and Vector
Answer: ArrayList is not thread safe and Vector is thread safe.

Question 5: What is the value of i in int i = 5/3
I said 1 since it takes the floor in Java and rounds off. He asked me the answer for float i=5/3 and I gave the answer(wrong) as 1.667. The correct answer is 1.0.

Question 6: How do you create a thread in Java.
Answer: Since I did not revise that section of Java, I could not answer this question well :(. I just said that there are two ways to create a thread. One is by extending the Thread class and the other is implementing the Runnable interface and overriding the run method. The interviewer asked me how do you start the thread? I answered that it can be started using the start method - but said I don't remember it that well since I did not use it recently.

Question 7: If you have a really big array - how do you find all the pairs whose sum is 50.
Answer: I gave a worst case complexity of adding all the elements in all possible ways to find the sum and see if it is 50. He tried going more in depth - but I declined to answer :(

Question 8: This was a tricky question and it took the interviewer some time to explain the question!. Given a number n, How do you find two numbers whose product is one of n+1 or n+2. In case both n+1 and n+2 have multiples - how do you find the multiples whose difference is really less. Eg: Take a number say 5. The two numbers n+1 and n+2 are 6 and 7. 6 has a multiple and 3,2 is the solution to the problem.
Take another number say 7. 8 and 9 are the two numbers. 4,2 and 3,3 are the two solutions to the problem. But since 3-3=0 is less - 3,3 is the correct answer to the problem....
My Answer:
Understanding the question was itself a big exercise for me and I think part of the question was an answer to the problem. But then he asked me how do you find a multiple of a number - I said we could divide it by 2, 4, etc. Then he asked me at what point you stop dividing and I said its n/2. So in case the number 8 - I will divide it by 4, etc. The second part of the question was how do you find the optimal pair (pair whose difference is less) - I had to take a wild guess and say that one way is to see if n has a root. So 9. 16, etc with pairs (3,3), (4, 4) will be the answer for n like 7,8 or 14,15.


Question 9: What happens when you type Amazon.com in your web browser?
I gave a really long answer on how DNS works. He also wanted the details about the hierarchical nature of DNS. So I explained about the root servers and the caching that happens in between. So the root server responds with the authoritative server for COM and then a DNS query is sent to COM server asking for the authoritative server for AMAZON.com. Finally the Amazon.com nameserver responds with the real ip of the machine hosting Amazon.com. There are some HTTP requests and response between the server and client. A successful response is usually a 200 OK status message followed by the complete HTML body.
The client renders the HTML and shows the page to the user. He asked me if there are multiple requests for getting the different images in a page and I said yes ofcourse.

4 comments:

Mg9H said...

I have no comments about the technical questions, but about the algorithm ones, here are my thoughts:

Question 7: For general cases, My algorithm will run in O(NlogN). Let's say the array of number is A, the algorithm is to sort A in ascending order (which takes O(NlogN)). After that, loop through the array, with each element A [i], use binary search to find the value (50-A[i]) from the array A. If there's such value, we can output or increase the counter. Since there are N elements, each binary search takes <= logN time, the scanning time takes O(NlogN) as well. Total running time is O(NlogN).

Improvement: if there are duplicates entries in A, we need to modify & have 2 version of the binarySearch function, one to find the latest index of a given value, and one to find the earliest index of a given value. By doing this, we will cover **all** the possible pairs that sum up to 50. (For example, if the array is 5, 5, 45, 45, the improved one will print out <5,45> 4 times).

Special case: If we are given the value range of the given array, for example if they are all 16-bit numbers, then we can use the idea of radix-sort to solve this question in O(N) time (in this case, the running time is something around O(N+2^16)).

I'll post another comment about question 8 later.

Mg9H said...

Question 8: There must be something special about n+1 and n+2. Otherwise, I could only think of trying all possible numbers from floor(sqrt(n+2)) downto 1, when never you reach a number that divides either n+1 or n+2, stop, and that's your solution.

Anonymous said...

Thank you for speaking with me today. This is to confirm that I have you scheduled for a phone interview on 33/29 at 4pm PDT/7pm EDT. Michael will contact you at: 523365211.

This time too, i do not have any hope of passing the exam, since they will have stupid questions.
1. Reverse a String without API

Unknown said...

You seem to imply that Hashtable supports null keys and values. But it does not. It is HashMap that supports null key and values.