Amazon Interview | Set 87 (For SDE)

I recently cleared the Amazon SDE position. Through out my preparation neveropen played great role, this is the only site which i referred/followed more than 90% of the time during preparation phase.

Please find my experience with amazon below.
1 Written test
1) Given a array of number find the next greater no in the right of each element

Example-    Input     12 15 22 09 07 02 18 23 27
            Output    15 22 27 18 18 18 23 27 -1

2) Given a link list and input int K, reverse the link list in K size slots

Example Input 12--> 13--> 3--> 20--> 55--> 87--> 20--> 77--> 90 Lets k =3
Output 3--> 13->12--> 87--> 55--> 20--> 90--> 77--> 20

3) Given tree and input int K, Print the nodes that are k distance way from leaf.
Input is below tree and k = 2

Output-2, 5, 4

2. First F2F round (DS and Algo)
Two interviewer was there in panel, Only one was asking question other was only observing, He was noting down all the conversation happening between us and noticing approach and solution provided by me. This was common in all the interview rounds.

1) Given a infinite string of O’s and 1’s respectively. You need to find the transition point from 0 to 1.
I gave the native solution in O(n). He told to optimize more. Direct binary search can’t be applied on it because string was infinite and length of string was not given.
I told that i will divide the string in 10 size slots it will reduce complexity. Still he told to optimize more. I told i will increase the slot size in power of 2 like 2,4,8,16,32. he was satisfied with that.
He again complicate it by adding that now my string contain 0, 1, 2 in sorted order. You need to find transition point from 0 to 1 and 1 to 2. i provided the approach.
After that told this time i want to make it generic. String can contain 0 to n(input) number find all the transition point. I solved it, he was satisfy with approach and told me write code for it.

2) Find common elements out of two sorted array

3. Second F2F(DS and Algo)

1) It was bit difficult for me to crack, She stated asking from java cloning, which was my weak area. Given a class which contain string Name and reference to person friend, clearly shown below.

Class A {
   A(String str, Person P { //Constructor
       this. name = str;
       this.friend= P ;
   }
   // override
   Clone() {
       // code for this function was expected from me
       // which can produce the deep copy
   }
}

Suppose A–>B–>C–>D means A is friend of B, who is friend of C and so on..
Calling once the Clone method will clone the whole friend list like
A’–>B’–>C’–>D’ (there A’ is the clone of A).
Cracking this was really tough for me, because i was not familiar with these question.

2) How to find the last nth element from singly link list, its was very easy for me.
Solved in 2 min and wrote the code quickly.

3) Given a sorted array of number, value K and value X, find the K nearest number to the value
Example: Input 12 16 22 30 35 39 42 45 48 50 53 55 56 K = 4 X = 35
Output 22 30 39 42
Interviewer was running out of time because 1st question took huge time. So she told to tell only the approach, code was not expected.

4. Third F2F (Bar raiser)

1. What is your current project, What value you added in your project till now.
2. What challenges you faced while working in project and how did you overcome.
3. What was the important learning for you in last project.
4. If you have the option to go 3 year back in life, then what would you like to change in life, means which skills and steps/decision you want to gain or change.
5. What you did in past on which you feel proud.. blaa blaa….
6. Given a tree, how will you find the vertical sum of nodes
   refer this link to understand more about question
   Print a Binary Tree in Vertical Order
   I gave the solution using Hash map, but he was not satisfy with answer. He told to gave other solution because Hash map will increase the space complexity. I used array solution which was increase time complexity, then i used circular link list and finally solve it using doubly link list. He was satisfy with solution. Told me to code for it.

5. Forth f2f round(OOPS, design pattern and OS fundamental)

1. Started with my project details, my project was in android mobile, so he told me to design a “Contact application”. Class diagram and their relationship was expected from me. What all design pattern you can use in that.
2. Explain inheritance and Base class is given you need to stop exposing the base class methods without touching the base class at all. It was really tricky.    question i liked it.
3. What is deadlock and How to detect deadlock in system.
4. Concept of Database normalization and various types of it.
5. He also started asking some networking question. Like TCP/IP, socket connection.
6. How the chat between 2 user work internally, internally how the packets flows between layer. And suppose user A send “Hi” message to user B and user B just shutdown the system. What will happen in that case.

6. Fifth f2f (Hiring manager)

1. Why you want to join Amazon.
2. What did you know about Amazon.
3. Current project explanation.
4. What new code you implemented and how much impact it put on other.
5. Given a tree, write the In-order traversal. I wrote in 2 min using recursion.
   Next addition was, can you write it using iteration tried and wrote some buggy code.
   He started checking and told the bug and told me to correct it. Even-through i solved the same question at my home, Still it was not clicking my mind. I started correcting it but failed. After that interviewer gave one hint. I used the hint and solved the whole code again. He was running out of time so took the code sheet and told i will check it later in free time.
   Refer this link for actual solution and proper understanding of last question
   Inoreder traversal without recurssion
   

Message for all :-
Amazon expect accurate and precise code with less complexity. So discuss first with your interviewer the approach. Don’t jump into code.
Even if you don’t know the right answer, keep on discussing various possibilities to solve the question and try crack that problem with different angle. Practice more and more verity of questions.

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 contribute@geeksforgeeks.org. See your article appearing on the neveropen main page and help other Geeks.