Python Interview with an Amazon engineer

Watch someone solve the partition equal subset sum problem in an interview with an Amazon engineer and see the feedback their interviewer left them. Explore this problem and others in our library of interview replays.

Interview Summary

Problem type

Partition Equal Subset Sum

Interview question

Given an array of positive numbers, determine if the array can be split such that the two partition sums are equal.

Interview Feedback

Feedback about Verdant Gyroscope (the interviewee)

Advance this person to the next round?

How were their technical skills?

4/4

How was their problem solving ability?

4/4

What about their communication ability?

4/4

You have amazing problem solving skills, You were able to quickly see through the problem and come up with a relevant approach, Your execution speed was phenomenal and you handled the follow up question quite well. You didn't panic when you weren't getting the desired output but instead calmly debugged through the issue. I was particularly impressed by your ability to quickly translate your idea in to code.

Feedback about Atomic Snow (the interviewer)

Would you want to work with this person?

How excited would you be to work with them?

4/4

How good were the questions?

4/4

How helpful was your interviewer in guiding you to the solution(s)?

4/4

Great interview experience!

Interview Transcript

Verdant Gyroscope: Hello?

Atomic Snow: Hello.

Verdant Gyroscope: Hi.

Atomic Snow: How you doing?

Verdant Gyroscope: Good.

Atomic Snow: Awesome. So let's start with introductions, then we'll jump on to the coding question and get through that question. We can then try doing another one. Okay, Does that sound good?

Verdant Gyroscope: Yeah.

Atomic Snow: Awesome. So I am a backend distributed systems engineer, I basically work in one of the cloud based internet companies. So do you wanna introduce yourself?

Verdant Gyroscope: Yeah, I'm a rising junior in college, University of Pennsylvania, studying computer science. And I'm preparing right now for, for coding interviews, for the internships I'll be applying to this fall for the summer after my junior year. So yeah, that's where I'm at. I've done I've been practicing pretty intensely for the past, like month or two, I would say, but I have a fairly long history of like, doing coding projects, and then study, I'm studying computer science. I would say I'm like, at an intermediate level.

Atomic Snow: At the intermediate level, awesome. Yep, that sounds great. Okay, you will, I'm pretty sure you'll be able to get your like more than one internship, cutting this down. So this will offer that. Thank you. Alright, so for today's coding question. Let's suppose you are given a list of positive integers. And we want to check if it is possible to break that set, or that list into two subsets such that the sum of both the subset is equal.

Verdant Gyroscope: The sum of you say positive integers?

Atomic Snow: Yep, so for example, I'll just write it out here. Suppose your set is something like this. We just want to make sure that if you sum it up this set, this becomes 12 to 14, so is there a subset which can sum up to seven. So in this case, I say if I break it into this way, like one subset has four threes, and the other one has 511. So we know that it is possible to break it in such a way that the sum of both the halves are equal?

Verdant Gyroscope: Okay. So I'm thinking, the first thing is, if we sum up all of the numbers in the in the set? We get that total, then we're looking for any subset that matches the total divided by two, I guess.

Atomic Snow: That's right. Okay.

Verdant Gyroscope: All right. So I think one strategy here would be to write a function to try and find a subset matching a target value. And I guess like our top level function, we'll just use that function in passing the sum divided by two. And I think the way the way I would go about implementing that function to find the subset that summing up to a target value is so I think if we have like a table where the rows correspond to like, the target value, if it's a positive integer, and so that those would go from like, one to the sum divided by two, I guess. And then the columns would correspond to like, a slice, or like a partition in the, in the list. And like, we can assume that, like, we have access to the elements up to and excluding that, that index, and then and then I think there should be a way to kind of express the optimal value kind of like in a bottom up approach code, you know, iterate through the table and set each each entry of the table row using the values of previous entries. So that's, I would say that's the main approach. That would be like I guess, if S is the sum of all the elements in the in the list and the complexity of that... The time complexity would be like, O(s*n) where n is the length of the list. And the space complexity would be the same. So I'll try to implement that. So I see. Yeah, so I'm thinking the tables initialized to, this is just initializing each of the rows. But where each row only has one element to start with, because the when the column is zero, that means that our slice of the list is like empty. Actually, I guess they should think about what's in about the contents of the table. So it's going to be like, I guess, like a Boolean, indicating whether indicating whether that like that there is a subset of that section of the array, which sums to that target. So yeah, I guess like if the target is zero, then it's going to be true, but for all others, it's going to be false.

