YOE: 2

Round-1 (Online Test, 90 mins.)

There were 2 coding questions.

1. You are given a list of song durations. You are on a journey and given the journey duration.
   You have to pick two songs that'll finish 30 minutes before the journey. 
   Basically, we have to pick two numbers from the songDurations list that sum up to journeyDuration-30.
   Approach: - Sort the array.- Find target sum with 2 pointer technique.
   https://leetcode.com/problems/two-sum/

2. Given a matrix, find shortest distance from source and destination.
   You can move in only 4 directions(top, left, right, bottom).
   https://leetcode.com/problems/shortest-path-in-binary-matrix/
   Solved it using BFS.

There is a 15 minutes slot after the online test where you have to explain your approach and the time and space complexities for your solution. These things will be asked every time you solve a question in the entire process.

After clearing the online test, I was told that they'll like to move ahead and scheduled 2 interviews on the same day after a week. All interviews were virtual and were taken on Amazon Chime. A link to codeshare is provided for each interview.

For every question asked during the interview, you are expected to write production ready code and explain the time and space complexities.

Round-2 (Technical Interview on Chime, 1 hour)

Without wasting any time, the interviewer moved straight to the coding questions and pasted the questions on codeshare.

1. Given a sorted string, find all occurrences of an alphabet. 
   Explained him the approach and started to code.

   Wrote 2 functions :
   bisect_left(returns the index of first occurrence of the alphabet in string using modified binary search),
   bisect_right(returns the index of the last occurrence of the alphabet from the first occurrence to the end of string using binary search).
   The difference between the last and the first index gives the number of occurrences.

   He asked me to check for corner cases and write comments.
   I wrote the missing corner cases and commented the code. 

   The interviewer did a test run and was happy with my code.

2. Given a matrix, (x, y) is the cell where a person is initially standing. There is fire in some cells.

   Fire is denoted by 0 and safe cell is denoted by 1. The person can move in 4 directions (top, left, right, bottom).
   Write a function which returns True if the person can escape without burning himself i.e. without going through a fire cell, else return False.
   A person escapes, when he reaches an edge cell(not corner cell).

   For this question, I made sure that I cover all the corner cases and write comments before the interviewer points out.

   Approach: Solved using BFS. Created a queue which maintained the possible movement co-ordinates of the person.
   If he reaches any edge cell, return True. Mark each cell as visited as you pop it from the queue or add it to the queue.

   The interviewer was satisfied with my approach but after that he modified the question.
   The modification was that now the fire is spreading i.e. a cell with fire lights up it's adjacent cells in 4 directions (top, left, right, bottom).

   The question wasn't clear to me at first so I asked him for explanation.
   I started to code when we came to a common understanding.

   Approach: Solved using BFS. Maintained 2 queues this time, one for fire cells and another for movement cells.
   Returned True if the person reaches an edge cell. Mark each fire cell, visited cell and movement cell as 0 so that it is not added to the movement queue going ahead.
   Initially added all the fire cells to fire queue.
   In one iteration, add the possible safe cells to the movement queue and then add adjacent cells for fire to fire queue.
   If the value of the cell popped from movement queue is 0 then continue else explore it's adjacent cells.
   Used concept of levels(extra loop for cells at a level) in BFS.

   This question uses same concept as Rotting Oranges.

   Modified my code and after few test runs the interviewer was happy with my solution.

   The interviewer asked if I had any questions for him.
   I had thought about some questions prior to the interview regarding the innovation at Amazon and how each employee contributes to it.
   He answered my questions and the interview was over.

The 1st interview went really well as I solved both the questions.

Key points from the 1st interview:

• Explain brute force-approach first.
• Give understandable names to variables.
• Cover all corner cases.
• Write comments to explain code.
• Keep the time and space complexity in mind.
• Ask for explanation when question is not clear.

Immediately after this I had my second interview.

Round-3 (Technical Interview on Chime, 1 hour)

The interviewer introduced himself and asked me to introduce myself.
I told him about the different projects that I had done and the work in previous company.
I had worked on AWS(Amazon Web Services) so he asked me all the AWS services that I had worked with and to explain one of them. 
I explained about the working of ECS(Elastic Container service).

After this, he moved to the coding questions.

