Amazon Interview Experience

                                  Image result for amazon attractive logo                                


     Position: Software Development Engineer-I      (WOW EVENT 2020)


"When life puts you in a tough situation, don't say why me just say try me".Read it till the end to know why I have mentioned this quotation here.
Round 1 (online round on Mettl platform): 
28 Technical Mcqs 
2 coding 

Round 2(onsite technical): 
1. Find the diameter of a tree when a binary tree is flattened. 
First approach: Finding the lowest common ancestor(which is at the highest level) of two nodes in the left and right subtree, then find the distance between them. This solution cleared only a few cases.

Few questions on different traversal techniques to be used to approach the above problem. It took a lot of time for me to get the logic right. 

Second approach: Finding the deepest node on the left and right subtree and finding the distance between them, maintaining a current distance and max_till_now and always updating the max_till_now whenever current distance exceeds the max value. The interviewer was satisfied with this approach.

And then he gave me some more time to write code that passed all cases. Though my code didn't cover a few edge cases the interviewer was ok with my code as it passed the maximum of the cases(around 80% of the cases).

Round 3(onsite technical): 

1. Given an array find the deflection point. 
The deflection point is a point where an array that has all increasing elements starts decreasing, Ex. [1 2 3 4 17 14 12] 
Deflection point: 17 

First approach: Linearly scan the array and keep checking the previous and next element to find the deflection point.
Second approach: Use binary search to find the mid element, compare it with the first and last element of the subarray and continue searching.
The interviewer asked me whether there's any specific use of comparing it with the first and last element of the subarray.
Then I gave him a binary search+sliding window approach where I'll do splitting based on the above technique while comparison will be with previous and next elements.
The code for the above approach was to be written.

 2. Design a kind of system where for each given user you have to return the recent 5 search page links. Basically, there will be amazon's system that calls my system.

 I used a map where the key is user id and keep storing Page links in values such that if a new page link comes in the least recently used page is kicked out and if it already exists in the list just update the index. 

So the interviewer gave me two function signatures as below:

page_visited(user_id,page_link)
get_recent_search(user_id) 

And  I was supposed to fill them to get the output he expected. 

3. Some tree question which I forgot that simply involved level order tree traversal.

Round 4(onsite technical): 
Before starting he asked me which DS I am pretty confident at. I answered him trees and linked lists. He told me I'll be giving you a problem and let me know if you have seen the solution anywhere.

1. Clone a linked list that has next and random pointers. 

I honestly told him I know the solution and asked him for the next question. He was happy that I didn't lie and gave me the next question.

2. Given a binary tree find the maximum sum of the subtree which is a Binary Search Tree and it should use o(1) extra space. (Recursion Stack space was not included). 

First approach: Find subtree which is BST by taking auxiliary arrays and then return the maximum sum of the array.

Second approach: Without using auxiliary arrays, maintain max and min for checking the range of nodes to predict whether subtree is BST or not and the finding maximum sum.

