Watch a technical mock interview with an Amazon engineer
Stateless Snake, an Amazon engineer, interviewed The Wild Husky in Java
Share
Summary

Problem type 

Median of sorted lists

Question(s) asked 

1) Given a list of daily temperatures T, return a list such that, for each day in the input, tells you how many days you would have to wait until a warmer temperature. If there is no future day for which this is possible, put 0 instead. 2) Find the median of two sorted lists.

Feedback

Feedback about The Wild Husky (the interviewee)

Advance this person to the next round?
  No
How were their technical skills?
3/4
How was their problem solving ability?
3/4
What about their communication ability?
4/4
N/A

Feedback about Stateless Snake (the interviewer)

Would you want to work with this person?
  No
How excited would you be to work with them?
N/A
How good were the questions?
3/4
How helpful was your interviewer in guiding you to the solution(s)?
3/4
N/A
Transcript
Stateless Snake: Hello. The Wild Husky: Hey. How you doing? Stateless Snake: Hi, can you hear me well? The Wild Husky: Yeah, I can hear you. Can you hear me? Stateless Snake: I can hear you. Yeah. How you doing today? The Wild Husky: I'm doing good. How are you? Stateless Snake: I'm good, thanks. Yeah. So this is a one hour interview, mainly focusing on the coding. So can you tell me a little bit about yourself and where you are in your interview process? The Wild Husky: Sure, yeah. I've been working as a back end engineer for the past four years. And before that, I used to work as a full stack engineer. So right now I'm kind of working for consumers in the consumer space. So my work kind of entails working on the product side of things and also work on data infrastructure. So we are developing ETL solutions for enterprise customers. So we are interested in like basically ingesting data from like different sources, like local filesystem, cloud sources, or your like databases. And it could be like any kind of file format, file structure. And like, the idea is like, kind of like transform the data in a certain way so that the consumers can use it. So that's a core idea about the product. So like, the ETL pipelining for them, and like provide a transformation and convert the data in the way they want to use it. And I'm kind of like looking for jobs in the same area too. I'm interviewing actively right now. So I have a few on sites like scheduled in the next couple of weeks. And I had like a few like, which I gave in the past couple of weeks. So it's kind of like somewhere in between. So I still have some more like phone interviews, which I'm going through right now. So I just wanted to see if I can kind of have some more practice, you know, having some peer to peer interviews, because I did just like last year, but I haven't tried any of them this year, yet, during my interview process, so I thought it would be a good time to give it a try again. So that's how my current interview process is, so it's kind of like somewhere in between, like very passively interviewing right now. It's not very aggressively have a lot of interviews scheduled or something? Stateless Snake: Okay. So do you have any specific company you're looking at? Or is it in general? The Wild Husky: I have been, I mean, I have a few of the higher tier one company interviews coming in the next few weeks, I think that's the main reason why I was like, kind of like aiming for you know, like interviewing more efficiently. But I had like a few startups like few like mid level startups that I interviewed at more recently, like some of them actually seem like good, like they even I even got to the last stage, but I just feel like it didn't really work out for different reasons. Like either I didn't do well. Or maybe for some reason, the team was not a best fit for me, or like maybe I'm considering, like, right now we don't have a lot of good openings. So I was a little not really ready to like make a move where I can just want to like take any job because like I'm just like I said I was looking for jobs more passively. So I'm like only looking for certain positions that I can really find myself as a good fit, considering that it's a good fit for me technologically. And also like, if I can kind of get into like a better position than what I'm doing right now. So just a good combination of all of that is what I'm seeking. So it's kind of like hard, currently how things are. But at the same time, I'm going to that also gives me enough time to interview in multiple places. So I'm not really looking for any particular company, which is like a dream company or something like I'm pretty open like, like the top tier one companies or any of the mid level startups where as long as I can find like a good product to work on. Stateless Snake: Yeah, so I'm gonna base the question here and you can feel free to choose whatever language you want to do it. Yeah. Yep. The Wild Husky: Yeah, I can see. Stateless Snake: Yeah, let me know if we already solve this problem or and contrast in that thing. You can. The Wild Husky: Okay. I think I saw something similar, but I couldn't recollect it like how I did it, but I kind of like have a sense of like, how I might have done it. But like I said, I don't really exactly remember like this for the same problem or not, because I saw the temperatures written on it. So I just felt like I've done something similar, but I don't really exactly remember how. Stateless Snake: Yeah, no, I just wanted to ask, like, if you want to do it, like, you can do this. The Wild Husky: Sure. Yeah. Yeah, I think I think it'd be a good problem to solve. So I don't think so. I remember like how to solve it in general. So it's... Yeah, so I think I want to give it a try and see how they implement it. Cool. So we have, we have temperatures, which are I'm assuming that these are all like integers. So we are like just considering integer inputs here. Right? Yes. Okay. And then is it also possible to have like, I think it's possible to have like negative, I think the ranges from one to 30,000. So you're already considering so that the length of the temperatures and the temperatures are in the range of 3200. So you don't have to worry about anything about the value. So yeah, I think the the restrictions on the value and the length is kind of pretty obvious. I think that clears out the basic input that I'm expecting. So okay, so how am I doing this, and I'm thinking in this case, since we have to know like, like not jsut sensitive arrays, so I would like first of all know how to iterate it. And also, somehow, like, maintain the state so that I can know how to update those values whenever I find a value, which is greater than the X in this case, since 73, is the first one and then it comes to 74. And it's basically like the next value itself. So I'm comparing it with one similarly with 74, 75, updating it with one, but for 75, it has to wait till it finds 76. So it has to kind of like skip through these values, but we have to somehow maintain those values, in some ways that it knows that until I don't get to this point, I need to... this leg look for the higher value. So this seems more like a like the data structure for this I can think of as like using like a stack or something, which will just keep track of the all the previous records, if I basically keep on adding the values in a stack, which will basically wait for a whenever the next value, which is going to be added to the stack is basically greater than the top value of the stack, I know that like I can simply like remove that value, and update the current value with the like in this case, if you need to have an output array, it can be like a separate array altogether, which is just keeping track of like how many values that I have to skip tracing to get here. So since within the stack, they're already maintaining, like what are the different values you added to the stack, so we can simply like keep on popping the values as long as we can find a value which is kind of like smaller than the current values. In this case, it's 74 73 smaller so if we just simply update that index and say like hey, just add one to it because it was the first value and similarly for 75 which is a big one. Whereas when it comes to 76 it has to pop all the different values and it could just keep on updating those so called single like xs in this case, it is just going to update those indexes when it has found that value so basically the stack is maintaining the index is not the values so that we can update that particular index whenever it finds an x value which is greater than it. So I think that's how I'm going to approach this problem. Stateless Snake: Yeah, I think that works. The Wild Husky: So I think in order to change the programming language to... Java. So, in this case, we are kind of looking for the values to be... So, we are looking for what is the current index at which we have found it. And then we also need to know the difference, until we found it, it will be the current index minus where the previous value was, because we need to know the distance between them. And then... So this will basically bring it back to the same state they're looking for the next vals, keep on doing it until this condition is satisfied. And then we also need to make sure that this new variable is being pushed. And also, in case of a large entries, if we couldn't find anything, the array would already have zero initialized and then we are looking for... Okay. I think because in this case, we are not doing anything stack is empty stack peak, and we are getting the difference here. And then I think, although that is... Yeah, I think this is the solution I will go with. In this case, there's only like one boundary condition to check whether the length is zero or not. And the rest of all this kind of like handle inside the stack, like I mentioned. So we are kind of like using a stack to keep track of the indexes. So when the stack is empty, there is like nothing we can do, we just simply add the index that we have. Otherwise, it is basically going to find the current value. And we'll check to the stack, whether it is having any other previous values, which are kind of like smaller than that value or not, which means that there has never been at all the values are kind of like constantly decreasing in that case, because it has never been able to find something greater than that, so it is going to keep on popping the values from the stack until it basically finds this condition to be satisfied. And just going to update the result, which is our output with a difference when the current index is and what is in the stack. And we also removed the value from the stack. And then we would basically update the stack with the current index so that whenever we have to update that value, we will update that as well. And finally, it just goes through each and every value into the temperature and like the results will have all the indexes that you're looking for. Stateless Snake: Okay. The Wild Husky: If you want, I can execute this one with the example that you give to. So whatever the case is, like if the stack is not empty at the end, because we won't have any values which are to be updated in that case, which is fine, because even if the stack is not empty, then but that means like the only time when we add values to the stack is, for example, in this case, you have 76 and 73. They are value zero because there is like no more values that we can update anyways. So even if the stock is basically still populated, we don't have to do anything because we cannot update them because we haven't found a value which is greater than 76 or 73. And they will still remain zero. So in this case, actually they will have those values left in the stack. So 76 and 73 will still remain in the stack because we couldn't find a value greater than them. And since we have initialized the array, we haven't initialized the values on the windows array. So those values would still remain zero. So we don't have to worry about updating it. So that's what the result would eventually return back. So we don't have to process the stack values again, because they are going to like kind of like not be used for anything else. Unless we are doing any pointer operation single, I guess, we reached like 76 or 73, we got another value after that, then it would do it. But if there is take nothing off of that we are just going to leave the stack as it is. And just going to return the result in that case. Stateless Snake: Yup. That's correct. Would you like to run this? Yeah. So try to run. The Wild Husky: And then I would have like, all decreasing values, just so that we have the condition of think is all the values are constantly decreasing supply, make it as like 79 78 77 76 75. And similarly, or increasing values too. And since you already have a boundary in which the values are existing, so we don't have to worry about this, I think that is only defining the regression until like, it's only going to be enough for them to check for the status to begin with, and then see if I can kind of like visually see how they're ready to so yeah, it won't break anything, because it's an empty array. In this case, it will basically be like zero for everything, because there's like no value, which is going to follow up with this. Okay. This is going to be like an increasing order effect. Yeah, 78 won't have anything close to finding value for that. Stateless Snake: What about like duplicates. So what would be the expected thing? The Wild Husky: If it's complicated duplicate, it was still wait for the next value, which is kind of greater because even if it's like kind of repeated, it would still be considered as like the same, same value, because it's not warmer than the current temperature. So basically, if I have something like 71, Stateless Snake: What if I say like it's warmer or equal. If I said like warmer or equal, like, what piece of the code you need to change? The Wild Husky: In that case, I will just simply like chain this condition where I'm just like popping the value out, like if it is like greater than equal to so I think that that programmatically solve this problem for me, in this case... Stateless Snake: Yeah, I think this works then. Can you explain like the time complexity and space complexity of this solution? The Wild Husky: Yeah. So the... in this case, that time complexity is going to be... all going to be able to run through each and every temp value and then you're going to also constantly remove the value from that stack. So we are running it for like a linear time. And then each and every value is going to be like popping it out from the stack as well. So this is within the linear runtime. In this case, even though we are kind of like removing the values from the stack by kind of like depends upon the way the value in the stack is added. And we are also removing it constantly. So it is basically like a linear runtime, because we are just iterating over the loop and going over each and every value once. And so, basically going to be like linear because we have like a stack, which is kind of keeping track of all the values inside. So, it's basically like a linear on time in linear time complexity. Stateless Snake: Yeah, so the space complexity? The Wild Husky: Space and time is what I'm talking about. Space is linear, because we are using a stack and also the time will linear because it's a monotonic stack. And we are kind of like using that to keep track of all the values and we're just going to kind of like remove the values every time we find a value just kind of greater than that. And so the runtime and also the space would be the same so they both are linear in this case. Stateless Snake: Yeah, perfect. I think that's all for this question. Do you want to since we have more time do you want to discuss another problem? The Wild Husky: Yeah, sure. Stateless Snake: Yep. Okay. You need to find the median of two sorted lists. Like how do you do that? So, the input will be to integer arrays and you need to return one value. The Wild Husky: So when you say array, like there's a difference between this case are we talking about like a list or an array? Stateless Snake: Array. The Wild Husky: So, I mean, I think I need to kind of like go with the same logic of finding median for like one area and then trying to implement that for two areas. So, I mean, this is like, like a binary search problem, where we can kind of like narrow down the search again, like the two different arrays can have values, which are kind of like spit in different ways. So we have to kind of like find a common like a like kind of like a pivot where we can see that like, hey, these are the values which I mean, it's kind of like using the same logic for the use for median with like a single array, we try to find like the middle middle value, and then we try to compare that to things and again, these are the values are smaller than the median or basically, these are the values which are sorry, these are the values which are smaller than the middle value, and these are the values which are greater than that and with two arrays, we have to still find that common value which is going to give us all the value smaller than that and like all the values greater than that. So, in order to do that, I have to kind of like keep on looking to the array elements. If I can individually kind of get what is the what is the half? What is the half value for each one of them. And then if I compare them and based on that, I can say that like I am interested in... So they're looking for the values or in this case, or for them, and then if I have to compare like, which middle value is it. So, like using that, using those calculations, we can kind of like determine how to keep on doing it on a binary level like like a more like a logarithmic runtime so that we can kind of get there, much, like much less comparisons that we can do. So, in order to do that, if I kind of like define. Stateless Snake: Sorry, can you repeat on that one? The Wild Husky: So, what are you trying to do, you're trying to find the median faster, and then try to find the medium and the second one. Yeah, this like finding the median, or the first one and the second one and then trying to compare like, what what would be the what, what part of the array would I have to compare, in this case, and, I mean, I'm just considering one example here, like a smaller array, but like idea is to, like check the like, concatenate, like two sub arrays, in this case, it will be the second part of it, and in this case, it will be the first half. So when we concatenate that we could like narrow down the search only for this side, like the second section, the second half of the area one and like the first half of area two, and then we can keep on comparing it seeing that I came, like probably my median is going to be somewhere in the second half of area one, or it could be in the first half of array two. And then you keep on comparing the new median, which would be like elected is like one more value with between five, we're going to compare that value with a median of three and four. So we'll notice that like, in this case, now, array two has like a value which is smaller than three and four. So, we will reflect say the like now compare all the values, which are in the second half of array two and like basically all the values show in the first half of array one. So, this may be just like reducing the number of search operations by just company median at a time and this would all stop and we get to the point where we only have like one value to compare between them and then we will see the like, whatever the middle value is now we are just going to do a... now whatever the values that are left are basically like the... is going to be like one or two values and based on that you can determine whether that is the final median or not. Stateless Snake: Okay, can you run your like, like each step on this example? The Wild Husky: Yeah, sure. Stateless Snake: Just to make sure, the median would be... can be double as well, right? If it is an even number. The Wild Husky: Right, yeah, I mean, that's how we will see how the median for those two sorted arrays, it will now be three plus four divided by two because it's an even size array. So, it will basically be like the sum of them and the average. So, it would basically look something like this, why is this like splitting this based on like a middle value, so, basically, we have like one which is going to be on the left section and this like three and four are going to be on the right section. Similarly, when I set this one to and then when I split is basically just like half of the size of the array and like literally whatever and since we are rounding it to the lower integer like to the floor, so it will be select out all the values that are greater than that to the next section. So it will look something like this and now based on the middle value, and now we have to just keep on comparing the values of k has since in this case my first array has and we like it has like the number of elements in there are look like if I have to keep one copy of this case. If the size of the first one is greater than the size of the second one, then we have to kind of do... Let me see how it will look like when it's like an evenly sized array. So, let me also change it according to the respective different size. But if you'd like an even size array, it will be select compare three and five. And like based on that it will pick like like in this case in three smaller than five, it will basically say that all the values are smaller than three. So basically like now my second always maintain like a start and end. So in this case it starts initially was zero, and in this case was two. So like once we find this medium, we are going to update the start to still remain the one because we are going to look for values in the second in the second half. And the end would be the same. In this case, it would be zero, like to keep on doing this comparison. Stateless Snake: So how did you come to a conclusion like it should be in the second half or the first? Once you do the find the median? Like what comparisons? What do you do to determine which half you need to check? The Wild Husky: I'm just basically comparing the middle values and just using that as an input to figure like all the values which are going to be anyways going to be like later than the middle value in this case, and all the values are going to be like smaller than the middle value in the in case of the second one because like we are in this table, all the values are less than five. So that's that's like two, whereas for three, which is going to be like three and four, which I can only create within three are currently greater than equal to three. So I'm using that logic to that while I got set up. Stateless Snake: You compare the medians of both and the smaller median will be taking the right half and larger median will take the left half? The Wild Husky: Yeah. Stateless Snake: You compare three and five. And since three is less than five, you pick the right half for the first array and left for the second array. The Wild Husky: Yeah, I mean, I'm considering Yeah, in this case, I'm considering that when I'm also considering the size of the array being seen, but it's in case the size of array are different than I think it would vary it would probably not be the same way I can do that in this case. Stateless Snake: So in this case, like the second array and index should be zero, right? The Wild Husky: So in this case five is... Yeah, I mean, this is kind of the middle and index will be zero. I mean so in this case, I have to update the start here as well. Stateless Snake: So one of them should include the mid value I think. The Wild Husky: Yeah, this is correct. Start will basically be three and four and this case start will be zero and one. So basically we have three, four and two, five. And now we are going to compare the normal values. Stateless Snake: Like when you divide it should be like when you're divided into two halves like you're including median in both halves? The Wild Husky: Good question. So in this case, it contains the values in this case. So three and four are no... I think I don't need to include it in this one. So this case, let's start zero end zero, this one would be three and four, which is clear to the one and two. I don't need to include the median in both of them. In this case, we are going to include the median only on the right section, so if I kind of go with that approach, so now if I do the same thing of finding the middle value of array one, which would again be since announcing the size of the array two so I can, I simply have to... I think this is where it has to be like the end condition, I mean, since I'm using a smaller range of complexity with computing, so in this case, it's basically like a size of array two, it would just simply be the ratio of these two with like the average of these two. And it would also do the same thing if I was including the median here, which is like two and five, but in this case, if the medium is significant, from still considering this array of size two, I think I should probably still be excluding the value of typically the value of this case. The values are exactly the size. And then we have to so I think I should be ignoring the second value, because it is of it has to be of size either two or has to be of size one, if it's one, then we just compare the two values and we find the value which is of size two and six. So in that case, we are just going to pick the greater of the two. But in this case, since we have three plus four by two, so I think I will actually include it in this case, as well because you have found the median. So I think it's I think, the same logic which was will be happening, like an odd number of elements if we have 1 3 4 2 5, so if I do the same thing here it would basically be only starting from zero and zero and one so we're still gone done the same thing, but in this case, the start and end value are one and two, just correct it was to give me 1 2 3 4 5, the output is three instead of 3.5. I'm kind of being confused if I have an array of size two and five. And if we do the same thing it is going to like now we have like the median calculated. 3.5. And now we're going to compare all the values and see that 3.5 is greater than three. So we're going to have all the values which are smaller than three point like less than the median, which is going to be two in this case. So this is going to be zero and zero. And now here it is still going to be three and four. So it is going to give me 3.5, whereas in this case, it is going to only give me two, so we cannot return 3.5 because those should return three in this case. So I have to keep on comparing 3.5 with two and see that if it can be reduced to... Yeah, I think this will know that it is to in this case it is producer to especially... Stateless Snake: How did we reduce 3,4 to 3? The Wild Husky: So I mean, I didn't do that the median part here is I think is the median is 3.5. And we are going to look for the values which are going to be less than three, because in this case, the median will be two. So whenever the values are compared, we are going to consider the second half of it. And we're going to consider the first leg the left leg, the first half of which in this case, 3.5 value less than 3.5 is three. So we're going to have an area of input three, and in this case it is going to be so I think this has been kind of like kind of like confused because if I have already considered to for getting the median, and now I can't see the like it will not have it will not be like an empty list, it would still be... Compare the value wouldn't be the one which is going to be returned back. And I think that's what I was trying to see if I can do that thing to get like just one element from both the arrays and then I can just compare them and whichever is greater is basically going to is the one which was returned back or in fact in this case, I could have even done with three whenever I had like 1 3 5 2 5 6 and even in this case, it could have been done in the space that I can find find the medium on this one to 2.5 and then by... Stateless Snake: So are you like... I'm kind of lost, like how this is going to give you the results because every time when you tried to find a median on each list, you're reducing the size of the each list by half right? You are removing elements by half... does that mean? What if there are two elements in the first array and 100 elements In the second array, for the first iteration, you will be left with one element in the first array and 50 elements in a secondary. The Wild Husky: Yeah, so yeah, I mean, that's what I'm saying. So there's like a slight difference between our two arrays of size. But I think when it comes to them being different, will basically be like going to compare the size of it if in case whichever is greater, so we are going to in case like, so whichever element has greater length, so it would basically be looking to that. So... Yeah, I mean, I think I just use that assumption currently, like, I also mentioned that, like, I'm considering the size of the arrays to be same and not different. But so, when it is different, in that case, we are still looking for, like a value, which is going to be like a subset, in this case, in this case, like, they both cannot have the same like the middle value, because, like you said, like the size is different than, like, it could be like a, like a different set of values from the second array, which I need to use, whereas in the first array might just be like one value, which is enough for me, but I'm not able to like, see, how... Stateless Snake: Did you understand my question like where you might be missing the solution might not work? Because if there are like, suppose if it is like, one on one and one not two, and you have another array coming from one, two, median would be 52? Right? 51. Right. So here, once you do the initial running, you'll have like, one on one. And here you'll have like the 1-50. The Wild Husky: No, in this case, I will have like all the values which are greater than that, because in this case, the median is, right. Stateless Snake: So once you compare the medians, what you're trying to do is pick one on one, from here and you pick 51 to 100 in this, right? The Wild Husky: Right. And it is going to keep on doing a comparison until it finds like a smaller section in this case, because 101 would always be greater than like 75 to 100. And also it could be greater than I think that's where the issue comes into play. Because once it keeps on doing that it eventually... fail for like the values are greater because we have to like stop. And whenever like one of the size of the array elements are because 101, it's not going to like make any difference because it's just like a size one. So we have to like use what we have here. So I mean, in this case, like since we only have a size of two, like these are only going to be like two elements that are getting added. So so this is like the condition where I have to like stop. So that's what I would like figuring out like how to end this loop because once we get like one element or two elements in one of the arrays, that means this is not going to like make any big difference because there's like not many values, which will determine the median. So like now in this case, I have like compared what could be the what would be the median here. So it has to compare it with either the start value and just see which one is which one is smaller. And then based on that it is going to determine what for the median for the complete array. So I think that's what I was kind of like getting off to this point is to 101, and to see 101 and you don't have to process it any further because 101 is not going to go any further because it's very small. But like 51 to 100 can be further reduced, but we don't want to already on the median one for people to see is something like that. It is something like that, in this case, still though... median is still going to be two. It's going to be like 51 or something and then we are considering all the values which are smaller than even in this case, if we consider zero, and that's where this loop would end and then we will have 51 to 100 in this case, because the values are still like small, I mean, we are considering based on the current median, we are considering all the values which are greater than that. So it was similar zero and 51 to 100. So, we have to use the... so I think it will still be I think I'm just thinking like, if in case we have these values will basically be the average of the current medians, because eventually those are the those are those are the two values which are going to determine what is what would be my final mediums you can give the stuff in case any other lengths are different. So, we are going to compare is going to compare what is the. Stateless Snake: You know, I feel like still we are missing something here, because if it is not one, one or two, not four. So your approach would say like you divided into one, 102. And you go into 103 and not four, right? So here are the initial decision, like what to have, say, we'll be picking. The Wild Husky: I will be picking the first half in this case, because these are the, like the smaller values compared to the median in the middle one, and also selecting the value of this mean, median is kind of like, currently greater than that. So it would be like 101 to 102 and like 51 to 100. Stateless Snake: Okay, then you compare it again, right? So it would be like 101, and 102 as a separate. And here, it would be like 51 to 75 and 76 to 100 I'm guessing. But in this case, again, if you follow the same logic you should be picking this up right? Yeah. So in this case, you're throwing away your solution you'll know where you're gonna reach it back. The Wild Husky: Should not be because the mean in this case would be somewhere in this range like 51 to 75 so cannot be it. It has to like find like a period in this case, which is like look for all the values in the... if I find the middle value from a smaller one that I can use that to determine like where exactly with that median fit in the larger array. So that way we can see the like all the values which are going to be smaller than this median is basically going to... Stateless Snake: Finding the median is something like how many elements are less than like finding the rank element like if you have like length of L one and L two you need to find an element which is greater than L one plus L two elements L one plus L two by two elements something of that sort right? The Wild Husky: Yeah, so if we are doing that we are going to find we are going to like pick one value from the first element... sorry, from the first array and then we are going to look for then you're going to look for that value where it fits into the second array. Yeah. Okay. And then we will decide like which part of the secondary is going to be considered a kind of ignored. So in this case, it's 101 is kind of a getting rid of of all the values in from one to 50. So we kind of are, so I'm just considering max in this case, we have something like this which is kind of like greater than 1 to 100. So we are always going to consider everything from one to 100. So we are always this like we are always going to consider all the values which are greater than 51 to 100 because it is always going to be greater so wanted to narrow down from there, to like 51 to 75 before I'm not able to picture how that would look like in the solutions, I mean, even if we have like a value, which is going to compare, and eventually, like, reduce it to like, you know, n plus one by two. Stateless Snake: Now, once you reduce every element in the first array, you will be left with only one element, right. So that you know how many elements you ignored in like, there are two elements you removed, so, you're left with only one big array, and you know, which portion of the element you need to find. Whereas total length would be 100 plus two, 102, you need to find a 52nd, you need to find an element which is a greater than 52 elements. The Wild Husky: Right. Yeah, I think okay. Yeah. Okay. I was totally confusing it with just doing one at a time. Okay. Okay. Make sense? Yeah, yeah. Sorry about that. Yeah, I just totally lost the question. And just kind of like, went in a different direction altogether. Yeah, but I got a sense. Stateless Snake: Yeah, yeah, I think you got it. The thing is, like for the from the initial approach, it will not give the solution just because like, you might be jumping or overshooting, ignoring the solution. What you have to do is like, you need to pick an element in one array and try to search for that element in the second array, once you find that every time we will be reducing the number of elements in either of the arrays, right? So one of the array will be empty. And then you will know how, with how many elements you need to find in the secondary that you're going to get. But there are a few edge cases in this like, coming to the even and odd kind of thing. But they're all the idea is to find one, pick one array and do a binary search. And the one optimization we can do here is like picking the smallest array, do the binary search on the smallest array. That would be one of them. The Wild Husky: Yeah, yeah. Because will be faster. Yeah, yeah. Stateless Snake: Okay, yeah. That's all. For the feedback. I had like, the initial solution you provided like the for the first problem, it was really good, like you asked relevant questions. And before jumping in the solution, and you come up with a straight away optimal solution, and the code is flawless. I see. And I really like the implementation, and everything is neat. I think you are already familiar with stack, and straight away picking the right data structure is a good thing. And coming back to the second question, I'm not sure like, have you heard of this question or similar question? The Wild Husky: I have heard of it. But I think I was just kind of like approaching it in a very different direction. So like, I was just kind of like not following the question properly. But I think I've heard of it. But I've never solved this question. I definitely feel like this is a very important question to practice. So we'll definitely... Stateless Snake: Yeah, one suggestion I can give you on that one is try to, before trying to figure out an approach, like try to run your kind of solution with different inputs. So that you can see like, once you think you got a solution, try to come up with an examples where you can break it. That would help you like to like to... spend a lot of time here trying to make your approach work. But try to see like, is there any test case which can break this right? Now, that would help you to eliminate any approach you maybe may not work or something like that. But apart from that, I really like your problem solving. And I like your coding style. The Wild Husky: Thank you. Sorry, but I think I really messed it up. I don't feel very good about solving the second problem. I should probably be doing better than this. Stateless Snake: The second problem is on the harder side. So even if you come up with idea, like coding would be a little challenging on this one. The Wild Husky: Okay. Yeah. So yeah, that's how I just follow I definitely feel like this gives me like an idea about like, where I stand. Stateless Snake: Actually if you want, I can probably do it for you, too. It's in leetcode, hard problem, I think, if you want to follow my link. Oh yeah, it was nice talking to you. Do you have any questions? The Wild Husky: No, no, I think thanks for taking your time and like, you know asking me an interesting question. So no, I think it helps me to, you know, figure out like where I stand right now. So yeah, allow me to practice more things. So, no, I think I am pretty good right now. Thank you. Stateless Snake: Okay, cool, nice talking to you. The Wild Husky: Have a good one. Stateless Snake: You too, bye.
Want to get some practice yourself?
Become awesome at interviewing, and get actionable feedback from engineers at top companies – it’s 100% anonymous!