Amazon Interview Got Tricky When I Was Asked to Explain My DSA Approach

Company: Amazon

Role: SDE Intern (6 Months)

Interview Mode: In-Person (Onsite)

Round: 1

The interviewer didn't jump directly into coding. We started with my resume and project experience, followed by two DSA problems that required me to think through different approaches and explain my reasoning.

Here's how the interview went.

1. Resume Discussion & Leadership Principles

We began with my resume, and the interviewer picked one of my projects, PlaceMate AI, to start the discussion.

The first question was:

Q. Tell me about a situation where you demonstrated ownership.

I used my PlaceMate AI project as an example and explained what motivated me to build it, the problem I wanted to solve, and the responsibilities I handled during its development.

The interviewer then asked a few follow-up questions:

• How much time did you spend building the project?

• What was the most challenging technical part?

• How did you gather and manage placement-related information?

I explained that collecting information from different sources, especially WhatsApp conversations, and converting it into properly structured data was one of the biggest challenges.

This part of the interview focused on understanding my contribution, decision-making, and the effort behind the project rather than just knowing its features.

2. DSA Round

After the project discussion, we moved to coding problems.

Question 1: Minimize Array Sum After X Operations

The problem was based on an array where each element represented a weight.

In one operation, I could select any element and replace it with half of its current value. I had to perform exactly X operations and minimize the final sum of the array.

Example:

arr = [2, 5, 10, 23]

For instance, I could select 10 and reduce it to 5 in one operation.

My approach:

Initially, I thought about sorting the array and repeatedly selecting the largest element.

However, after discussing the approach and getting a hint from the interviewer, I realised that the largest element could change after every operation. Re-sorting the array each time wouldn't be an efficient solution.

That's when I moved towards using a Max Heap (Priority Queue).

The approach was:

1. Insert all array elements into a Max Heap.

2. Perform X operations.

3. In every operation, remove the largest element from the heap.

4. Reduce its value to half and insert the updated value back.

5. Once all operations are completed, calculate the sum of the remaining elements.

The interviewer agreed with the Max Heap approach.

Complexity discussion:

We also discussed the time complexity of different heap operations.

Some important operations to remember:

I got a little confused while explaining some of the complexity details, so this was definitely something I felt I could have handled better.

Question 2: Word Break / String Segmentation

The second problem was related to string segmentation.

We were given an array of strings:

["catdog", "cat", "dog"]

The task was to identify strings that could be broken into smaller strings, where each smaller string was also present in the given array.

Example:

catdog = cat + dog

My approach:

I recognised this as a variation of the classic Word Break problem.

I suggested the following approach:

1. Store all the given strings in an unordered_set so that we can perform efficient lookups.

2. Use recursion to explore different ways of splitting a string.

3. Check whether the generated substrings exist in the set.

4. If a valid combination of smaller strings is found, consider the original string segmentable.

The interviewer then asked me to write the implementation again on a fresh sheet.

While explaining and rewriting the code, I struggled a little with handling substring boundaries and deciding the recursive choices correctly.

We also discussed the time complexity of the basic recursive solution and how it could become exponential because of the repeated exploration of possibilities.

This question made me realise the importance of being comfortable with recursion, substring handling, and optimising recursive solutions.

3. Questions I Asked the Interviewer

Towards the end, the interviewer gave me an opportunity to ask questions.

I asked two things:

• What kind of responsibilities and goals does Amazon expect an intern to achieve during the six-month internship?

• With AI evolving so quickly, how do you personally keep yourself updated and continue learning new things?

Both questions helped me understand more about the internship expectations and the engineer's approach to continuous learning.

Overall, the interview covered three major areas: project ownership, Amazon Leadership Principles, and DSA.

The two coding problems tested different problem-solving skills:

• Max Heap / Priority Queue: Selecting and updating the maximum element efficiently.

• Word Break: Recursion, string segmentation, and Hash Set-based lookups.

• Complexity Analysis: Understanding the time complexity of individual operations and the complete solution.

The project discussion was equally important. The interviewer wanted to understand why I built PlaceMate AI, what challenges I faced, and how much ownership I took during development.

A few things I would recommend based on this round:

• Be prepared to explain your motivation, technical decisions, challenges, and individual contributions.

• Don't just practise problems; understand the complexity of every operation.

• Try solving the problem using recursion first, then improve it using memoization or DP.

• Pay attention to substring boundaries, recursive conditions, and edge cases.

• Even if your initial approach isn't optimal, communicate your reasoning and be open to hints.

That's how my first Amazon SDE Intern interview went. It was a good learning experience, and I came away with a clearer idea of the areas I need to improve.