Atomic Snow: Right? So how it will help you in figuring out whether, let's suppose even if you have an answer for a subsection of your input, like is there a way I can use that to build an answer further, because in this case, it will only tell you like, this is not possible to reach up to target. But it wouldn't indicate in any way that if I can use that information to deduce that if I take further elements will will it help or not?

Verdant Gyroscope: Yes, good point. So I think maybe,

Atomic Snow: Is there any merit in storing just the sum? Like if I can use... Okay, you summed up to x, and I am, let's suppose five. So I know if I include myself, I'll be x plus five, that may or may not match my target, but at least I'll be able to deduce what is possible using what that information?

Verdant Gyroscope: Yeah, that's a good point. What I guess like, would it be maybe like the closest value to the target? Because then like, there is a way to say like, whether, you know, when you're taking this step, I guess, should I include this new element or not? Like if it is closer to the target than you should? And then like, like, if it's feasible to actually reach the target, then the value will equal to the target, and then you can say it's true.

Atomic Snow: So going back to one step further, if you're saying we'll, we will take the element if it takes you closer to the target. But that condition will always be true because you have positive integers through either get closer to target or you will over.

Verdant Gyroscope: Right. But yeah, I guess is that is that a problem? It doesn't seem to be a problem to me because like...

Atomic Snow: Yep, shouldn't be a problem. Which are sorry, when you say, I think that shouldn't be a problem. If you use it in indicate to this way, like you can maybe explore both the path and see where it leads. Because you only have to check does any one of these paths leads to having that target? achieved if it is you're done. If it isn't, then you know for sure. There isn't a way to achieve that.

Verdant Gyroscope: Yeah. So yeah, I guess it isn't, like say like, even if the first like three numbers, you know that the like, I don't know, say the target is, is like, like, I guess with these first three, that is kind of not a good example. But like the first like, you know, however many elements of your list, if you knew that, you know, a subset of them some to some number, and that was as close to the target is possible. I guess the problem is, when you're taking a step, it's not just a constant time thing to check. Like, because, you know, when you're including that new element, I guess it could be the case that the subset of the previous elements would be different.

Atomic Snow: That's true.

Verdant Gyroscope: But I guess it's like, since you have the table, like, what you want is the subset of the previous elements that's as close as possible to the target minus the element you're adding? And if that's like, if that number is closer than not including that element, and just including like, Okay, I think, I think it'll be, I think I have some sort of idea for how to implement this. So I'll try and like, explain as I'm going, and hopefully it'll work out, but I guess I'll see. But, but yeah, so then, what is your these and then I'll say, like four, like, I guess, four partitions. In range. Actually, the partition will be just the range, like the length of the array. And then we'll say, four. Then like, so I guess the actually, maybe it's a better idea to go. Like this. So then, in this like, here, we can just append to the list. And then basically, like, T. So the so the new element that we're considering adding is array minus one. And so we'll say like, the closest like value, if we included would be... I guess like, Oh, yeah, up here we can say...

Atomic Snow: Yep, and that's a great addition.

Verdant Gyroscope: I'll say like final final target is x over two so. So the final target is what we're trying to like, achieve. And then so closest if we include it would be final target, minus new element. And then the part and then it would be partitioned by minus one. If and I guess we have to check like if this is greater or equal to zero else negative 30 so it's like, Yeah, actually, well, I guess it's not. Yeah. Cuz like if the optimal value for, like a target being final target minus two element partition being partition minus one. If that. Or I guess if final target minus new element is less than zero, then it could be that. Yeah, that gets like, you know, if we were actually solving the problem where we were trying to get as close as possible, then we would want to, like consider that case, like, maybe it's better to be, you know, if it's, if it's overrun slightly, then that's closer. But I guess we don't care about that case, because it's always gonna be false. In that case, right? And we want to if it overruns, we want to just ignore it. And yeah, I think that should be if we get so close. Oh, but it's so it would be that plus new elements. And then if we don't include it, it would be just that and we don't need this case. So that we can say T of target. Partition equals causes, if not included the period is less than actually, I think this should be target. Yeah. So and then at the end, who would like to return? Final target length array equals final target. So I have to like review this to see. Okay, so yeah, so one thing that we have to do actually, is because the way we set up the table, we have to append instead of setting. And then let me see. So close it. If we include it, then the closest we can get is like whatever the optimal subset was to reach the target minus the new element using only the values from like, the partition minus one sub array. And then and then you add new element to that like closest sum. If the like, if new element is less than or equal to the final target, and if the element is greater than the final target, then we definitely don't want to include it.

