Warp Dromedary: Can you hear me now?
Samurai Loris: Yes, I can now, I called you through my phone.
Warp Dromedary: Okay, okay, great. Yeah. In my interview before I had this problem, so at least you managed to connect. That's good. No problem, I won't take the, we'll give you three minutes back, so don't worry about that. Okay, so I guess before I ask the question, I just want to get a sense of your experience. So are you like, mid level? Are you first software engineering job? What's your situation?
Samurai Loris: Um, so I'm a software engineer person for the last one and a half years now. I don't know if that's considered mid level or... definitely not a starter. So I have I've been working as a software engineer for the last one and a half years.
Warp Dromedary: Oh, great. Okay. Awesome. So I guess, in terms of the question, yeah, because I just I get interviewers with all kinds of different experience levels, so I just wanted to gauge where you're at how comfortable you are with the programming stuff. So seems like you have plenty of experience. So I'll kind of gauge the question based on that. So I'll kind of do a warm up question. And then if you can solve it easily. We'll move on from there. So the problem if you've seen this problem before, just let me know. And I can get another one. So the problem I want to share today is going to be called... Well, actually, I won't tell what it's called. But let me do... yeah, let's try this one. Okay. Let me post the problem statement into the chat. And let me give you some sample input and output. Okay, so basically, you're gonna be given, you know, basically a 32 bit signed integer, which means that the leftmost bit, the leftmost bit can be one. And so your you can represent essentially both positive and negative numbers. And the goal of this is just to reverse the digits. And here's, here's another example, involving negative numbers. And you can assume this constraint as well. So you could assume that the number will not exceed that size.
Samurai Loris: Okay, cool. Two to the power of 31. Okay. Okay. Um, so if it's a negative number, if it's a positive number, I'm going to divide the number by 10. I get the divisor and the remainder. So I keep building up the next number. So there's 123. So I'm gonna divide this number by 10. Because it's log 10. So I get 12, when I get three as a reminder, three is going to be my... so I'm going to start my number three. And my next number is going to be 12. So now I divide 12 by 10, I get two. So I make my next result as three into 10 plus two, so I get 32. And my next number is one, the remainder is going to be one, so I'm going to add that. But if it's a negative number, if it's a negative number, I'm going to treat it as a positive number and just append minus at the end.
Warp Dromedary: Okay, yep. That sounds right.
Samurai Loris: Okay, let me continue. If n is less than zero... You can actually use a boolean.
Warp Dromedary: Instead of doing that, instead of doing that, one thing you could do is just make it the multiplier positive or negative one, depending on that right? And then you just multiply that number by the result at the end. You could do that too. Yeah, that way you like you don't need the extra variable.
Samurai Loris: Okay.
Warp Dromedary: Yeah, so sorry, I didn't mean to throw you off. What I was thinking was, yeah, something like this, right int sign is one, and then if it is zero, you just set sign to negative one, right? Something like that. And then at the end, you multiply sign by the result, right.
Samurai Loris: But I cannot start with a negative number. So I thought I can take them as...
Warp Dromedary: Yeah, yeah.
Samurai Loris: But I have to sort of take like instead of doing that math dot abs everywhere. I can just convert it to a math dot abs and then continue from there.
Warp Dromedary: Yep, yep. Yeah, you just do the conversion once. Yep.
Samurai Loris: Once again, let's see, I have 123. And then my remainder is going to be three. My number is going to be my number is going to be 12. And then my result is going to be 3. Then we have one. Excuse me, and then my...
Warp Dromedary: Yeah, so in the first step, yep, that looks right. Yep. In the first step, you get three, right? Your sum is zero. Okay. Yep. Yep.
Samurai Loris: Okay. So my okay.
Warp Dromedary: Yep. That looks good. Yeah, that looks great. Um, so one question here. I'm not too familiar with Java. Is this integer division or will it be a float?
Samurai Loris: It's going to be integer. 123 with 10 you get 12.
Warp Dromedary: Okay, good. Okay. Okay, and then the remainder is three, right? Sum is zero. So first time it will be three then the next iteration. Your remainder becomes two, you get 30. Okay, so it becomes 32. Okay, then your remainder is one on the last try and then it becomes 320. Okay, perfect. Yeah, this is this is good. This is good. Okay, great. Yeah. I mean, that's a good solution.
Samurai Loris: I don't know, it shouldn't be greater than or equals.
Warp Dromedary: Yeah, just greater. You don't want to do it when it's equal to 0. Yeah, yeah.
Samurai Loris: Okay, should I test it?
Warp Dromedary: Yeah, sure. Okay, that looks great. And we try with the negative number too? Try one this one. Cool. Looks great. Okay, nice work. Yeah, so, finished that problem pretty quick. We can do another problem if you like. Or we can end the interview here. It's up to you.
Samurai Loris: Maybe we can try another one.
Warp Dromedary: Okay, great. This one is a little bit harder. Okay, I'm not expecting a complete solution, but if you can get to it, that would be great. It doesn't have to be optimal, but so let's, let's just get rid of this now and let me post a new problem statement in here. So in order to do that... okay, so if you've seen this problem before, let me know. I can get another one for you. Okay, here we go. Okay. Okay, so the problem is, given an array of n integers, are there elements, so basically, namely three elements in that array, such that they add up to zero? And what you need to find is all unique triplets in that array, that give that sum. Okay, so here's a, here's a sample input and a sample output. And just let me know if you have any questions about that.
Samurai Loris: Okay. Are you typing in the example? I don't see anything here. Oh, okay. Okay. It's all there. Okay, I was just up there. I didn't scroll down. Okay, cool. Also, you want all of the triplets. Okay. That's hard. So I'm going to traverse through the array, then maintain the sum of element. So I have a minus one.
Warp Dromedary: So basically, just to give you a hint here, there's a few ways you can start this problem, right? You could have three for loops, right? So one way to the solve this is... one way to think about this is, um, have you ever done a problem where you have an array, which has like, let's say, I don't know, like this, and then you get a target, right? And then the target is equal to five, right? And let's say I asked you, can you give me all pairs of unique pairs of numbers, which add up to the target, right? So like, in a problem like that, right? It's kind of like this, except for each for each number, you fix that that becomes your target. And then the remaining elements in the array, you're checking to see if they add up to that number. Right. And, basically like, yeah, so like, in this case, your target is actually not this, it would be zero minus this. And then you want to check to see if the rest of the elements in the array add up to that. So yeah. So yeah, so that's kind of the idea here, right? So yeah.
Samurai Loris: I had the same idea. Say we have minus one. So our target is going to be choosing a target is zero here. If we have a minus one already, we're looking for a plus one in the rest of the array, like sum of two numbers where you have a target of one, right? This is going to be the same problem again. So I'm going to send this part of the array so... Okay, I'm going to send this index and not use, I'm going to send the entire array and then not use this index, because here, it's easy, because it's the first one you can just send the rest of the array, but later, when you come you're there's another minus one. And then you have to still use, okay. I'm like the, yeah, you know, yeah, the sub problem is, have a target and then send an array, it's basically find two elements where the target is going to be this. So let's solve that first. And let's think about the other part.
Warp Dromedary: Right, right. Okay. Okay. Sounds good. Do you want the return type to be integer array, or...?
Samurai Loris: I think it would be an array of arrays. That's right.
Warp Dromedary: Is list of lists okay too?
Samurai Loris: List of lists is fine too, sure.
Warp Dromedary: This is the main method and just writing the sub problem here. That's going to be those, that is going to be on top. That is going to be a list of... This needs an index because we shouldn't include that number again.
Samurai Loris: Okay. And do you want to pass the target to that function as well? Or you're not gonna include the target.
Warp Dromedary: Yeah I need the target. So how do I do this is basically with a hashmap. So let's say we have, let's just consider this first one. So I'm gonna pass this index and set. So now I have this part of the array, I'm going to put zero in the hashmap with an index one, and then I'm gonna look for the... I'm gonna have index in the key and value can be my target minus this value, which is basically one minus 1. And, okay, the key has to be the value. Okay. The key is going to be target minus this is going to be one, and the value is going to be one because the index is one. And then when I'm looking... Okay, one second. I just got confused, but I'm looking for one again. I know that it already exists in the lab, which means that this pain is going to form the sum. So I'm going to return zero and one. 5 is not equal to index. Oh, so you want to return the numbers right and not the indices here? Okay. If map.contains numbers, which means that my... Okay.
Samurai Loris: Yeah, hang on just a second. Sorry what what is this result? Ah, okay? Okay, that's an ArrayList. Okay, okay, sorry. Okay, so you're saying... So you're saying if the... Okay, so you're saying if the element is in the hashmap, then add to this ArrayList you're creating a new ArrayList, you're adding that number and then you're also adding the target minus that number. Okay? Okay, why? Why do you need to create this? Okay, I see this is your gonna be your answer that you're returning right?
Warp Dromedary: Yeah. So if you have this array and then I have minus one here, so I'm not going to use that, I'm gonna use these elements here. And I so, I didn't finish my map.put yet. So I'm going to do that. Okay. This is going to be, so I'm assuming all of these are unique numbers. Basically and then...
Samurai Loris: Oh, they're unique? In the map, they should be all, but you could have duplicates in the array, right? So you want to make sure that you... so I don't know if you've considered that or not, but you can definitely have duplicates in the array.
Warp Dromedary: Okay. Now, I have to call this find pairs for each number in the array.
Samurai Loris: Okay, okay. Okay, so one question here, right? So you only want to add two numbers because your goal is to get three right? So can you walk me through how in this loop you can ensure that you're only ever adding two numbers? To that result at a time. Because like this result array right, if I understand your code properly, it should not have the size greater than three, right? Should be exactly three.
Warp Dromedary: This is going to be two here. The size is going to be just two. Yeah. Once you find a pair...
Samurai Loris: Okay, okay. I see. Yeah, that's what I meant. Okay, so, okay, so it should be two, right? Yeah, that's the thing because you didn't break right? Yeah. So you're gonna keep adding that's the issue. Okay. Okay, good. Good. Okay, that looks right. Yep.
Warp Dromedary: Okay, so I have basically I have zero and one here, and have to find for which number I'm looking for. Okay. So, minus one. So I have to call this method, find pairs. If the result set is not empty or if It is not empty, which means that I found something that matches the sum. So I'm gonna create a new list and then add.
Samurai Loris: So one question here, what happens when the target is duplicate? So what happens when you call this function with the same target? Because remember, you don't want duplicate pairs, right? So how would you handle that? You can, you can still keep your design, right, it won't break your design. But you need to do something, right to handle that. You want to keep track of the target. Right? That you that you call before, right? Because if you think about it, if you pass the same target to this function, right? You're going to get that same combination, right? Of the same two of those same two numbers, you might you might have a duplicate there. So yeah. So for example, right, let's say that, you know, you're here, let me give an example like, so. You have your nums. So you're computing your target by subtracting zero right from each number, right? So let's imagine you had something like this. Okay. Can you hear me? Yeah, something happened, it kicked me out of the interview. Okay. So yeah, let's say you had an array like this, I don't know if you can see it and scroll down here. Let me come and post it right above your code. So you had an array like this, right? So this negative one is duplicated, which means your target is going to be the same, right, the second time you call it?
Warp Dromedary: Yeah.
Samurai Loris: What happens in that case? What do you do in that case? What I can do is I can maintain a set of targets. I can maintain, has set of targets, it's already in the target, I can just do or that's not if, if, before my minus one here... Okay, that's possible. Let me think about it. So if my target is seen, I can use a hash map. From my target to this list. See, if I have the targeting the key, it it contains key, then I'm just gonna return from the map and start doing again.
Warp Dromedary: So you're basically just saying on you want to keep track of the solution you had from the previous target. And if you already computed it, you don't need to do it again. Okay. Yeah. Why don't you just keep track of the target itself? Like, why do you need to have? So if you see the same target again, you can just skip it. You don't need to try again, right?
Samurai Loris: That's true. I don't have to return thing. Okay. Yeah, I don't have to do it again. Oh, but for that, also, I have to keep track of the target, right, because how do I know if it's already?
Warp Dromedary: Yeah, yeah, exactly. You need to keep track of the targets, right? Yeah, but you don't, you'd like have the extra space to like map it. You could just put the target in a set or something, right? And then that way, yeah. You don't need to have the hash map.
Samurai Loris: Which means we found our target.
Warp Dromedary: Okay. Yep. Great. Okay. Yeah, that looks good. That looks good. So yeah, that's one solution. Sure. That could work. There is another one. So what's the time complexity for your approach? What do you think it is?
Samurai Loris: Oh, it's going to be O(n^2). For each number we're doing pairs again. So there's a for loop and there's a for loop inside that one.
Warp Dromedary: Yep. Yeah. What, what about the space? How much space are you using for this?
Samurai Loris: Okay. So I have hashmap of all the numbers, worst case, at least like, so it's going to be O(n) for this. This one. And then I have a set of targets here, which is going to be O(n). And so, this is going to be O(n) and what is the, temporary list that I've been using. But this is used to get the result. Okay. So this is O(n^2), the result itself. Because we have stuff list of integers, and this can... Oh, this is just constant. So if I consider that as a constant, then it's going to be O(n).
Warp Dromedary: Okay. Yeah.
Samurai Loris: Because this list of integers is always going to be three and not more than that, or less than that.
Warp Dromedary: Okay, so you're saying that for each element, potentially, you could have you... Oh, okay. So you're saying, you're gonna have a list of lists. Each of those list is a constant size. So it's size is O(n). O(n) space. Um, well, it's in terms of... Yeah. I mean, like, it's probably still linear space. Yeah. Okay. Yeah, yeah. Yeah, I agree with that. That sounds right. Okay. I think the solution is good. There could be a way you could do it actually, without using any space, I would challenge you to think about how you might accomplish that. We don't have to go into it this time. But there is a solution to this problem that you can find that involves using pointers. And you can basically eliminate the extra space needed by cleverly figuring out... you need one more heuristic. So you need the list to be sorted. But after doing that, you can you can avoid the extra space. But we, you know, we don't like yeah, there's, we don't have to talk about that. But just so you know, like, if you do see this problem, come up again, and you you are able to do it. I think this solution would pass. But just to know if your interviewer in the future, he challenges you and gives you a space constraint, just to know that there's a way to deal without extra space. Yeah. Yeah. Overall, I think you did great. You did really well. Do you have any, like questions for me or anything?
Samurai Loris: So are you, I know this is peer to peer interview. So are you also in getting interviewed from people on this platform, are you are you just a professional interviewer that's doing using interview.io?
Warp Dromedary: No, actually, I do. I do. I do use interviewing.io, I get interviewed by other people on this platform too. And for me, as well, I'm kind of waking up to doing the anonymous interviews with those companies that they have listed that, so it's cool. Actually, any anyone can sign up to do the interview. But I think you need to have at least some number of successful interviews before you can before you can start interviewing other people. But yeah, if you're if you're interested in doing it both ways, I think it's a great experience. Like I think it's good to be on the other side once in a while to you know, mark this only getting interviewed but also interview other people that you like, you know, how how to have a communication with them and understand like their thought process too.
Samurai Loris: Okay, makes sense. Thank you. That's all, I don't have any other questions.
Warp Dromedary: All right. Cool. Well, thanks very much. And I'll leave you feedback, please, you know, if you'd like to leave feedback, don't hesitate.
Samurai Loris: Okay, cool. Thank you.
Warp Dromedary: Cool. Thank. Bye bye.
Samurai Loris: Bye.