Hot Gyro, an Amazon engineer, interviewed Talking Rabit in Python
Closest three sum
Find the sum of three values closest to the target.
Feedback about Talking Rabit (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?
Here's some feedback below that we discussed already. I am rating a no advance for this problem because the code still a few bugs, but with 10min more I'm sure you can debug it and make it work fully. Question: https://leetcode.com/problems/3sum-closest/ Positives: - good job simplifying the problem and start with something more manageable, as this can let the interviewer give you feedback and hints - good job providing the complexity of your solution before you start coding, so that interviewers can correct you or steer you to an even better solution Things that can improve: - be proactive with unit testing and immediately start running (manually) your code after you're done. - more unit testing around the edges, like integer overflow, input validation, and input sizes - consider some inline comments in your code to make it more clear. Imagine someone other than the interviewer looks at your code for 5sec and makes a decision - minor: for array indices, typically use "i" and "j" instead of "a,b".
Feedback about Hot Gyro (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)?
It's all positive feedback, the interview was very helpful. The interviewer helped me to get unstuck with good hints and in general it was a good technical conversation.
Talking Rabit: Hello. Hot Gyro: Hello, can you hear me? Talking Rabit: Yes, I can hear you. Hot Gyro: Perfect. So we have an hour together, I thought we could... I have a couple problems here today. Talking Rabit: Okay. Hot Gyro: And before we get started, I want to get a sense from you, if you prefer a more harder problem or start with an easier problem? It's really about how it can help you improve in interviews. So what would you prefer? Talking Rabit: Yeah, I am trying to prepare for an on site interview for one of the four big companies, so I would prefer something more similar to that kind of level, which I guess it will be something more between medium and hard, some like that. Hot Gyro: Sure. Yeah. You know, even the the medium type questions have a big range. But that being said, let's start with one question. And then after that, you can tell me if you prefer one that's harder. Then we can go from there. Talking Rabit: All right. Sounds good. Hot Gyro: All right. So I've got this question. You want to pick the language first that we will be using? Talking Rabit: Sure, I can use
Python3. Hot Gyro: Perfect. Yep. All right. So just copying the question here at the top. Here's the question. And let me see if I can get an example here. There we go. Talking Rabit: Okay, so we have an array of integers, they can be negative or positive. And we're looking for three different numbers in the array that sum up the closest to the target. And we return this sum for the total sum of the three numbers, which in this case, okay, for the example it is minus one plus two plus one, equals to two, and that is the closest we can get to one. Let me see other examples... I guess, if we do minus four, plus two is minus two plus one is minus one. Okay. Yeah, but two is even closer. Okay. And you can assume that each input would have exactly one solution. Okay. Okay. Let me see. So we want to get the sum of three numbers that are the closest to the target. So what if we had the problem where we are looking for three numbers that sum up exactly the target... that I think, hmm. Okay, I think that would require us to do some kind of like one loop through the entire array, and then each value will be storing some kind of map, where the key is the value in the array and the... Oh, okay. And actually, the problem doesn't require us to return the actual values. So. Okay, but let me see... Hot Gyro: Yeah, I think you have a good start here by thinking about what happens if we are looking for the exact target, right? So, I think that's a more simple approach, a simple solution if you could get that. And then, after that, they can extend to how to get the closest. Talking Rabit: Uh huh. Okay. Yeah. So it would be basically looping through the array. Storing the values in a map or even a set, I think would work or... no I think we still need to know the indexes because we don't want to repeat the numbers. Is that actually a good assumption? Because I'm assuming that I cannot use the same value twice? Right? Is that correct? Hot Gyro: That's a good question. In this problem, I think let's make it easier. Let's say no, you cannot use the same number twice, because if you can, then I think we can easily get the exact target, right? So let's say you cannot use the same value twice. And you can also assume there are no repeating values. Talking Rabit: And non repeating values, okay. Cool. So yeah, basically, what I'm thinking is, in this map, I would have a... what are the values that we have in our array and their corresponding indexes, which, then that will help us to do a second iteration. And since we're looking for actually three numbers, then I think we will have to do a nested for loop. Because yeah, we will have to find a two different values, where if we subtract those, the sum of those two values to the target, and if that result is already in our map, then that means... and if the index of that value in our map is different to the two indexes of our two candidates, then we have found a combination of three different numbers that sum up to this target? Not sure if that makes sense? Hot Gyro: Yeah, I think it does. Let me try to repeat what you said, which is essentially, so you go through one iteration. And then in that first iteration, you put the value and index into a map, and then in your second... so within that iteration, you will go through another maybe two iterations to find the combination of two numbers that was together with this first iteration sum up to be the target or closest to the target, right? Talking Rabit: That's correct. The second step would be a two for loops, two nested for loops, I mean, one inside the other. Hot Gyro: But, so in total in your algorithm, what is the time complexity? Talking Rabit: That will be... so the first step is linear and the second step is quadratic step. So but in total, the total running runtime and it will be
O(n^2). Hot Gyro:
O(n^3), just trying to understand... it sounds like there's three loops in total. Talking Rabit: Yeah, but the first loop is independent from the other two. Hot Gyro: I got it. I got it. I understand now. So then quick, right? Yeah. So overall, it seems like you have a
O(n^2)solution then? Talking Rabit: Yeah. Hot Gyro: Yeah, that would work. Talking Rabit: But yeah, the thing is, now if we want to adopt that solution to the original problem of looking for the closest... Hot Gyro: Yeah. So the good part about this problem is you don't need to know which three numbers right? All you need to know is the sum and track and output the sum that is closest to it, so maybe that can... Talking Rabit: Okay. Then, if I can somehow pre compute what are all the different sums of the numbers... And then... No, but that would actually require another loop inside our nested for loops... What if... Okay, so what I'm thinking right now, I'm not sure if I'm going through towards the right approach or not. But what I'm trying to think is, okay, what if... so we are in this nested for loop where we are basically iterating over every single element and then for each of them, we're going to iterate again, through the through the array. So we have two numbers at this point, and then we're looking for that certain number. And then at that point, we're looking for the closest that give us the target. Hot Gyro: Okay, so if I understand your algorithm, you are effectively testing out all the combinations there are, right? And define the three numbers that would be that would sum up to the target. Instead of equaling to the target, what you can do is track the difference. If this difference is smaller than the initial the difference, then you can store that, right? So in this case, in the example here, the output is two, right? And your program would output two. So somehow, along the way, as you are visiting three numbers, you get the sum of two, and then you store that two, because that is your best solution so far, right? You can also get minus one, which is another combination, but that's not as good as two, right? Because two minus one is one, but minus one minus one is minus two, right? So you score the sum that has the smallest difference. And you keep that with you until you've exhausted all combinations. Then you can do something right? Talking Rabit: But that would be a cubic algorithm, right? Because we will have to go through every single possible solution. Hot Gyro: Okay. Talking Rabit: So that algorithm would be
O(n^3), is that correct? Or thinking about it? Hot Gyro: Yeah, yeah, you can always do better. So here's another idea here. So far, you have the best solution of
O(n^2), if we're simplifying the problem to find the three sum that is equal to the target, right? The best solution that you can find is
O(n^2). Now, the solution is already
O(n^2), you can do some operations on the input set without impacting the complexity further, right? So there are things you can do, given that you already have an
O(n^2)solution, for example, if you sort the array, you're not hurting the complexity overall, because sorting the array still less than
O(n^2). Right? So let's say you sort the array, or like, let's say your input is already sorted because that's already... not relevant enough to your algorithm. Then how can a sorted array help you find the solution? Talking Rabit: Okay. Ah because maybe that helped to maybe do it by Binary search, when we are looking just for the third number? So let's say that we have... maybe yes? Hot Gyro: I mean, so it was only one number, right? It doesn't help you find two numbers. Talking Rabit: Yeah, but what I'm what I'm thinking is that what if we are... So I'm thinking the scenario when we are already inside our nested for loop, which in that case at that point, we already have two numbers. And we are looking for the third one. So it works. So it is kind of straightforward when when we when we are looking for the exact sum of the target, because at that point, it is just a matter of like subtracting the sum of the two numbers that we have with with the with the target, and we just look for for that missing part in the map. But what I'm trying to think is what if we, instead of looking in the map for this specific number that we are looking for, what if we do some kind of binary search at that point? Looking for that certain number, like for example... Like let's say that we have, in this case, maybe our current sum is minus four and minus one, which is minus five. So at this point, we're looking for that certain number that get us the closest to one. So we know that we are looking for a number that is closest to one minus minus five, which is... Wait, is that true? Yeah, it will be six, right? Like we are looking for a six at that point. So at this point, what will be the closest number? And so saying that our current possibility is starting from from this index. So since this piece of the array is already sorted, we can look for what is the closest to six in this part of the array? And, of course, since we don't have a six here, we are going to say... like we can we can do some kind of binary search that gave us the closest number to our target. In this case, it will return to which... Yeah, that's what what we are looking for. But I'm not completely sure if that will work, because let we see... Hot Gyro: I think it will, I think, basically improve your algorithms from
O(n^2 log n), right? I think that's definitely at least a little bit better, right? But you still have to iterate through the minus four to minus one. And then you do a binary search on the rest, which is an improvement. So that's a good step forward. But I think you can do better than that, too. And I think that because this problem is not exactly the famous three sum problem, where you find the sum that equals to the target, you may have to kind of come up with a completely new algorithm in the sense that you have been thinking of this map, right? And then and then I think the map kind of makes you use the binary search approach to make it all work, right? But if you start without a map, right, you may be able to come up with a better approach that may even be better than
O(n^2 log n). Without thinking of a map, and then knowing that you have a sorted list, right? How will that help you... Let me think about how that can help you to find out the three numbers. So let's say you start with minus four, right? You're gonna get to the right side with minus four, you do something and then if it doesn't work, you go to the next one minus one and then you again do something. But let's say you start with minus four here, and then the remaining list is still a sorted list, right? So you always have a sorted list to work with. So what are you going to do here? So basically, I guess the question is given minus four, find the two sum so that closest to the target. Talking Rabit: The target is minus four I guess? Hot Gyro: The target is one, target is equal to one. So you have minus four. That's part of it. Yes. Sp actually, you can put that together, right? Okay. So if, if you're given four and the target is one, so I guess the question now becomes find the two sum closest to 5, right. That's the same problem, right? Talking Rabit: Yes. Yeah, sure. Hot Gyro: So this is the problem here. This is obviously a subset of a problem, right? Like you're given minus four. So how do you find that to some other sort of list that is closest to five? What would be the solution, if you can figure out the optimal way to do this, then I think you're closer to the optimal solution of the overall problem. Talking Rabit: Thinking that we can start probably with two pointers. And like, given the fact that the silver array is sorted, then I think we kind of start with two pointers, one at the very beginning and one at the end. Say that, for example, this is the first pointer and this is the second pointer. And then in that case, we're looking for a five. So we're going to say, okay, we have this point, two minus one is one. So we need something greater than our current sum. And since we know that, yeah, since the array is sorted, then we increment this pointer to the next value, which in this case would be would be one. And then so of course, this sum is greater than the previous one. So now we have three. I think at this point, we can... So this will be our base case, or... Yeah, this is this will be the end because we don't have any more numbers. And, and yeah, so it will be these two number, like that will be the answer. One and two are the closest to five. Hot Gyro: Right? So in this iteration, your answer will be minus four, one and two, and that would be minus one, right? So that is not the closest, but it's the closest given this iteration right? So, next thing we do is, you know, given minus one then you can kind of continue that process, right? So yeah, with this approach, what do you think the time complexity is? Talking Rabit: That is
O(n^2)? Yeah, it is. Yeah, that is
O(n^2/2), which is still
O(n^2), but it is definitely faster than
O(n^2 log n). So yeah, I think this will be
O(n^2/2). But in general it will be
O(n^2). Hot Gyro: Yeah. So I think that's a good solution so far. So obviously, there's more to it. And then you have to keep track of the closest difference throughout all the iterations. So again, you have all the pieces right now to kind of put them together. I think it's time to start coding this up. And then we're gonna run through a couple tests to make sure it works. Talking Rabit: Right, okay, I'll do that. Okay, so we're going to start with a function that is going to... and then we're gonna have an input, which is an array, which is a list of integers, and we also have a
K, which is a target. Then this is going to return an integer. Okay, so what we're going to do is we're going to have a... Okay. So this is going to be the final answer. So this is going to be initialized with an infinite number. And then we're gonna do a for loop. Then we're going to say for each number, we're going to find... Okay, I think that it is fair that we leverage a different method to do like the second step of like having the two pointers and doing like the sum of the two numbers. Oh, wait, actually, can I assume that the input of this method is already sorted? Or should I should I sort it? Hot Gyro: So I think for completeness, you have to sort of yourself because the input should be what the question is giving. You can call a one liner, you don't have to implement the sort algorithm. Talking Rabit: Okay, thank you. Yeah. I can just probably do
array.sort(). Okay, and then what else? So for each number, okay, we're gonna take... Okay... Okay, so we're gonna say ref equals to max between ref and max... No. Two sum method... which would an array... One second... So let me explain what this is doing. So... Well, I think I can actually explain that after I implement the two sum one, so it will also receive an array. Then it's going to say okay, we have a equals zero, b equals one of array minus one. Why is this... I don't know why that is highlighted, but okay. Yeah. I don't know. Hot Gyro: I'm not very good at
Pythonwith notes, but I don't know if this list, or should it be like, lowercase? Talking Rabit: No, that's the... Okay, so Okay, so one is pointing to the first one, the second is pointing to the last element. So we have our current sum, which it would be, actually, let me think about this. So we're gonna keep... we're going to... And current sum would be... close to zero. So in here, we're going to decide which index we're going to move. So if current sum is greater than our target, then we're going to increment
a. Okay, so what if it is equal to k? What's going to happen? If
aequals n, we just return. And we do this while... And then we're gonna say that... Okay, so at every single step, we are getting a better answer. Hot Gyro: I wouldn't say that for sure. I think you may arrive at the answer early on in your two nested loops. So I think it's important to keep track of the difference at every step, and then to store that difference so that you can go through everything, but then make sure that you store the difference. So make sure you keep track of the minimum difference. Talking Rabit: The minimum difference? Hot Gyro: Yeah, the minimum difference between your
Kand then the sum that you're doing. Right? Talking Rabit: Oh, right. Right. We want to... Yeah, we want to sum, okay, sorry. Yes, of course. Hot Gyro: So even line
147seems a little suspect because it's like the difference between the two. But if you're looking for sum of them, that is closest to
K, right? Talking Rabit: Yeah. Yeah. Right. That's true. Okay, yes, sure. Then okay, we have, our current sum. And then yeah, we want the best one. So rest is going... So if
Kminus current sum is less than... actually, since this is going to be... And then, let me see. Okay, yeah. So this is wrong as well, it's the current sum equals to
K? Oh, well, actually, we can just... I think we can get rid of this thing. And then we can just return graph at the end. Let me see, I feel like I'm doing something wrong here. So okay, this function is looking for the two numbers that are like, where the sum of them is closest to... Yeah, it's sum is closest to
K. Okay, so... So we keep track of the difference. But we actually need the... but we need we need the sum, we need the... Yeah, we need the sum, we need to return the sum. So okay. Okay, what about this? So now, yeah, we are starting our pointers, left and right. And then we check the sum of those two, we check the difference between the... Yeah, between our target and the sum. And if that is better than what we previously have, then we store that as our best answer. And also, we assign the current sum to the final response. And then we continue by doing the comparison at line 53 saying that if the current sum is... Yeah, if the current sum is greater than
K... Actually, we need to decrement d. And the other way around. Hot Gyro: Yeah. I agree. One thing to point out, though, is the difference there, that diff value? Just about that, do you think you need maybe the absolute value around that? Or maybe can you think of some corner cases where that block of code line 49/51? Could that be a problem? Think about that. Talking Rabit: Maybe with negative numbers. Hot Gyro: So what I'm thinking of is, let's say your diff value here at this point, could be minus point five, right, let's say? And then in the next round, the
Kminus curr sum could be point five, could be equals to or say, point four. Right? So it's that idea of absolute values that I think can tend to come about, depending on the input. Well, something we can handle that. Talking Rabit: Yeah, since we have the option of having negatives, then, and we are looking for the closest to the target. So I think we need the absolute value of the difference because we want to know this difference, how far is from our target? And then we want also to store the absolute value of the actual difference? Yeah, because we want to know how far is it from the actual target? Yeah. Okay, that makes sense. Okay, and then going back to line 38, which might be a bit confusing, what I'm thinking is that it is going to be the maximum value between the responses we already have and the value where we add right now, so in the example that we have evolved, the first element would be minus four. So at that point, we will say okay, minus four plus whatever is returned from the function calling two sum with this sub array. And we are looking for the target equals five as you described here, in the example in line number 23. So, yeah, that's what I'm doing here in line 38. Because we are we are passing this new target to the two sum function, saying that, okay, we are looking for a
Kminus our current number, which in this case would be one minus minus four, and which is five. Hot Gyro: Okay. Talking Rabit: Yeah, what do you think about this? I should test it with a simple test case, something like that? Hot Gyro: Yeah, I think this is something that you should do without needing permission. So definitely run through the test case. And I would suggest that every time you should run through the example that the question gives you, and then on top of that come up with edge cases, which is what the interviewer mostly are interested about, like, what kind of cases that could cause a problem. And then if it does cause problems, fix that as well. So like, just that iterative process is something that they definitely look for. Talking Rabit: I see. Okay, cool. Okay, then let me take this second example. I think it is a small enough, I think. So, let's say so we're gonna start with with minus four, and as I said before, here in this for loop, we're gonna say okay, minus four, plus whatever it is returned from this two sum function, and we're gonna pass to the two sum function, we're gonna pass this subarray, then we're going to say, and in the two function
Kis going to be equal to five. So let's say now... Hot Gyro: I'm going to pause here for a second, I think we can do better than what goes through because this is good. This is going to be time consuming. Let's actually run the code with the input. For example, I am calling this code with the input, right? So let's do that, like minus four minus... Well, actually, let's do the original input,
-1 2 1 4. And then
2right? Let's run your code and
Klike that. Talking Rabit: Okay, okay. Hot Gyro: Okay. So let's run this and then see if we get the right answer. Okay, looks like we have a problem. Talking Rabit: Not defined again. What, what? Why? It is not? Well, no, it should not be like that. Okay. Let's try, but I'm pretty sure. Yeah, it's not correct. Hot Gyro: Yeah. Maybe we need some imports in order to do that, I don't know? Okay. Talking Rabit: Actually we can just get rid of the types. They are not required, they are allowed, but what they are not required. So let's just do that. Okay, let's see. This should work. Infinity, okay. Huh. Oh, because we are trying to return the maximum. And of course, nothing is going to be greater than infinity. We actually want the minimum... Hot Gyro: Yeah minimum sounds fine. What's wrong with minimum? Talking Rabit: Yeah. Nothing. Let's just go with minimum. Hot Gyro: All right, that's a sudden relief. We got the right answer on this example case. Okay. Let's spend maybe two more minutes on test cases. And then we'll wrap it up with some feedback and then questions. Talking Rabit: Excellent. Okay, let's say... I'm sorry. Are you still there? Hot Gyro: Yeah, I'm still here. Yeah, I just got dropped off a little bit, but I'm here. Talking Rabit: I don't know what happened. Okay, let's see. Let's try with... Let me see what is kind of tricky here, or let's see if... So we are looking for three numbers that equals to two... let's try something probably a bit simpler. Like what happens if we call it with a combination that can give us the exact target. So for example, here we can say, what if we target three. I mean there should be... the answer should be three here. And then we can say something that is pretty, like I don't know, like minus 10. And then that would give us like the three smallest ones, which would be like
2 -1, which is... that would be actually, the answer to this one to be, will be two as well. But let's say that this is minus two. So this will give us the sum of the of these three numbers. So let me just try this three examples. And see if we're getting what we're expecting. Yeah, yeah, I think they are correct. So I was expecting two in the second case, and minus two in this third case, because the closest is the sum of the first three numbers. So let me think about something a bit more tricky. What if all the numbers are for example, negative. And we are looking for a positive number. Like we are looking for five? In that case? In that case, we, yeah, we want the three smallest, or the three largest, the three largest positives. Which this is actually incorrect. I think the correct answer here should be minus four. Hot Gyro: Right. That's good. That's good that you're able to come up with a test case and identify a bug and then you can fix it, but we don't have time to fix it. But I think that's a good kind of... even like in an interview, this would be a good thing, because you're able to discover an issue with a test. So that's what I was going to get into in the testing part. I think it's about the time where I will just stop here. I do want to give some feedback, and then answer any questions that you have. So we'll quickly go through that. And I'll summarize it in the end as well. So don't worry about taking notes here. I think you did a good job at beginning, you are able to understand the question, clarify the problem. A couple things you could do, sort of as a bonus, as well as to make sure to ask questions like, are there going to be... I'm gonna put it on line 12 here, let me just maybe put a section of feedback so that you have everything, I put it in line 36. One thing you could also clarify, and this is not like a requirement. But something to think about as well is, anytime you're doing arithmetic, you always want to ask whether you will have a chance of going integer overflow. So in this case, you can ask whether the input would be, we would need to consider that right? And usually the interviewer would say, you don't have to worry about it. They all care about just the algorithm. But asking that question gives them the idea that you are thinking about the edge case. And this is one of the cases, right? Because when you're summing things, it could overflow, right? So even fixing that, addressing that will be easy to do. Just convert everything from an int into a double or a long into that. So but consider that, ask that question in the beginning, that will save you time in the coding. The other thing is, as you are describing the problem and coming up with your algorithm, you did a really good job explaining the complexity. And that's a good thing, because we had this discussion, and then I was able to tell you, you can think about you know, a better way, like if you don't provide the solution and just start coding, you're just going down the wrong path. And that way, even if you have to write code, the interviewer is gonna look at that and say this is not the optimal solution. So it's really hard for them to pass you. So, you did a good job by explaining your algorithm first, explaining the complexity. And by doing so, early, you can have that discussion of whether that is the optimal solution or not. And then you can basically save as much time as you can, and then continue with the coding, right? So your coding is going to be, you know that the coding is going to be optimal code if you have the complete, right, so that's that's a good point. So good job for explaining the complexity early. So that can thrive to discussion. And then just confirm the coding right before you start coding. So that's a good part. And then as your coding, obviously, I think there were some minor issues. But as I kind of give you some hints, you were able to fix it. So I think there were two maybe occurrences where you show a little bit hesitancy, one is the absolute value part and the other is the max/min part. But those are dine, because you're able to get it over with some help. And you've got the, I thought it was a correct solution until I see the test case. So at this point, I don't know where it went wrong, but I think it should be a minor thing should be easy to fix. But it's okay to make mistakes, and then discover them yourself, and then try to fix them. We don't have time today to fix it. But I think, you know, given five to ten more minutes, we should be able to address that problem, no problem, right? And definitely be aware that if you are doing your interview in a platform that allows you to code, they expect you to run the code, right? So you don't have to do the manual testing that you were going to do. In some companies like
Microsoft, they actually use
Codilityand then expect you to run the code, and some other companies as well. So, obviously, a lot of companies use Coderpad, like this one here, but just make sure that if it's available to run the code, you should run the code and always run it with the example case first, and then. Right. So on the unit testing, I think you did a good job first discovering a bug, that's very important. That means that you have to consider some cases. But one more thing, I have a couple more cases that I thought you should include as well is the case where there's three elements, right? That is sort of thinking about the bounds of the input, right? So the most common use case would be like invalid input, right? I'll make sure that what if your input
Kis a negative value, if you have an empty array? These are things that you can just call it out, you wouldn't have to do it? Because they expect you to know this. But then the edge cases is well, what if the input is only three items? What if it is really long? And think about different things? And what if the values are close to the upper bounds of the integer array? So integer type? These are things that you should always think about too, especially when you're doing arithmetic. Right? So so that's one case. And and I think, yes, the whole idea of negative and positive, I think those are good. That's where you're addressing line 76. That's great. So yeah, I think if you have the ones the cases that I mentioned, I think that will make the unit testing much more complete. There might be a couple more that I can think of right now. But if you have time, you'll be able to think about that during the interview. So I think that's all I have for feedback. Do you have any questions? And do you have any feedback about this question, what you like what you don't like or anything like that? Talking Rabit: Yeah, well, honestly, I really liked the question. And I liked that it is not like, one kind of those questions that like very short one, one correct answer. And if, if you don't know it already, is like, pretty much impossible to get it. So I did like the question, it is also encourage you to like to think about many different approaches. So I definitely like that. Something I wanted to ask you is I I don't know if it is okay to have like, for example, at the very beginning, I hesitated about the right approach, because I knew that while at the very beginning, I didn't know how I was going to solve like the problem, the original problem of like getting the closest one, but I knew that I could do something about what happens if we want the exact target. So I don't know if that is a good way to start, or if you could recommend a different approach of like, forget about that and try to think about completely different approach or what what do you feel about about what is the path that I follow? Hot Gyro: I really like the approach you took, especially, like you said, if you don't know how to solve a problem, you definitely want to simplify the problem first. Right? And when you simplify the problem, I think that can facilitate a discussion, right? The interviewer is going to help you try to think along the direction that should lead to the solution. Right? And I think whenever you start the problem in a simple way, or maybe a restricted version of the problem, the interviewer will help you along the way, or you can have a discussion. And I think that's really where the interview is evaluated on is, can you take a hint and then make progress, right? If you know that right away, there's very little the interviewer can know, right? They don't know whether you memorize the solution you've seen before you just regurgitate. It's very good to see that a, you don't know how to do it, and b you have a good approach, that's a good way of doing, so I really like that, starting with a simple approach. And then I thought the discussion that we had helped you get to the right approach at the end. Yeah, so I think that was good. I would say that if you wanted to do some more practice, here's another problem that is a very similar in style, but you want to break the problem into simpler parts, and then try to do a harder, like solve the problem later on. So another problem would be the regular expression matching, where you have to match the star and the dot. And so for example, a dot c would be matched to
ABC, right? And then the a star c also matches to
ABC, because the star means anything right? Zero or more items. Star means zero or more. A dot means any one character, right? Matches any one character. So for a problem like this, you might want to say, well, I'll just start with a handling the first case, the dot case, and when you handle that, then you can try to extend to handle the start case. And then probably, I also suggest that you can try it out on your own to kind of develop the habit of solving a simpler problem of the overall problem. And then extend it. Yeah. So yes. Just coming back to answer your question. I think you had a good approach. Talking Rabit: Okay. Make sense? Now, that's perfect. Can I expect some questions on a this level on an on site interview? Hot Gyro: I definitely do think so. I think this question is more of a one hour type interview, as opposed to a
interviewing.io. Talking Rabit: Thank you very much. Have a good rest of your day. Hot Gyro: Yep, you too. Bye. Talking Rabit: Bye.