Atomic Snow: It's a false like, including it wouldn't really give you the answer in that subject.

Verdant Gyroscope: Right. And so, yeah, so... So in that case, we just say like the closest sum is like negative infinity, which is or continue with the find like, it's not going to be it's going to choose because it does not include by the way, and then if we include it, it's just the same target, actually. Okay. So yeah, just to make. Okay, yeah. So if the target milestone is greater than zero, and then if we don't include it yet, it's the same target and just partition minus one. And we're not adding anything. Then we say, the row corresponding, like the target row append. Closest, if not include, if that's closer than closest, if included yet is that goes to the closest include. And I think because we're, we're saying like, it's always going to be less than the target, we could do like, target minus closest, if not include. That would be fine I think.

Atomic Snow: Do you want to like, call this metric from a function, and just...

Verdant Gyroscope: yeah, so let's see. So this one should be true.

Atomic Snow: This should be... False. Sorry, yeah, true.

Verdant Gyroscope: So yeah, 5435. And then I'll do like, I guess at the end, I'll do some edge cases, like the empty array. Technically, is true, I think. Because, wait. Yeah, I mean, I think like the trivial sum is generally considered zero. So you can split it up into like, two empty pieces, where they both sum to zero. And then, just like, that should be true. And that should be false. Should be true. Oh, yeah. I'll just run these and then from there. Oh, yeah. My bad. Okay, so it looks like it matches in those cases.

Atomic Snow: Yep, the numbers are matching. Pretty much everything. How about we test it with a single input? just have one which has only one input size?

Verdant Gyroscope: Okay. Yeah, so that should be false. Unless it's zero, but because we're assuming positives, so...

Atomic Snow: Yeah, I can change this one to zero. line number 31. Yes. In this case, it should be still false, because there's technically only one element and you can't really bifurcate...

Verdant Gyroscope: Oh, I think I mean, I think if you consider like the so if this is this case appears true, then I think this should be true also, because, like the subset was containing zero and then the empty subset...

Atomic Snow: You know, right. I think that makes sense. Because you're technically saying that all the members of your set in one and the another is your sum. From some they both sum up to zero?

Verdant Gyroscope: I think. Oh, yeah. I forgot to change that. That should be true.

Atomic Snow: Yep. So it checks out. Are you got the complexity right as well?

Verdant Gyroscope: Where did that run?

Atomic Snow: This works, this is great. I know let's suppose we also wanted to figure out that subset which sums up to some how would we change this to also print that output?

Verdant Gyroscope: Okay, so, I think the the way we do that is and just like printed out as like a side effect?

Atomic Snow: So, like, we asked this function to only tell us whether it is feasible or not. Now we want to know if it is feasible, then return the answer, otherwise, return false or just return an empty array.

Verdant Gyroscope: Okay, okay. All right. So I think like... Okay, so at the end, I'll say like, if it doesn't match then return None. And if it does match, then so I think we want to say like target equals final target. And purchasing is the length of the array plus one. And then like, while target is greater than or equal to zero, or actually well, yet, so I may change these conditions later, but our zero will say like, we'll kind of figure out whether we included or didn't include that element. So I mean, we can just kind of copy this, this logic again. And so in this condition, so, alright, I guess we should say if... Yeah, so if not included less than include, then we append the element? Or... Yes, we can. This as well. And then once we get to, yes, I think we actually have to have target for we have to have partition grid greater than or equal to one. And then yeah, that then at the end, we'll say and should I return like the...

Atomic Snow: This list would have any of the answers because it could be potentially multiple answers. We're just looking for only one.

