Round 1 Coding and Problem-solving (1 hour)

Question 1: Longest Valid Parentheses

I contemplated employing a stack and was familiar with the method of validating parentheses expressions (pushing an opening bracket and popping on encountering a closing bracket, ensuring an empty stack signifies a valid expression). Initially, I proposed a brute-force approach, examining every possible substring (N² substrings) for validity, resulting in an overall complexity of O(N³).

Upon the interviewer’s request for a more efficient solution and the provision of a few hints, I successfully devised an O(N) solution using a stack. The concept closely resembled the one employed to verify whether a string constitutes a valid parentheses expression or not.

The interviewer asked he we could solve this problem without using additional space. I provided a few ideas but could not provide a solution using constant space.

Question 2: Rotate image

In this problem, I was able to use additional space of the same size as a matrix. The interviewer asked if we could solve this problem in place. I gave enough thought but was unable to devise a constant space algorithm. Due to time constraints, the interviewer asked me to implement the solution I provided.

Back in 2017, I was working at a startup, and things were not going well. We were unsure if the company could secure the next round of funding. Due to numerous financial obligations, I decided to move on.

I contacted a recruiter at Amazon who had been part of my previous Amazon interview process in 2016 (when I received an offer for an L3 role). I got to know that he left his job at Amazon. So, I reached out to a few random technical recruiters of Amazon I found on LinkedIn. Fortunately, one of them responded. When he inquired about my availability for an interview, I requested at least 2 weeks to prepare, which he agreed to.

Back then, Amazon was actively recruiting, and conducting hiring events on weekends. If you received an invitation for an in-house interview, you had to go to their office and complete all the interview rounds in a single day. They used to provide lunch to all the candidates. Those face-to-face interactions were enjoyable, and I find myself reminiscing about them, especially since they were replaced by virtual online interviews post-COVID. I miss those in-house interviews.

My preparation:

In 2017, with just two weeks before my interview, I reconnected with Data Structures and Algorithms (DSA). I kicked off my prep by tackling recently asked Amazon interview questions.

Recognizing that each round of an Amazon interview delves into 1 or 2 Amazon Leadership Principles, I made sure to integrate them into my preparation.

Admittedly, I wasn’t aware of system design resources back then. I caught up by delving into Amazon’s system design interview questions from GFG and Leetcode, discussing them with mentors and friends.

I’ve also compiled notes to articulate my projects and highlight compelling situations from my career. This preparation has equipped me for situational-based questions related to Amazon Leadership Principles.

Gave a few mock interviews.

Screening round:

The recruiter provided a HackerEarth link containing three coding questions to be solved within 1.5 hours. If you’re acquainted with platforms like HackerEarth and HackerRank, you’ll be familiar with the types of problems typically presented in screening rounds. It’s crucial to solve the problems within the specified time limit and ensure that all test cases pass.

I was able to solve all the problems in time.

After 2 days recruiter sent an email inviting me for an onsite interview at the Bagmane office in Bengaluru.