Amazon Interview | Set 55 (On-Campus)

Online Test on InterviewStreet: 
18 MCQs (Normal C loop questions, networking, dbms, os, analytical) 
2 Coding questions 
1. Check if an undirected graph is a tree or not. 
2. Given an array of integers, print the 2 elements with least absolute difference. 

Interview Rounds:- 
Round 1: 
Tell me about yourself. 
1. Given a matrix(not necessarily square) in which the elements in a row, as well in a column are sorted. Find a given integer in the matrix. 
Tell the approach. And then code. 
2. Given a position where a knight is placed on an nXn chessboard. Find the maximum number of knights that can be placed on the board, so that no 2 knights attack each other. 
Remember that you need to just give the number of knights, not all their positions. I first could arrange ceil(n*n/3) knights. Then he asked me find a better solution. Finally I got to ceil(n*n/2). Then he asked me to code it. Then he asked me to remove the ceil condition(check for even and odd separately). 
He asked me if I had some question for him. I asked – Amazon strives to be the most costumer centric company on earth. What, as a programmer/developer, do you do to achieve this, because generally, the customer’s problems are an issue for high level managers and planners. 

Round 2: 
Started with some questions from my Intern project. 
1. Given a Binary Tree, replace the data of each node by the sum of data of all its descendent nodes.(Leaf nodes will have 0) 
2. Given a sorted array of positive integers, find the least missing positive integer. First I gave an O(n) solution. Then he asked me to optimize it. Finally I gave an O(log n) solution. 
3. Given a stream of numbers, find k random numbers from them. I explained him Reservoir Sampling approach. He asked why this approach works. What is the probability of each number being selected? What is the probability of any number being selected if stream has less than k numbers(its 1). 
He asked me if I had some question. I said I had one, but I already asked it to previous interviewer. He asked me if I got a satisfactory answer to it. I said the answer was very much satisfactory. 

Round 3 (CS Round): 
He asked me if I am comfortable with writing SQL queries. I prefered not to. 
1. What is an interface? Why it is used? Give an example. What is an abstract class? Why it is used? Give example. Why 2 different concepts of interface and abstract class? 
2. Do you know about singleton class? What is it? Implement a simple singleton class. I made some mistakes in making attributes static etc. He guided me and finally I corrected all bugs. 
3. Given a binary tree, where each node has an extra next pointer. Fill the next pointers so that each node’s next pointer points to its next sibling node. First I gave a solution where I would require a map, where each map key will be a level number, and value will be pointer to the last currently accessed node of that level. Then he asked me to do it without space. Finally I gave him a solution without space. I gave a non-recursive approach, and he asked me to code it. 

Round 4(Senior SDE 3 from Seattle Office): 
He told me about himself, his team, his work and his team’s work. 
1. Tell me about one of your challenging project/internship/class assignment. 
2. Give a situation from your life where you were given a negative feedback, and how did you tackle the situation. 
3. Explained me a cache situation, where, keys will be in cache, and each key will point to a string. It was LRU cache condition, and I had to implement the LRU cache. Then write a function to retrieve a string, given its key, from this cache. Retrievel should be O(1) (if you give O(n) retrival, he will ask you to make it O(1) ). 

Finally got an offer !! 🙂 🙂 

While you are answering a question, clarify any doubts that come to you mind. Dont take any assumptions by yourself at all. 
Keep on speaking your approach as you think. Keep speaking, if possible, even when you write code. They want to test if you really know the approach, and not just copying code. All rounds were technical and elimination. The last round has the highest weightage in their procedure. Write clean code, ask for some time if you want. 

Thanks a lot to the GeeksForGeeks team for helping with interview preparations! 🙂 

Many Many congratulations to the author. If you like neveropen and would like to contribute, you can also write an article and mail your article to review-team@geeksforgeeks.org. See your article appearing on the neveropen main page and help other Geeks.