Verdant Gyroscope: Okay, yeah, so I'll say like first subset and second subset of course subset that append

Atomic Snow: One is fine. We just only went on about one subject.

Verdant Gyroscope: Okay. And then yeah, we can just assume that the

Atomic Snow: Remaining is whatever is not included.

Verdant Gyroscope: Okay. So and then we returned matching subset. So I believe that should be good. This condition is just basically matching the start conditions of this participant as far as the end. Yeah, so I can run this and see. Okay, so this is one line 25. Oh, yeah. Partitions should start at the length of the array.

Atomic Snow: Okay, so yeah, we forgot to update target and... Alright, we're gonna say the partition is gonna be minus one, no matter what. Okay. Matching subset... interesting. So let me just print the output there let me just print these two values to what's going on so in the first example like print the target first. Okay so yeah the first example... Wait a second the target is seven which makes sense.

Verdant Gyroscope: Or target is like decreasing pretty well if you see the seven to one It means it did found something and then it is moving in the right direction it is not adding the element which we just consider to get to this sum.

Atomic Snow: Yeah, it seems like every time it's just saying it's just saying to not include each element like but it doesn't really make...

Verdant Gyroscope: okay so conditions is closest if not including target is less than closest if including target. So think about it is this condition like necessarily true in every situation? Like you may have two elements for example suppose you're starting from 10 you have one one element. The other element five when it's a practical you get to seven when you subtract five to get to five but it could have been possible that your answer would have been in the set which you raised to by subtracting three depending upon the other elements so it is not necessarily true that only the elements will take you closer to the target which will lead you to the final answer I hope I'm making sense?

Atomic Snow: Well, I feel like this is just like replicating the logic the logic appear like because if closest if included is the same thing it seems like and because it's it's not included with it so like the whole...

Verdant Gyroscope: 20 above example you're going from like zero to 10 so yeah, no matter what you will include it will take you to the closest.

Atomic Snow: If you if you include it'll always take you to the closest?

Verdant Gyroscope: Like you're moving from one to 100 so no matter what element you pick, guaranteed like everything is a positive it will be moving closer to it but when you're reversing backward this condition may not be true like it may not be equal to the answer.

Atomic Snow: I see. Yeah, but I guess like regardless of like the direction of movement like at any so like with at this first iteration. Yeah, I can even print out like here like the target position because I'm thinking like at any individual iteration of like the values are the same right? It's just like the way you change the value so I'm not totally sure... Oh, and I have to add like...

Verdant Gyroscope: I think you can just comment out the other print statements or maybe just work with one easier to follow.

Atomic Snow: Well yeah, I was trying to like compare the compare that I guess so yeah. Like for instance when it's like first section, like when the target the target starts is seven partition five. And if we like compare that here, like 7577 that should match and then like it goes to seven four and then here's seven four... Yeah, wait or like here I guess like seven one is closer to seven zero is right

Verdant Gyroscope: So we went to seven then 0. Yep, that is true.

Atomic Snow: So then like in this iteration that should closest does not include should be less than I guess like I can't even like print out like the distance to the target the absolute distance to the target see.

Verdant Gyroscope: Yeah, so in this last iteration, it's like one... Okay, so in this last iteration, absolute value of closest if not include minus target is seven absolute closest if include minus target is six and so...

Atomic Snow: so you will be taking the path of 6? And I'm saying that may not be the path that leads you to the answer.

Verdant Gyroscope: Well I'm not sure this is the reason why it's always empty but I'm pretty sure yeah so like if the distance of the if not include is is greater than the distance of include then you should... But yeah, I don't think that's why but oh for some reason that was that's my bad for some reason that it seems like that was the issue I guess because... yeah, so now it seems to be working it was just it's like the inequality was flipped, right? Like closest does not include, like this is like the distance the target so like, you only want to include it if the closest include is closer. But I guess the reason why that went up that messed it up is like closest if not included. Closer than... Oh, I guess because it's always going to be closer to include something. Yeah.

Atomic Snow: And if you can add one more like add a comma one. Input number 35. Sure. Yeah. Just wanted to say just one sec. Okay, so it is saying false. Yes. Correct. Because there is no we can add one more click. Check. So.