He was satisfied with my approach and asked me to write code. I wrote the perfect code in 10 minutes which passed all the edge cases( I didn't expect to write this perfect code :P). He was pretty impressed.

3. Given an array where the ith element in an array represents the maximum number of forward moves. Find the minimum number of jumps required to move to the end of the array. 

Ex. [3 4 1 7 8] Since we start from 0th index I can move 1 or 2 or 3 steps in jump 
1. If I move 3 Steps I reach 7 and in 2nd jump itself, I reach the end of the array. 
Another case can be I move 1 step from 0th element reach 4 and then if I move 4 steps forward I have reached the end of the array. In this case, also the minimum number of jumps is 2.
 I gave O(n^2) solution.
He asked me for a better approach. I told him we can store a maximum of the next a[i] elements and determine how many steps are to be taken. 
But I got stuck, asked him for a few hints, it was then when he changed the question to below one. 

4. Given a 2d matrix print in spiral order. The code should be perfect and should pass all edge cases. I missed one of the cases and he straight away said it fails, think and instantly I realized my mistake and fixed the edge case. 

After this round I was asked to leave for the day, I was happy to have made it till here.
I didn't leave the campus yet when I got a call again to come back to the same floor where interviews happened. I went and I was informed out of some confusion I was sent back where they were supposed to send someone else back. 

They asked me to come down again the following day for the last round-THE BAR RAISER. I was literally scared when he told me that it is going to be the toughest of all and you are just one step away from getting into "AMAZON".

Round 5(Onsite technical Bar Raiser Round): 
I reported an hour earlier than the reporting time and the HR met me near the gate. She noticed me waiting for quite long and my interviewer was late by an hour so technically I had to wait for 2 hours altogether.HR called me into her cabin and gave me few tips to excel in the final round.

1. Tell me what makes you "Sirisha"? 
2. Some questions on leadership principles that I have experienced in my career. 
Few follow-up questions from my answers.
3. Given a sorted array and an element x, find the index of kth nearest number in the array from X. 
It was a modified version of the below question.

The nearest element is defined as the element which has the least absolute difference when computed with X.
Ex.[1 3 5] 
 X = 5
 K= 2 
Abs(5-3)=2, Abs(9-5)=4 
so the output to be returned is 3. 

4. What is thrashing? 
5. What is something that I learned on my own? 
6. Why Amazon? 
7. Suppose you have an incoming stream of numbers how would you determine the 5th maximum element at any point in time. 
I told him I will be using a max heap to store the elements and then I will return the 5th element from the root. He asked me when I say millionth element you traverse max heap million times, then it's not a proper solution.
I suggested I will be using a queue implemented as a linked list, he told you were thinking in the right direction, think in terms of the heap and I suggested a solution with min heaps. I can create a heap of 5 elements and keep storing values when I have to return I can return the minimum element in O(1) time.

8. How are hashmaps or dictionaries implemented? And how do I handle collisions? 


I was told that results will be declared in a week and I got my result after 10 days.

Verdict: Selected 

Few tips: 
1. Don't panic and be confident in the interview. Each round lasted for 1 to 1.5 hours so make sure you are not hungry before you enter the interview room. You won't be able to think through the question if you are hungry.
2. Always ask for follow up questions to the interviewer when you are unsure of the question. If you ask questions, they actually start dropping hints. 
3. If you are stuck somewhere let the interviewer know and ask for hints. Few give hints and few won't (like the guy in round 3 was playing PUBG when I was writing code :P) but that's ok. 
4. Preparation or getting code right is not what is important. "Think out loud" so that they know your thought process and the way you approach given a new problem. 
5. Make sure you tell the interviewer the space and time complexity of each approach you provide even if they don't ask you.
6. Practice pen paper coding or whiteboard coding rather than practicing on IDE . You should have enough practice to write code as soon as you get the logic. You will be expected to write code in 15 to 20 minutes that covers all the edge cases too.
7. Preparation material that I would suggest is GeeksForGeeks Amazon archives and Cracking the Coding Interview Book.
https://www.geeksforgeeks.org/Amazon-topics-interview-preparation/


A few questions asked to my friends were from graphs traversal techniques, stacks, linked lists and queues too. Apart from DS and Algorithms, a few questions on Networking, OS concepts were asked to my friends.

Speaking from my personal experience my father was hospitalized because of a heart stroke just a day before the interview. I was blank when I went for round 1 on-site and I almost cried in front of him. He said that it takes courage to come and attend the interview leaving your family behind. Family always comes first and I salute your courage to face the interview. He calmed me down, gave me some water(so sweet of him) and suggested I speak with my parents.Only then was I able to perform in further rounds. 
HR said this line to me when I was in her cabin waiting for the final round, which motivated me further "Keep your personal trauma aside and think of AMAZON for the next few hours".

I'm satisfied with my performance given the state of my mind, I wasn't even expecting to clear round 1 but I'm happy that I made it till the last round. 

I sincerely thank all my mentors, guides, friends who motivated me in this time and also encouraged me to do my best.

I thank my family, mentor ABHIJITH RAVURI annaya for his constant guidance and support during all these 3 years which made me reach this stage. I also take the privilege to thank SRI HARSHA KOMANNA annaya for his constant motivation and pushing efforts to help me crack Amazon since the day MRND course ended.

P.S: For more interview tips and suggestions refer this video on my Youtube Channel.

Comments

Post a Comment

Popular Posts