1. Given a matrix of 1's and 0's find the maximum distance from a 0 to a 1.
   Approach: Solved using BFS. Initialize distances for all zeroes to be infinity.
   Add 0 cell to queue if distance is less than already calculated distance.
   Used extra loop for levels in BFS.
   When the queue gets empty, the last level gives the maximum distance.

   Similar to the below question but here we had to find the farthest 1 from any 0.
   https://leetcode.com/problems/01-matrix/

   At first, the interviewer wasn't clear with my approach. So I explained him with an example.
   I started writing code after he understood my approach.

2. Given an unsorted array and two integers k and t, find Ai and Aj such that
   |Ai-Aj| <= t and |i-j| <= k.
   Gave the brute force approach first. For every element in array, check whether there is an element in last k indexes such that |Ai-Ak| <= t.

   The interviewer asked me to optimize the solution.

   After thinking for a minute or two I came up with a more optimal solution.
   Approach: As we traverse the array, maintain another array which stores last k elements in ascending order.
   Find the position of current element in the sorted array and check absolute difference between the preceding and next element.
   If the absolute difference is <= t then return the two values.
   Remove element at i-k from sorted array.
   Time Complexity: O( n log(k) ), where n is the length of given array.

   The interviewer agreed with the approach and asked me to code it.
   After I was done writing code the interviewer did some test runs.
   He found out one loophole in my code. 
   The operation to insert an element in sorted array was of O(n).
   I told him that we could use something like bisect.insort in python but he was not completely satisfied with it. 
   He gave me a minute to come up with another solution but I wasn't able to.

The time for the interview was over till then, so he asked me if I had any questions to ask.
I had thought about some questions prior to the interview regarding Amazon's work culture and product lifecycle etc.
He answered my questions and then the interview was over.

I thought that I won't move ahead as I wasn't able to solve the second question satisfactorily.
But I got a mail in 5 minutes that they'll like to conduct more interviews and that they will reach out to me on phone as well.

Key points from the second interview:

• Be very confident about the things that you have worked on.
• Be ready with scenarios where you had used a particular technology and explain it.(in my case AWS ECS)
• Explain your approach to the interviewer and start coding after he is convinced.
• Never give up and try to find the optimal solution. While practicing DSA, look for the most optimal approach.
• It's fine if you are not able to answer something perfectly. They just want to know whether you are thinking in the right direction or not.

They called me within two days and told me about the process ahead.
I was told that there will be 2 more interviews - Hiring Manager round and Bar Raiser round.
I was also told to prepare for Amazon Leadership principle questions.
The 3rd interview was scheduled after 3 days.

Round-4 (Hiring Manager Round on Chime, 1 hour)

The interviewer was a very senior person with at least 10-15 years of experience.
He introduced himself and asked me to tell about myself.(Leadership principle questions followed)

I told about my college projects, the technology stacks that I worked on and the work in my previous company.
He asked a lot of questions about my college projects.
Be very clear and ready to explain your projects in depth.
Asked about the challenges that I faced and wanted to know the most difficult challenge and how I solved it.
He then asked me about the improvements suggested by me in my previous company.
He asked me why I want to leave my previous company.

This discussion went on for a long time. He was checking whether I really knew what I was talking about. People with experience can just see through you.

The leadership principles are very important and have a lot of weightage. They are very serious about these questions. Prepare well for these questions. Have some scenarios in mind. 

Most of the time for the interview was taken up by the discussion.

He then said that, let's do some coding and pasted a question on codeshare.

Given a binary tree, identify whether it is a special tree.

Special tree - When a tree is folded from middle, every node overlaps with another node.

Approach: Solved using DFS. Similar to mirror trees.
Pass root.left and root.right as arguments to the is _mirror_tree function.
First explained the approach to the interviewer. He was satisfied and asked me to write code.

After I wrote the code, he asked me the time and space complexities and whether the solution is the fastest solution.
He asked me to enhance my code, which I did.(Traverse right subtree only when left subtree returns True)
Also commented the code.He accepted the solution and asked me if I had any questions. 

I asked him questions about the team that I was applying for, the division of work in the team and some more questions about the software development lifecycle. 
He answered my questions and the interview was over.

Key points from the round:

• Be very clear about your past projects and work.
• Prepare scenarios for leadership principle questions.
• Ask questions. It shows that you are interested in the job.

The fourth and the final interview was scheduled 10 days after the third interview.

Round-5 (Bar Raiser Round on Chime, 1 hour)

The interview started with introductions and some Leadership principle questions.
The interviewer was again a senior person with at least 10-15 years of experience.

I was asked to explain about some AWS services.
He asked me to tell about a time when I had a tight deadline and how I worked during it.
He asked me about a time when I took initiative and came up with something new which helped the entire team.
I had prepared well for the LP questions and was able to answer everything.
After this we move on to coding questions.