Verdant Gyroscope: Yeah, I didn't I didn't realize like the optimal path, I guess will always involve like including stuff because it's all like positive integers. And it's like a sense that you're trying to get to a some so like this one bugs where it was like flip, where it only appended if you're not supposed to include it. Actually just caused nothing to be appended. It was kind of a weird bug. Yeah, I think it's correct now.

Atomic Snow: Yep, I think we describe the time complexity of the space complexity correctly for the solution. So how about if we try to, let's say, reduce the space complexity? And what direction you could take steps?

Verdant Gyroscope: Okay, so yeah, I guess like it's, it's always only using the partition minus one column. So I think what we can do...

Atomic Snow: You don't have to implement it, because we don't have time.

Verdant Gyroscope: Okay, yeah, I mean, we can just include like, save the column instead of the whole table, and then just replace the column at each, like make the partition the top level loop, and then replace the column at each iteration. And then the complexity, the space complexity would be reduced to O(n), as opposed to O(s*n). Oh, that's... Yeah, there Yeah, there'll be n different. Yeah, so that's...

Atomic Snow: Yep, I can that make sense. Yep. I think that will be all the questions I had for this interview.

Verdant Gyroscope: Great. Okay.

Atomic Snow: I'm trying to get to the feedback. So first of all you have done very well I think you must have realized by now I used to ask this question when I actually cannot refer my company less than 5% of the candidate is able to get to any solution able to get to an optimal solution is less than one person able to get to a follow up if you are talking in zero point something percentage so from my point of view, they're pretty spectacular like I would give you a strong hire the best possibility you are able to see through the problem like to understand it what it was you also able to see that you put in early optimization as well that if some is not even then you know it is not possible so that was pretty great. Then your approach was pretty good to tackling the problem you ran through an example you quickly coded it and you were also able to run it so like all around pretty great.

Verdant Gyroscope: Yeah, I think I guess usually I'm faster like debugging stuff like that. But that was kind of a weird bug that came up but yeah, I guess that's cool. Thank you for the positive feedback.

Atomic Snow: Yep, no, I think you'd like to debug well and it is expected that there will be some sort of null location and you can't really debug it perfectly just by one thought so I don't really mind you trying something and see what makes sense and then going back and revert it so badly from my perspective, I wouldn't hold it against you for for that matter and you ended up your execution speed was also finally once you had an idea what you wanted to do you were able to convert it into code so that gives me a pretty strong signal even if you for some reason you wouldn't have been able to solve the problem I would have still given you a hire if not strong I would have said really looking for the interview is not whether you can arrive to final solution or not. Whether like once you have an idea what to do or you will try to throw it back and all this I think still fine so.

Verdant Gyroscope: Okay thanks so much.

Atomic Snow: You have any questions for me or anything you want to ask?

Verdant Gyroscope: What do you have any advice for someone in my position you know, I'm trying to prepare for for internship interviews and stuff like that. And I guess the summers like around halfway done so I continue preparing as much as possible. But do you have any advice?

Atomic Snow: I think from the coding perspective, we are predictable you will easily get an offer no matter where you decide to interview. So keep doing what you're doing that works well proactively reach out to the companies who are who you are targeting to and once you get to an interview stage where somebody can like after the interview I'm pretty sure you will be able to get through it.

Verdant Gyroscope: Nice yeah. Yeah, I guess part of the challenge is actually getting like an interview sometimes they I guess I'll work on my resume and all that to try and get to the interview stage. But yeah.

Atomic Snow: I work in AWS I don't know how to select folks for interview but if you want to can forward me your resume and I'll try to see if there's some way I can refer you I can like I can refer folks for the full time position but for the interning I'm not sure but I can check with whoever is in the in charge and see if there is a way I could refer you what I would love to.

Verdant Gyroscope: Yeah, I'll definitely do that.

Atomic Snow: Now. So let me check out with some of the folks who were an intern and then got full time hired if there is some way to make sure they have an HR contact or some particular effort to do that. Okay. So many I'm just keep doing it. Your coding skills are super good, man. You were able to solve most of the problems so pretty impressed. I would say overall.

Verdant Gyroscope: Well have a great day.

Atomic Snow: Have a great day. Bye