Amazon SDE-II | Phone screen round experience.
Summary
I recently had a phone screen round for an SDE-II role at Amazon, which primarily focused on Data Structures and Algorithms. I tackled two sliding window problems, demonstrating various approaches and discussing their complexities. I felt positive about my performance and am expecting an Inclined verdict.
Full Experience
I began the interview with my introduction. The interviewer then presented a DSA problem: "Calculate sum of each subarray of size K for an array." I first outlined a brute-force solution and then proceeded to optimize it using the Sliding Window technique, clearly explaining the time and space complexity. I also re-iterated and dry-ran various edge cases to ensure the solution's robustness. I was not required to compile the code.
The follow-up question was to "Return max of each window instead of the sum." For this, I offered three distinct approaches:
- For distinct elements, I suggested using a sliding window combined with a set to track window elements and a maxHeap to find the maximum. I explained how to handle
heapPop()if the max element is no longer in the window. - For non-distinct elements, I proposed using a map instead of a set to maintain counts, ensuring
heapPop()is done only when the count of the max element is zero. - As a more advanced option, I mentioned using a segment tree to efficiently store the array and query the maximum of each segment.
Towards the end, I asked the interviewer a query regarding the typical range of work and responsibilities for this role. My expected verdict for this round is Inclined.
Interview Questions (2)
Sum of Subarrays of Size K
Given an array and an integer K, calculate the sum of each subarray of size K.
Maximum of Each Sliding Window
Given an array and a window size K, return the maximum element of each sliding window.