1) Given an array of integers nums and an integer target, return the numbers from the list that sum up to the target. 2) Find the start and end indicies of a subarray that sums up to a given target.
Feedback about Chaotic Pizza (the interviewee)
Advance this person to the next round?
How were their technical skills?
How was their problem solving ability?
What about their communication ability?
Well rounded candidate. Worked through the problems with speed and efficiency and produced optimal solutions. We got through 2 problems in 50 minutes. My feedback would be to "signpost" a bit more -- when running into an edge case or recognizing a potential bug, try to describe the breaking case that causes the bug to the interviewer before proceeding to fix it.
Feedback about Existential Crumpet (the interviewer)
Would you want to work with this person?
How excited would you be to work with them?
How good were the questions?
How helpful was your interviewer in guiding you to the solution(s)?
Thanks for interviewing me late in the evening and giving me many useful feedback along the way! The problems you gave are connected and that's very helpful for me to think of the solutions. The questions are well prepared, not very hard but still require calm and clear thinking to get right.
Existential Crumpet: Hello? Anyone there? Chaotic Pizza: Hi. Hello. Existential Crumpet: Hi. How are you? Chaotic Pizza: Good, good. How are you? Existential Crumpet: I'm good. Well, a little hungry. I should order some food. Chaotic Pizza: Yeah, sorry. Are you also in the in this time zone? Existential Crumpet: I'm on the west coast. Chaotic Pizza: Yeah, yeah. So, eight o'clock. Existential Crumpet: How about you? Chaotic Pizza: Yeah, me too. Yeah. I'm in Seattle. Existential Crumpet: Did we do a practice interview together, earlier? Have you been doing these for a little while? Chaotic Pizza: No, no, no. Just my second time. Existential Crumpet: Your second time? Okay. Cool. So let me start off by telling you a little bit about me, my background as an engineer. And I think it's just standard practice interviews for me, as the interviewer, to ask you about your background. So if you feel comfortable talking about that, practicing your schpeel. I'll ask you about that. And then maybe we can figure out something you'd like to work on. We can work through a problem together. Chaotic Pizza: Okay. Existential Crumpet: Cool. So, I am a backend applications engineer at
electronframework. So I write
Reactfor the front end. And also I use a little bit of
Gofor the so called back end of the app, but it's not really a back end, because it's also this is combined as a client side application for our... we have a cloud platform, cloud service. So we do business with police officers, and government. So we provide software and also some hardware, like body camera for them to use. Existential Crumpet: Oh, okay. So you use
Gofor the back end, but it's not truly back end? Chaotic Pizza: Yeah, yeah, I recently am working on uploading applications. So it just allows you to drag and dropping files and previews them and added some of the fields and upload them to our cloud platform. So I do, you know, I have a back end, like I write the upload part in
Goand managing the most of the business logic in the
Gopart. So I just use the
Go. Chaotic Pizza: I could use
O(n^2), if you wanted it time wise. Existential Crumpet: Okay. Can we do any better? Chaotic Pizza: So basically, you could, okay. If you use, like, a stack or map, you know, basically to record each one you go through. And maybe you can check along the way if there's something. Maybe I can write it. For example, you want to 78, you want to see the 78 When you hit five, you can check if I have say 83. So it's minus. So do I have 83 or not? If I have a 83 already, I could just you know, return the, the pair. And if I don't know, I will just record five. And I go to the next one. I say I made 20. And I will check if I have 98. For example, if I have 98, I could just return the pair. If I don't I just record 20 and go to the next one. So I think when I go to the 80, I need to check if I got two, I already got two here. So I just returned 80 and 2. Existential Crumpet: Cool. What happens if... Yeah, that seems fine. I think there's one specific technicality to that. I think I'll leave it to you. Let's see if you anticipate it in your code. Chaotic Pizza: Okay, I would just say, oh, maybe start to write down. You know, generally there might be bugs, but we can we can fix it maybe later on. It's not so obvious. So I could start writing this algorithm. Like it's a... Yeah, we have something like, yeah, like this. Um, so basically, See? Right? Maybe I can run it. Existential Crumpet: Yeah. Show me how it works. Chaotic Pizza: I'll use this list. See? And maybe not if diff plus E, I still have some cases I should find. Okay. Yeah. But it might be E minus. No, no, it might just be minus E. Yeah. But in this case, the diff will be.... Yeah, if the diff is larger than... So essentially, I needed to have absolute value, some something like absolute value. Because this one should give me the answer. Right? Because the when the E is 80, last two. Existential Crumpet: I'm not as familiar with the ES6 API. Chaotic Pizza: Yeah, yeah, maybe I shouldn't do something like
forEach. Yeah, yeah. Existential Crumpet: Yeah. And so for these purposes, personally, I don't care. And I don't think usually an interviewer won't care too much. As long as your algorithm is right, I mean, sometimes they're looking, "Okay, do you know ES6?" So while you might want to... Yeah, I mean, it's usually nice to to be conservative with your syntax. Chaotic Pizza: Yeah. Because the for each syntax, we're basically taking a function for every element is like transforming every element, but it won't return, the return won't be returned to the outside function, it's just returns inside the function that gets assigned to each element. So so it's not right. Just like that. There we go. Yeah, so yeah, definitely. Existential Crumpet: Nice. Okay. So usually, I give that one and people either do pretty fast or it takes the whole time. So when you It took us only about 20 minutes, which is pretty fast. And you basically have the optimal solution here. Which is great. Because I think the cleverness of doing the two checks. So you say diff + E is our number. Or if E - diff is our number. Yeah, that saves us a loop through the list. So we don't have to go through it twice. We can just go through it once. Yeah. Because in either case, it's its
O(1), right? Chaotic Pizza: Yeah. Okay. Existential Crumpet: So let's give you another one. If you're up for it. All right, here's one. This one's fun. We're gonna try to get this one done in time. So this one's kind of similar. It also involves summing numbers. And with this one, our goal is to given an array and also given a target, our objective is to figure out the indices of the sub array that when the values of that sub array are summed, equal the provided target number right here. So in this case, 3, 15 is the first zero through four. Okay. Chaotic Pizza: So we're still looking for just the one answer. Existential Crumpet: Yeah, it really doesn't matter which solution you provide. Although that's a good question to ask. Chaotic Pizza: Yeah. Like, one obvious solution will be you know, you just I think calculate all the subarray sums. And check along that way if you see one, if you got one, you just return. So calculate the array sum is like, you can first add them up like, so you have a new array, that's the sum of from zero to this index i. And you can do the minus when you go through the array. So for example, you have this one, maybe one plus two will be three, one plus two plus three will be six, an array like this can. So your sum of this subarray from the beginning. And you can you know, you can minus any two of them. You move through this array. So that will also take
O(n^2)time. Existential Crumpet: What I want to make sure I make clear is that you could encounter, I don't know if I said this, you could encounter a case that looks like this. Chaotic Pizza: Yeah, sure. I mean, when you've got this array. Yeah, I mean, when you've got this array, you still need to check, because, you know, you need to go through this like multiple times to check every pair, basically, because the pair, the subtraction of the two numbers represent a subarray sum. So that will give you all the subarray sum. So you can check in there, but see, it's not very efficient, I guess. It's not very efficient. Okay, okay. I think I have something maybe similar to the previous problem. I think you also use a set to record the... basically you record the sum from the beginning. And you can check if basically the current sum... okay. Maybe I can write it down. So that's your current sum. And basically you want to see if... and we also have a set again. You basically want to check if your set has the target minus sum. If you have target minus sum, yeah you are... oh I should use a map here, you see one of the indices right. Okay minus song, and it's get in
1 3 7 5 12. Existential Crumpet: Okay what happens... Did you find something? Chaotic Pizza: No, no I think this seems to have a bug in the code. But yeah, yeah, go ahead. Existential Crumpet: Well, I think I found the same bug, so I'll just let you work through it. Chaotic Pizza: Okay, okay. I see, so there's one edge case. Existential Crumpet: So, describe to me your sort of current thought process on this algorithm. Chaotic Pizza: Yeah. Yeah, it's still has some bug, I'm afraid. But to the biggest, I'm thinking about you know, you can have this, you can accumulate a sum. So from the beginning, and the sub array sum is really just the, you know, you subtract two subarray sum, right? So you got, you know, from the beginning, so you got the difference between them. So that's a subarray sum. So since you're doing this kind of difference or subtraction, it's sort of similar, like the first problem where you want to find to a pair of integers that which has the difference. Existential Crumpet: Can you explain the difference to me a little bit more? So where's the difference come in to the picture? Chaotic Pizza: You mean, the difference between the two problems? Existential Crumpet: Oh, no, not between the two problems, but I guess what I mean, you started, I think you talked about that difference, like subtraction. Chaotic Pizza: Okay. It's like, the subarray sum is, I think the sum from zero to i. So, basically, sum from i to j is equal to sum from zero to j, minus from zero to i. So yeah, that's the difference I am talking about. So it's, it's a basically a difference between two sub arrays from the beginning. Right, so if you consider the each sum from the beginning, you know, as an element in array, you basically you have the problem. Similar to problem one, so yes. So I'm thinking using a set to do it as well. Or map. Existential Crumpet: No, I see. Yeah, just to sort of keep you on course, here since we're a little tight on time. I think that might be a bit of a red herring. Because you know what... why don't see if this works. I don't want to stop you. Chaotic Pizza: Yeah. Existential Crumpet: Okay, I would try to keep the two problems separate. That would just be my recommendation here. And let me know if you'd like a hint. I mean, I'm trying to make this as realistic as possible. Chaotic Pizza: Gotcha. Yeah, yeah. Existential Crumpet: So can you explain to me why you think calculating sum i through some j is easier done by this different approach versus just calculating out some i through sum j when you need to? Chaotic Pizza: I guess it's just a one way to do it, it doesn't, it's not necessarily the better way to do it. It's just because I, when I saw the, you know, sub array sum, I would think of a minus, you know, the difference between two sum. So that's just how I think of it. So in this case, if you really want to calculate the sum of all the sub array, that's really, that's not very efficient, I guess. Yeah. So do you understand this function I wrote? Like, roughly? Existential Crumpet: Yeah. I didn't realize that this was a this was a prepared solution. I thought you were still working on the problem. Chaotic Pizza: Oh, no, I'm trying to figure out what's the bug, where's the bug. But yes, it is. I think this will work. Yeah, but it seems it has some. I mean, you should go to the details to try some example to to fix this. Existential Crumpet: Yeah, so let's check a specific case. Let's say I give you 15 right here? Can you walk me through the test case on line 18? Chaotic Pizza: Okay, okay. So I think maybe we can try an easier example. Maybe we can try maybe, like, if you want to find five in this, in this case, you will have to keep the sum of one. And and you try to find maybe you try to find the four but you didn't find, you know, you couldn't find four. So then you go to the next one you are you added up this. So now your current sum is is three. So you try to like find the two, but yeah, you still can. So now you've had up to add up to six. Right? So six. So now you have the sum of six, now your target is five. So yeah, I guess that might be the problem. So, you want to find in this case it would be minus one. So you fail. So you, so you need to try the other way around. So, maybe you need to check if you can find like one, because six minus five, you also find one, and now you have one here. So now you can just basically use six minus one. So that gives you five, which means your sub array is from the first index to the second index to the third index. So that will give you five, because the six here minus one is is equal to your target five, because you will have already recorded this one in your map or set, you can easily find it like so you don't need to do the find multiple times, you just do it once. And you use a map or set to record the sum so far. And you can find the answer. So I think the algorithm function I wrote is still problematic because I only check the target minus sum. But there will be cases where the sum is actually larger than the target. So it's absolute value. So I may need to check the sum minus target as well. And let me try if I can. Let me try if I can. I'll put something. Yeah, so I guess I will plus one here. Yeah. Oh no, no plus one here. Yeah, that's why. Yeah. So yeah, yeah. It's because this example is
1 2 3. So
2 3 7. Yeah, yeah. Existential Crumpet: Okay. I think this looks pretty good to me. Chaotic Pizza: Yeah, sorry. This took a lot of time to figure this out. Existential Crumpet: No, it's fine. I mean, we we managed to fit two in one interview, so that's great. And you move through these both pretty fast and it's a good efficiency. So yeah, yeah. I have to go pretty soon because I have another interview at nine and I need to eat a little bit. Do you have any questions for me? On feedback or anything like that? Chaotic Pizza: I haven't interviewed anyone. So I cannot really, I think you're doing great. So I didn't know how to, you know, I don't really have much feedback to you. Is just, so I actually have one question. So do you do like interviewing for