Amazon SDE II Intern | Coding challenge | Interview experience | August 2024 | [Offer]
Summary
I successfully completed my Amazon SDE II Intern interview process, which began with an online assessment featuring two coding problems, followed by an interview round that included two more Data Structures and Algorithms questions. I performed well in all stages and ultimately received an offer.
Full Experience
My recent journey to secure an internship at Amazon was quite fulfilling. Although I had attempted 12-15 online assessments for various companies without being shortlisted, Amazon was the first where my online assessment performance led to an interview invitation. I managed to clear the entire process in a single attempt.
ONLINE ASSESSMENT (2 questions, 70 minutes):
The online assessment consisted of two coding challenges that I had 70 minutes to complete.
The first question asked me to select a prefix of any length from an array and decrement each element in that prefix by 1, ensuring no element became negative. The goal was to count the maximum number of zeros after all possible operations. For example, given [3,2,4,4,1], the output should be 3. The explanation involved transforming the array through prefix decrements: [3,2,4,4,1] -> [2,1,3,3,0] -> [1,0,2,2,0] -> [0,0,2,2,0]. I had to achieve this in O(n) time complexity, and while thinking of the optimal solution was challenging, I luckily figured it out during the exam.
The second question was about an array of strings and a threshold value. I needed to count the number of segments that had a vowel count less than or equal to the threshold. For instance, with ["lciy","ttrd","aod"] and threshold = 1, the output is 3, as segments like ["lciy"], ["lciy","ttrd"], and ["ttrd"] meet the criteria. This problem was relatable to 'Find the Number of subarrays having sum less than K'. I solved this using a brute force method with O(n2) time complexity.
I successfully solved both questions and was subsequently shortlisted for the interview round.
INTERVIEW EXPERIENCE:
The interview started with a basic introduction, after which we immediately moved into Data Structures and Algorithms questions.
The first question was an easy string problem from GeeksforGeeks, but with a slight modification. The string would only contain lowercase letters, and if a character occurred more than 9 times, I had to return '9' followed by that character, then continue counting. For example, "aaaaaaaaaaaaaabbeee" should yield "9a5a2b3e", and "abcde" should yield "1a1b1c1d1e". I solved this correctly in a single go using an O(n) approach, finding it pretty simple and straightforward.
The second question was exactly 'Check if leaf traversal of two Binary Trees is same?', another GFG problem. Initially, I proposed a wrong approach using level order traversal. However, the interviewer helped me realize my mistake by providing another sample case. This allowed me to figure out the correct approach, and I successfully coded it.
The interviewer seemed quite impressed with my solutions and indicated he had no further questions for me. He then asked if I had any questions for him. I asked, "What is the definition of a good code according to you sir? When a student writes a code what are the key elements that you look into?"
He provided a thoughtful answer, and then informed me that the recruiting team would update me on the next steps, concluding our meeting.
I GOT HIRED!!
Interview Questions (4)
Select prefix of any length from an array and decrement each element in that prefix length by 1. Make sure no element becomes negative. Count maximum number of zeros after all possible operations.
Sample case: [3,2,4,4,1]
Output: 3
Explanation: Select prefix of size 5, [3,2,4,4,1] -> [2,1,3,3,0]. Now choose prefix of size 4, [2,1,3,3,0] -> [1,0,2,2,0]. Now we have to choose prefix of size 1 because 1st index will become negative if we try to make further elements smaller... [1,0,2,2,0] -> [0,0,2,2,0].
Had to do this in time complexity of O(n).
Given an array of strings and a threshold value count the number of segments which have count of vowels less than or equal to the value of the threshold.
Sample case: ["lciy","ttrd","aod"] , threshold = 1
Output: 3
Explanation: Segments with vowel count less than or equal to 1 : ["lciy"],["lciy","ttrd"],["ttrd"].
Relatable question: Find the Number of subarrays having sum less than K using C++ (tutorialspoint website)
This was an easy string GFG question with some modifications.
Modifications:
i) String consisted only lowercase letters.
ii) If a character occurred more than 9 times then we have to return "9" + "that char" and continue counting again.
Sample case 1: "aaaaaaaaaaaaaabbeee"
Output: "9a5a2b3e"
Sample case 2: "abcde"
Output: "1a1b1c1d1e"
Check if leaf traversal of two Binary Trees is same? (GFG question). This was the exact same question asked.
Preparation Tips
Before getting shortlisted by Amazon, I faced several rejections, having given around 12-15 online assessments without success. This experience drove me to focus intensely on my preparation, particularly for coding challenges. I ensured I practiced enough to confidently approach problems, aiming for optimal solutions where possible, but also understanding when a brute-force approach was acceptable given time constraints.