Mock Amazon Interview | Amazon Software Engineering Technical Interview | Amazon Interview Questions

Key Takeaways

Hello. Is this a Jud? Hey. Yeah. Hi. How are you? I'm doing pretty good. Well, my name is Neil. I'm a senior software engineer here at Amazon and I'm going to interview today. I just wanted to start out with a few introductory questions and then we're going to head straight into the technical portion. Does that sound good to you? Yep. Sounds great. All right. Uh, so how about you tell me a little about yourself? What got you interested in Amazon? Yeah, sure. Sure. As you know, my name is Sad. I am currently a computer science major at Georgia Tech. This past summer, I actually interned at Amazon as a software engineering intern, and that got me a lot of exposure with AWS cloud computing and automating data pipelines through the different AWS resources. Also, I have prior experience working with Python as part of a research project working with genetic algorithms as well. And with that being said, my top two programming languages are Java and Python. And so what really got me interested in Amazon, the fact that you guys use a lot of AWS cloud computing and that's something that I have prior experience with that I really want to explore further. Cloud computing really is the future and it's something that really intrigues me. I feel an internship at Amazon would give me the right step into the future. Wow. Okay, that sounds amazing. Um, so let's head into the coding interview. Um, so could you log into the coding platform? Yeah, just give me one second. All right. So, this is coderpad. This is the platform we have here. I'm going to paste a question and then I'm going to give you some time to read over it. Does that sound good? Yep. Sounds great. You can pick any coding language of your preference. All right. I am going to go with Python. All right. So, given an array of integer nums and an integer target, return values of the two numbers such that they add up to target. You may assume that each input would have exactly one solution and you may not use the same element twice. You can return the answer in any order. Okay. Essentially, you're looking for given an array to see if two numbers add up to a target and kind of returning those two numbers. Is that correct? That's exactly right. All right. All right. Um is it possible I could see some sample inputs and outputs just so I can like visualize this a little better? Yeah, sure. So you see this input and output I pasted onto the code. So for example of how this program should work is we have a target of nine and we want two numbers in this array whose sum is nine. And as you can see the output is two and seven because these two values are in the dums array and their sum is nine. Does that sort of clarify the problem to you? Yeah, that makes sense. That makes sense. All right. So um what comes first to my head and I know this is kind of like a brute force like naive solution iterating through the array upon each part of the iteration kind of doing a subiteration to search for an element that complements it to get to the target. How this would play out for the example that you gave is starting out with 2 7 11 15. So iteration 1 2 then in our nested iteration going to 7 11 and 15. But in this case it would stop immediately because it would recognize 2 + 7 = 9 and just return uh 2a 7. Okay, this is a good approach. So what would you say the space and time complexity of that approach is? Um, so the time complexity certainly would be O of N squared because we're going to have like a nested loop each one to N. So that's going to be N squ. And with regards to space that this algorithm actually doesn't take up extra space. So it's going to stay at a O of one space complexity. Exactly. Yeah. So why don't we start out by implementing the solution that you have? Yeah, sure. Sure. Um, and I'll just code it out. Uh, we're going to pass in nums and we're going to pass in target. Is there a specific thing that I should return? If the target sum doesn't exist, you can just return a list of negative one. Okay, sounds good. So, this is my solution. it does a nested iteration and in the case that the solution exists, it will certainly find it in an O of N squ time complexity. This is kind of the brute force solution I was able to develop. There are certain things I feel like I could do to optimize it, right? Uh why don't we go over those uh ideas that we have potentially to optimize this code because we are dealing with numerical values and we're trying to target a specific sum. I feel like if we're able to sort it kind of like in a lowest to highest just like smallest number to highest number order I feel like that may be beneficial to discovering that target. How would the ascending order of the numbers help you solve the problem? This situation we have here 2 7 11 and 15. If we set up a pointer to be at two and a pointer to be at 15 just like a reference to both of those variables. we sum them up and we check if the sum is equal to target. If it's equal, we return right there. Um, but if it's greater than our target, then we decrement the right pointer down so that we have 2 + 11 and then we decrement again and we'll get 2 + 7. Now, the case that it's less than, uh, the numbers we're adding are too little. So, we have to increment from the left pointer. That's kind of what I'm thinking. I like this approach. Why don't you tell me a little bit more about the time and space complexity of it? The best case scenario we can get is a time complexity of N log N because that's kind of like the best case scenario with sorting and I believe we can get the space complexity to O of one kind of like using the best sorts out there. Sure. Why don't we go over how this would look like in code? Yeah, sure. Sure. This is good this n login solution but there is another optimization that can be done on top of this. Let's see if we can take it down from O of N log N to O of N. Just to give you a little hint as to what I'm sort of looking for. um when we inspect an element of the array, we don't want to be looking at it more than once and we want to store it in some data structure that but we might be able to retrieve it quickly without looking at it in subsequent iterations. I I I get what you're saying like for example in my brute force solution I look over it many many times even this uh solution because I'm like sorting it I have to deal with it once and then actually use it to solve the problem as well. So you mentioned storing things that we've visited before. I I I think I understand that solution. Um things that we could use to store for quick retrieval. We can use Python's use of hashing with a hash set. Say we have that input nums that you gave with 2 7 11 and 15. If we iterate through the array, add each thing to the set if it hasn't been visited yet, and see if the target minus the element we currently are on plus the other element equals target. Sorry if that was a little confusing, but I I think I see how to go about this. Uh, you're you're actually right on the money with that with that solution. While you're at it, what do you think the time and space complexity of the solution would be? We'd only be visiting each element maximum ones. The retrieval adding and removing to any like hash set type thing is all O of one. So I think it's actually going to be O of N uh time complexity. But because we are taking an increase in space for each subsequent element, that's going to be an O of N space complexity. Right. Would you like to start by coding out the solution? So first thing I'm going to need is a visited set uh to maintain the elements that I've seen. So we have to now iterate through. So do first for numbum in nums. So I need to check if the target minus num exists within the set. So like for example if we're we're pass to we're on seven if 9 minus 7 exists within the set already. I know in Java how like we do set we check if it's in the set we do like if visited set contains like we do something like visited set contains target minus numbum I'm not sure if that's how it works in Python is that something you can check yeah of course so in Python it's a very similar concept except we use the keyword in to check if target minus num is in the visited set for example we would say target minus num in visited set and that would correct we oh okay okay that makes sense yes sorry sometimes I mess up the syntax don't worry about it too much we mainly just check for understanding of algorithms and I believe this is the correct solution and it actually looks much simpler than I thought it would great yeah let's give it a run and see if it works yeah I'll just print get sum nummed comma target. Let's run this. We got 7, 2. Is that cool? Outputs a 2a 7. Perfect. The order doesn't matter for the solution. Awesome. So, let's try it on another input. Let me copy over replace the nums. 3 2 4 and 6. Okay, let's run this. We got 4, 2, and 4 + 2 equals 6. So, I think it's correct. Perfect. You did an awesome job today. So, Jud, we're all done with the coding portion. Now I I just wanted to open the floor to see if you had any questions for me. Yeah. Yeah. Um certainly. So one question I had a little about Amazon and like your experience. How would you describe culture at Amazon, especially with everything being virtual and all that? How are things holding up? Oh, it's it's awesome here. Uh I'm very fortunate to have an amazing team. Uh they're very supportive. We have a lot of fun together um and have virtual social events and the work life balance is great. We have plenty of time to get our work in, but also enjoy time together outside of work. Sounds good. Um, so that's about all the questions I have. Well, I had a great time talking to you today, Sad, and thank you so much for doing this interview. I hope you have a good rest of your day. Yeah.