1. Given a list of sentences or lines, create an index to get the lines in which a word is present.
   Discussed the solution using hash map. He was convinced and asked me to code.
   I wrote a well-commented code and he was happy with it.

2. How will you implement an LRU Cache?(Common question)
   I had solved it earlier and explained him the approach using doubly Linked List and Hash map.
   He was convinced with my approach and asked me to code it without using any in-built data types. He asked me to write classes. I had prepared the solution with classes and started writing the code.

   He kept asking me about every line as I was writing it. I explained him well.
   He also asked about some OOPs concepts like Polymorphism as I was writing classes.

As we were discussing while I was writing the code, the time for the interview was about to end.
He said that he is satisfied with my code and stopped me before I completed it.

He asked if I had any questions for him. I asked about the daily work at Amazon and how teams at Amazon adhere to deadlines keeping in mind the SDLC.
He answered the questions for some time. He then wished me luck and the interview ended.

Key points from fourth round:

• Practice the commonly asked questions well.
• Solve as many questions that you can from LeetCode.
• Be very confident in whatever you say.

After this round, I got a mail followed up by a call after 3 days that I'm Selected.
I wasn't able to believe it. It felt surreal. It took quite some time for that to sink in. I was very happy.

Tips:

• Prepare the Data Structures & Algorithms well. They'll be asked in every round.
• The language in which you code does not matter.
• The Leadership Principle questions are very important. Prepare well.
• Be confident. It should reflect on your face.
• Do not give up. If you have worked hard for it, you'll get it.
• If you are well prepared, the entire process seems easy and you gain confidence as you go through the process.
• Solve Medium & Hard level problems. Easy problems don't help.

Preparation
For people with jobs, it can be tough to dedicate time for studying. What helped me was that I stayed at home during the lockdown and got some extra time and didn't get exhausted after the job hours.
It might seem like you have read the below points many times but that's what needs to be done. There is no other secret ingredient.

• Start with the basics if you have lost touch with competitive coding. Don't directly jump to interview questions.(Platforms like GFG and Hackerrank help a lot)
• Create a time table and set goals. Keep aside 3-4 hours for studying.
• Solve at least 2-3 good questions each day. Don't take long breaks.
• Focus on medium and hard questions. Solving a lot of easy questions doesn't help.
• The most important thing is "CONSISTENCY".
• When solving questions on Leet Code, look for the most optimal solution.
• Try to get the code right before a lot of submissions.
• Make a habit of covering all corner cases.
• Don't solve the related questions suggested by Leet Code one after the other.
• Sort questions by topic if needed.
• Prepare topics like DP, Trees, Graphs well.
• Filter questions by company for which you will be interviewing.
• Thers's no substitue to hard-work.
• Everything seems easy once you are prepared well.
• Be patient. You'll get there.

Journey

• 6.28/10 CGPA in college. Enjoyed college life. Was very bad at competitive coding.
• Had done some good web and android projects in college.
• Did a lot of full-stack development freelancing jobs.
• Fortunately got placed in a MNC with decent package.
• The initial 6-7 months were good as I got to know about the working of the company and the SDLC.
• Got introduced to some good new technologies.
• But after that, I didn't have any significant work for almost a year. Didn't write a single line of code.
• Decided to switch.
• Gave some tests but wasn't able to clear any of them. Was very weak in DSA.
• Decided to start fresh and started learning DSA again.
• Started with the basics. Solved questions on GFG and Hackerrank initially.
• When I thought that I have good command over DSA, I started interview prep on LeetCode.
• It all happened during lockdown and so I got extra time due to WFH.
• Was preparing with one of my friends. We gave targets to each other. Studying together helps.
• Applied to thousands of jobs. Most of them didn't reply, some rejected me due to my CGPA, some didn't match my comp requirements and some rejected even after good interviews. It was very disheartening. Job search really exhausts you. It tests your patience. Felt like giving up on a lot of occasions.
• Had applied to the job at Amazon through the jobs portal. Didn't get any response for at least a month.
• One of the recruiters noticed my profile on Naukri. My profile matched the job role.
• The process took nearly a month.
• But I finally got there.

It took me 7 months from the time I started fresh and 1 year after I decided to switch to land this job.

Special thanks to LeetCode. The platform helped me a lot in my preparation. Hope this article helps others.

"The more you sweat in practice, the less you bleed in war!!"