Interview Experience of Pavithra by Amazon India

Hi, this is Pavithra, sharing my interview experience with Amazon at campus.
I was exempted from writing the online written test as I had interned at Amazon. This was considered as PrePlacement Interview for me. After the online written the procedure was the same as for others.
Elimination Round:
This was a kind of group coding. All of us were asked to write code for the following 2 questions. (Later during dinner they said they selected based on the logic you gave and also the perfection of the code)
1) Print a matrix spirally – use 4 ‘for’ loops inside a while
2) Connect the next pointer of a node in a tree to the next node in the same level
a. Level order traversal, use a count variable to maintain the count of nodes pushed in one particular level.
b. Use recursion. For root>left, the available choices are root>right, root>next>left, root>next>right, NULL. For root>right, the available choices are root>next>left, root>next>right, NULL.
Face to Face: Round 1
The interview directly started off with the question.
(a) Given two linked lists, each node has a single digit and each linked list as a whole represents a number (integer). Write a function to add these two lists and store the result in a third list with each node representing single digit.
Eg: List1 = 5 > 2 > 1 > 7
List2 = 3 > 8 > 4 > 9 > 0
o/p = 4 > 3 > 7 > 0 > 7
Reverse the two lists and keep adding, maintain a carry variable.
After writing the code, he asked me test cases for this. I said normal ones having same number of nodes in two lists, one of the lists having greater number of nodes and one of the two lists being NULL.
Then he asked what would I do if a single node contains more than one digit, but still the entire list represents the same number.
Eg: List1 = 5 > 21 > 7
List2 = 384 > 9 > 0
o/p = 4 > 3 > 7 > 0 > 7
You are given no information about how digits are grouped. I said, I would reverse the list as well as the number inside a single node.
He then asked me to write a simple module which takes x = 21 and y = 38, (say these are those reversed numbers in a node) and o/p the sum of these which should be 59. The challenge here is you need to add the digits in MSB position first, as you have reversed the number.
(b) He then moved to the next question. You are given a map which contains islands and sea. Sea is in blue colour and islands in green. The entire image is stored as a matrix in which each entry represents a pixel. Blue colored pixels have a value of 0 and green colored ones have a value of 1. Find the number of islands in the map.
This can be reduced to a problem of finding the number of blocks of 1’s in a matrix of 0’s and 1’s. Initially I said have a visited matrix, mark all 0’s as visited and start bfs from the 1’s. Number of times you call bfs gives the answer. He told me to remove the visited matrix. So I wrote a code where I would change 1’s to 0’s as I push inside the stack in bfs.
He then asked to modify the code to return any one point in the largest island. Count the number of 1’s visited in each bfs. The call that visits the maximum no. of 1’s is the largest island. I returned the point where I started the bfs with.
He then asked me how could the storage space be optimized (ie) to avoid storing the entire matrix. I said it is enough to store only the boundary pixels of islands and manipulate it. He was satisfied.
He then asked me about my Intern project and Intern experience at Amazon.
Face to Face: Round 2
First he asked me how I got intern at Amazon, then about intern project. Next, he asked me to tell what I liked at amazon. I told about the working atmosphere and the flat hierarchy. Then I was asked what I didn’t like about amazon. I did not tell anything in specific (:P) Just spoke about my last two weeks of intern, the problems I faced in it etc.
He started off asking about runtime polymorphism, virtual functions, where are they kept in memory and pure virtual function. I just told him what all terms I knew and what all I remembered at that moment.
He then asked me a kind of coding question but only the algo. There are 100 million stars in the sky, you need to find the closest 10 million stars to the Earth. I said this can be done using max heap. He tried to confuse me telling min heap. But then I reasoned out why min heap can’t be used.
Then he asked me to choose a programming language and rate myself in a scale of 1–10. I chose C++ and said 67. He asked me about a destructor being virtual and the cases where it would be needed. I did not know about this but managed somehow.
Then I was asked about idempotent functions, dynamic cast and RTTI. I had not heard of all these before. So I told him that I did not know these terms. Still I guessed something and just blabbered (:P)
Finally I was asked to code the following question. Given a sum, print a path from root to leaf in a binary tree that sums up to the given value. I did that and then he asked me about Microsoft and Morgan Stanley interviews and how many rounds I cleared in them.
Face to Face: Round 3
As soon as she entered she told me this is a simple problem solving round and you need not write code. We will discuss only the logic.
She first asked about my intern project and where I come from. Then I was asked 2 questions
a) Given an array (1D) in which adjacent elements have a difference of 1 ( +1 or 1) return the index of the given element.
I initially came up with solutions which had flaws. After sometime I told the following solution : find the difference between the element to be found and the first element. Skip so many positions and again find difference and skip. Continue this till you reach end of array. She then told me to think of some other approach. Nothing came to my mind then. She said we ll get back to this question at the end.
b) In an array, for every element find the first largest element to its right side.
I knew this can be solved with stack but then I do not know the exact solution. When I said stack, she said lets try to solve in some other approach. So I tried some multiple solutions like processing from the end, finding the max till that particular point and some stuff. I don’t think I gave an exact working solution for this question. We were just discussing approaches, after a while she said we are running short of time and we are done!
She finally told me all my interviews are over and she asked me to wait for the result.