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.

Terracotta on FC6

Terracota makes clustering simpler by providing a shared VM concept, where the application programmer need not worry about any kind of clustering API's and assume that her code will be executed across multiple JVMs. Its a novel approach for clustering any application without the need of changing much code.

Its driven by a XML based configuration file called tc-config.xml file which can control the classes you want to share across multiple JVM. By sharing it is not the usual serialized way of sharing, instead Terracotta sends the difference between the objects and thus is more efficient.
The sample applications provided with Terracotta are very neat and show the power of Terracotta and it just works out of the box. While I was trying to download Terracotta on my Mac, I did not see any Mac binaries in the download page. I remember seeing the demos in different videos [1] used Mac. Ofcourse it is based on Java and it will work on Mac, but I was annoyed to see only three links when I clicked on the download link. Later I found out that it has been fixed with the new version 2.3-stable1 build which is a generic build and can be used in most unix like platform. Its available as a separate tab in the download page and was hard to notice. I did download the generic 2.3-stable version and got it working without any problems. I had to set my JAVA_HOME to /System/Library/Frameworks/JavaVM.framework/Home/


I dual boot Mac and Linux FC6 - unfortunately I have a few issues in Linux (battery, hibernate and sound related) and have to boot in Mac quite often. But being a Linux fan and with Terracotta giving me a reason to boot into my Linux again, I booted in FC6 got all the Linux binaries - the three binaries listed in the download site (DSO, Spring and Session). Untarred them to a terrocotta directory and ran the demos. For a start DSO is good and untarring that alone would be better.

#bash# cd terracotta/terracotta-2.2.1/dso/bin
#bash# ./tc-welcome.sh

FC6 has some issues with 3d Desktop effects and swing. The swing applications like JTable demo did not show up and it was not because of Terracotta - any swing application in FC6 did not work. I thought it was related to gcj java and I tried to remove all the gcj related packages. While removing gcj, I had to loose almost all the important packages like eclipse and open office which are dependent on libgcj. After loosing all my good applications, I tried running Terracotta again and still saw the same blank JTable frame. Then I had to google to find the solution to the problem and then I discovered that it was the 3d desktop effects (XGL) that was causing the problem. I was using Jdk 1.6 and it seems that the issue has been fixed in a newer jdk. For now I am happy running my swing applications without the 3d desktop! The JTable application and the Shared editor application worked just as shown in the video [1] and the introductory video at Terracotta.com.

Overall I was really impressed by the product. As with any rapidly developed open source (or commercial product) the documentation was really scattered around and there were lot of things to read.

[1] Google Video - Terracotta presentation

Macbook and Linux

I got the latest Macbook Core 2 duo (Mar 2007) and really liked the new OS with the speed of Intel Core 2 Duo processors. At first I found it hard to use OS X, mainly with the keyboard layout and new shortcuts, but I liked a few things about Mac. Few of the UI things were really mind blowing, but then I was lost trying to find a few things. I am more of a Linux fan, but Mac OS X seems to be a better alternative to the more dominant Windows. I found the Mac experience better compared to Linux, since most of the things work straight out of the box. I know Linux requires a bit more work in that area, but I am sure it will catch up soon.
Being a hard core Linux fan, I thought of installing Linux in my Macbook.
I had used bootcamp to partition the drive, but unfortunately I pressed OK somewhere and created only a 5GB Linux partition :(. I had also installed reFit for dual booting OS X and Linux.
I managed to install Fedora Core 6 64 bit version on this 5GB parition, but I was not able to boot because of some partition synchnozation issues. MacBook uses the new EFI partition. Many of the Linux tools like parted, etc is aware of this partitioning scheme, the Linux installers does not work straight out of the box :(. I had to do a few reboots and do synchronization using reFit.
I was impressed by the new effects in FC6. The cube effect and other desktop effects were really cool.
The new wireless card is not supported yet (Mar 2007) and I had to use the wired network to browse the internet. I saw Flash 9 was available, but could not have it working because of my 64 bit version. I could use ndiswrapper to make the wifi card work, but it required a 32 bit OS. I also had a 5GB linux partition, which was not enough by any means. I wanted to increase the partition and thought about installing different Linux versions in Macbook. Then I had some issues resizing and I had to completely remove the Linux partition and start from scratch. I did not want to install OS X again, so I had a 40GB OS X partition which I did not touch. I wanted to install various Linux versions and with the new EFI partitioning, there was a limitation of the number of partitions you can have. I wish there was something like extended partition to satisfy my ambitious goal of installing multiple Linux distribution. In my previous IBM thinkpad I had 3 Linux distributions and one other OS. (MS Windows which I rarely used). I found that one way I could achieve that in my Macbook is to use LVM and dynamically resize the partitions and create new partitions for new distributions that I want to install. Unfortunately Ubuntu at that time (or maybe even now) did not have support for LVM and Gentoo live CD did not work that well - X did not start and I tried running some install scripts from command line which failed.
I downloaded FC6 32bit version now and I burned a DVD. I booted using the FC6 DVD and created LVM partitions. So I had four partitions now - two of them were the EFI partition and the MAC hfs+ partition which I did not touch. I had to create a boot partition of 100+MB, since boot partition cannot reside on LVMs. I then created few partitions inside LVM - one of them was the / partition and others were partitions like /home and /opt. /home will be shared with all the distributions once I have more distributions installed.
After installing I got the basic rpm's like mplayer, flash which are not there by default. I was forced to use Yum, though I am not a big fan of Yum. I like apt-get and I am aware of the apt-get port for rpm, but recently I have been using the defaults provided by the distribution. With Ubuntu apt-get is the default since its debian based and I really like that command :). I have used Smart with OpenSuse - which was not bad.
I used ndiswrapper with a binary driver for some time and was irritated by the frequent kernel crash. I had no choice but to use this driver or stay near a wired network :(. I was constantly tracking ticket 1001 in madwifi and finally one fine day there was an announcement that support for the card with device id 024 is finally available. I checked out the madwifi branch and everything worked fine with an access point without encryption. But with WEP it did not work and I am now tracking ticket number 1243 and hoping to have WEP support soon! WEP support is finally available (Yay and thanks to all those developers who made this possible) for device id 024 ( the one that comes with Macbook). To compile the madwifi drivers, get the following branch of madwifi:

#bash# svn co http://svn.madwifi.org/branches/madwifi-hal-0.9.30.13 madwifi-wep
#bash# cd madwifi-wep
#bash# make && make install
#bash# modprobe ath_pci
(also added the following entry in modprobe.conf
alias wifi0 ath_pci
)
NetworkManager in Fedora did not detect the card even after restarting it several times. May be it was some issue with uninstalling the previous version of madwifi driver that I had installed. I had to reboot (I have never done that in Linux, except for Kernel upgrades) to find that NetworkManager worked perfectly and I was just able to connect to a WEP based network using this new driver.

I do have issues with hibernation and suspend. It does suspend or hibernate properly, but after restoring, X behaves strangely. The mouse pointer sometime vanishes or the mouse pointer gets caught in a small area in the top left corner of the screen. I will have to kill X to get a usable desktop.
Microphone issues: The soundcard works fine, but the microphone does not work. I discovered that when I was trying to call someone in Skype and the other person was not able to hear anything. I am yet to apply the mactel patches to get the microphone working.
Battery Usage: I noticed my battery gets drained very fast in Fedora and so I usually have my power cord connected while using Linux. I tried stopping a few services but that did not help. I think I have to remove some modules and that may increase the battery life.