Amazon Software Development Engineer interview questions

applied online got an email saying they need me to give an online assessment test. The questions were pretty straight forward regarding linked lists and nodes.

I am interviewed as part of on campus recruitment process.I am a student of NIT waranagl. this review therefore is in the context of on campus placement. There was an online aptitude test followed by technical interviews. There were four technical interviews . In the first technical interview I was asked to find the pivot element in a sorted and rotated array. O(n) solution is obvious and I gave him O(log n) solution ( binary search )and I was asked to code it.After writing the code,I was asked to check my code if it covers all the edge cases or not. I have tested it and it seemed to work for all the edge cases but the interviwer pointed out a case where my code fails and then I have corrected it.He also asked me to write the code for searching an element in the sorted rotated array using binary search. the second question is given a binary search tree ,replace each node with the sum of numbers greater than the number in the node.I gave him O(n) solution and he was satisfied with it. In the second round , I was asked to design an application that sends a message to two friends if they come within two miles of each other. I gave him a solution indicating the data structures used to maintain the friend list and model of the solution . He pointed out the cons of the solution and I modified the data structure.Then there was long discussion where I gave him different solutions and He pointed out the cons of each solution and asked me to overcome it.Finally I arrived at a solution and the interviewer was satisfied with it. He also asked me a couple of puzzles and I answered them. I think the third round was the bar raiser I was asked two questions. The first question was : Given n jars each having a colour of some value.the value of the colour is from 0 to 100. when two jars (with colours say 'a' and 'b')are combined, the colour of the resulting solution is (a+b)%100.Also (a *b) amount of gas is released .Find a way to combine all the jars to form a single jar with minimum amount of gas release.(Only adjacent jars can be combined). The problem is similar to matrix chain multiplication- O(n^3)(Dynammic Programming)and after I gave him the solution I coded it. The second question was: A quadra tree is a tree where each node has atmost 4 child nodes.(similar to a binary tree which has atmost 2 child nodes). A monitor screen (black and white) is represented by a qudra tree in the following way: case 1:IF the entire screen is white then the value in the root node is white. similarly if the entire screen is black then the root stores black. case 2:If the screen is neigther completely black nor white then the screen is divided into 4 quadrents. and the node has 4 child nodes each representing one of the quadrants.( the screen is recursively divided into subscreens). Now given two screens represented by two quadra trees, return a quadra tree which represents the overlapping of the two screens.( assume when white and white overlaps results in white,black and white overlap results in black , black and black overlap results in black). I was asked to write the code for it. Round 4: Q1: Implement a stack which supports pop_min (return minimum element in the stack in O(1) ) along with push and pop operations. I gave him a couple of solutions and I was asked to code them.The he gave me a solution (maintain a linked list of minimums in the stack) and asked me to code it. Q2: Given a binary tree with fields- {pointer to left child,poiter to right child,next pointer}. Initially the next pointers are all NULL. Now fill all the next pointers in each node with pointer to the node which is immediately right to the node in the same level. The next pointer of rightmost node in a level shold be NULL. It can be done using level order traversal using a queue but the interviewer asked me to do it without using queue or any extra memmory and in O(n) time. Hint: The logic is to fill the next pointers in the (n+1) th level while trvelling in the n th level. I was asked to code it. PERSONAL INTERVIEW (HR) There was no HR interview although I was asked some questions like -Why do you want to join amazon, future plans , tell me about yourself,your habits and interests and about why I didn't do an intern ..etc SUMMARY OF EXPERIENCES The amazon interview process is very cool.The main thing here is to stay focused since the whole process is time consuming. The interviewers were very friendly and they are not bothered about the formalities.So the experience was great.