Interview Transcript
Lexical Panda: Good afternoon. Hello. How are you doing?
Wily Tornado: I'm doing quite well. How are you, my friend?
Lexical Panda: I'm doing well as well.
Wily Tornado: Excellent, excellent. Wellness established, I suppose.
Lexical Panda: I'm sorry?
Wily Tornado: Wellness has been established.
Lexical Panda: It has been established, of course.
Wily Tornado: course.
Lexical Panda: So, uh, just to get started, um, what is your objective? What are you looking to get out of this session?
Wily Tornado: Um, oh, um, I want to get better at, um, just programming on the spot. I have a tendency to freeze in actual interviews. I want to work through that. Um, and, uh, I'll be honest, My data structures and algorithms, when it's things I'm familiar with, I do well. But when it's things I'm more unfamiliar with or a completely new problem, I have trouble figuring things out on the spot for the first time. So those are the things I kind of want to work through.
Lexical Panda: Got it.
Wily Tornado: And I'll also say that sometimes I know a problem and I know what to do high level, but when I start writing the code, I get mixed up with the conditional logic. Um, so, so these are the, the issues I, I have. And, um, at you, however you want to address that, um, you have that, uh, liberty. Yeah.
Lexical Panda: No, this gives me an amazing context actually. And, um, so I had like a couple of questions in mind, but I'm going to change those now because this is a Slightly different scenario. This is good. This is good. So what we'll do is, uh, we typically do like 2 questions, and that's the format I've seen in [REDACTED], um, in an hour. So about 20-25 minutes questions, and then we'll leave like 5-10 minutes at the end for any Q&A, or if you want to ask me anything or whatever, right?
Wily Tornado: Yes.
Lexical Panda: How does that sound?
Wily Tornado: Sounds great.
Lexical Panda: And if you like, do— yeah, if you just, uh, crack them, we'll do one more or something like that. So that's not an issue as well. So from the dropdown, you can pick the language of your choice, and then I'll introduce you to first question. Okay. And you're doing JavaScript. Okay. So, let me actually take all of these out for you, so I can write my question. I'll leave this one.
Wily Tornado: Yeah, that's what I thought actually, here.
Lexical Panda: Okay. Okay. Okay, let me, let me introduce you to the first question. And I'm not like super familiar with JavaScript. So if you think that this data structure doesn't fit well in JavaScript, you think— I, I think we should be okay. But if you think like, hey, this is not implementable easily, then let me switch up the question.
Wily Tornado: I'll let you know.
Lexical Panda: Okay, so I'll keep it generic. We are given a list, right?
Wily Tornado: Yeah.
Lexical Panda: And it's like, okay, okay, but then the list could have a nested list. So something like this. And maybe even things like— I hope my God, my, uh, one more, I guess, right? So the elements at this level, like 2, is level 1, but This one is at label 2. This is label 2, but these guys are at label 3, right?
Wily Tornado: Mm-hmm.
Lexical Panda: What we want to do is find weighted sum. So what I mean by weighted sum is— why is it doing this? I don't know. Weighted sum. And what that means is number multiplied by label. Sum all of them.
Wily Tornado: Okay, you want me to just do it?
Lexical Panda: Yeah, um, if you want to talk about a high level how you will approach it or just want to code it up, I leave it up to you.
Wily Tornado: Um, so this is the one I feel like I could kind of just get going on. I feel like I can do this pretty straightforward. Um, basically we're just iterating, um, through the list.
Lexical Panda: Mm-hmm.
Wily Tornado: And we're going to seed the function with a value and a level, and the initial level will be level 1. And as we iterate through the list, every single item, it will either be of type value or of type array. And if it's of type value, All we do is accumulate it, multiply it by whatever level our param is. If it's type array, we just recursively call the function and increment the level by 1, and then that, uh, that call will return a value, and, and we just use that as an accumulation. Uh, does it make sense?
Lexical Panda: So that's perfect because you identified the recursion as a pattern here that can be useful. Your high-level approach is perfect. What do you think runtime would be of this algorithm?
Wily Tornado: So the runtime will be— it'll be at least O, and But I think it'll be O of N times H, where H is the height. Or O of N plus H, because on every— at every level we have to do the recursion call. So I would, I would account for that.
Lexical Panda: Yep.
Wily Tornado: H can never exceed N, so we could just say it's O of 2N, which amortizes just O of N, right?
Lexical Panda: Oh, yes, yes. And it will take some additional memory, right? Because the recursion will— you'll have a stack. So, as the deepest you go would be probably the extra memory that you—
Wily Tornado: Um, I, I feel like, uh, somewhere in, in the calculation I should have, uh, been accounting for the, uh, like the O of H. And, and that's where you're right, it's in the— it's on the memory.
Lexical Panda: That's it.
Wily Tornado: So the worst case memory is, is O of N because N could be H worst case.
Lexical Panda: Right, I think you have a great level of clarity on this now. So, uh, let's implement this because that is the other problem that you have. So want to make sure that you can actually implement the idea that Thank you.
Wily Tornado: Yes. So let's call this rolling product aggregate, aggregation. And we're going to say we have v, which in this case is a number. And then we have our level. And then v is going to either be a number or array type.
Lexical Panda: Mm-hm.
Wily Tornado: And we could say if array.isArray, Um, v. Um, in, in this case, we'll do the for loop. Um, otherwise, uh, we're just going to assume it's a number and, and return it. Um, so in the case we do the for loop, um, we'll start with a sum. And all we'll do is just call the function on itself, v of i.
Lexical Panda: OK.
Wily Tornado: Passing in the level plus 1. And let's see. Down here is where we actually do the level multiplication, and that's, that's the rolling aspect. And then level will just be initialized to 1. Um, so I could go ahead and just console.log the output, or I could trace through it, whichever you prefer as the interviewer.
Lexical Panda: Uh, let's, uh, let's create a simple example and so that we know the way the output's value. And because of my example, a little too complex, so Let's do something like, yeah, uh, yeah, something. Yeah, yeah, that's fine.
Wily Tornado: Okay, let's trace through this real quick. Um, so we call, uh, the function on this array. The very first time, it's going to be, uh, v is going to equal 2. Um, so when v is 2, um, well, I'm sorry, It— in the very first one, v is actually going to be the array x.
Lexical Panda: Yes.
Wily Tornado: Yes. So, it's going to get to line 12. It's going to say this is an array. And then, we're going to for loop into it. The first v , that's going to be 2. It's going to recursively go back into itself, increment the level to 2. Um, and then it's going to call, um, v times, uh, 2, which, um, I don't believe that's— is that technically correct? Like, would you say this is— because this looks like level 1, so I think—
Lexical Panda: Yes, it is level 1. Um, it should be more like Um, so wait, the first— because I think you skipped something. First time this gets called, v is x, right?
Wily Tornado: Yes.
Lexical Panda: So it will enter this loop, the first if condition.
Wily Tornado: Yes.
Lexical Panda: Then it will loop through all the elements, right?
Wily Tornado: Yeah.
Lexical Panda: And for that, it is going to recursively call this function.
Wily Tornado: Yeah.
Lexical Panda: And label 1. Okay, so that's why you are trying to set it at 0. Okay, got it.
Wily Tornado: Yeah, um, because no matter what, it's going to add the level, so I need to do the offset, um, when it first enters.
Lexical Panda: Um, sorry.
Wily Tornado: Um, yeah, because the, the assumption here is that it'll— we'll never initially call it with something like 2, right? It'll always be wrapped in 1 array. So that's why we do that little offset. Um, so, um, so at this point, uh, it's, uh, 2 times 1. Um, so The return value of that is 2. So at this point, um, sum is going to be 2. Um, we're going to increment, uh, i to 1. Um, so x of 1 is going to be 3. And, um, we're going to call the function again on, on 3. Uh, we're gonna hit line 20 on the next call. So it's gonna be 3 times 1. And then that's obviously 3, and then it's gonna add that to the sum on line 17. So sum is gonna be 5.
Lexical Panda: Mm-hmm.
Wily Tornado: On the next call, when i is 2, well, that's an array. So when we recursively go into the function on line 14, that's gonna be true. We're going to initialize a new sum. And then, um, on line 17, it's just going to, um, do that, do that loop again, uh, 2 times the next, uh, 2 values, except this time, um, level is going to be incremented where level is 2. So the very first time, it's going to say, uh, 1 times 2. And it's going to add that to the sum, and then it's going to say, uh, 5 times 2. And then add that to the sum. And then that sum therefore is gonna be 12. We're gonna return out of that and it's gonna be 12 plus 5. So sum is gonna be 17 in the outermost function call. At this point, we're going to get to the last element where i is 3. x of 3, we're gonna index into that one value. And again, we're just going to drill down into the recursive function, uh, do 1 times 1, add it back, uh, we're going to get 18. Um, and when we're done iterating, um, we need to return the sum. So, uh, that was a mistake.
Lexical Panda: So that— I was going to— I was going to ask you to run. Yes.
Wily Tornado: So if you want, I could run this with code or, uh, take it.
Lexical Panda: Yeah, yeah, let's, let's run it and make sure, uh, to do that. Yeah, so one time, it's pretty easy to do.
Wily Tornado: So Oh, let's see. Some should be returned here. Because since I used let on line 15, it was scoped to this if block.
Lexical Panda: Ah, right, right, right.
Wily Tornado: So it's just a scoping issue.
Lexical Panda: Yep.
Wily Tornado: Okay, there we have the value.
Lexical Panda: Yeah, got it. So that was pretty good actually. So I have to level up, uh, level up the questions a little more. Okay, uh, you ready for another one?
Wily Tornado: I'm ready.
Lexical Panda: Okay, I'll go back to the talk. Okay, so that's how you can see. Let's say we have— yeah, this one is good. Let's say we have a list of car rental requests with start and end time.
Wily Tornado: Okay.
Lexical Panda: Something like this. Given a list of car rental requests with start and end time, assign cars to rental in such a way that the total number of cars used is minimized. So I'll give you an example, so to make things clear, right? So let's say we have— we are given this, uh, it's start and end time. In a list, right? So the first one says that I need to pick up my car at 1 o'clock and I'll return it at 3. The second one says pick up at 2, return at 5, uh, so on and so forth, right? So we want to find out what is the minimum number of cars we will need to satisfy this request. So, yeah, let me stop there.
Wily Tornado: I'll ask questions. So I know this problem well, but I— it's good because I know it well, high level, but I have a lot of problems with the conditional logic. So this is an overlapping interval problem. We're going to go through, we're going to sort by the first value. in each, uh, tuple pair. Um, and then we just loop through and we just do the overlap logic. Uh, so this is a problem I, I have a lot of issues with in the past, so it's good you asked it. Uh, because when it comes to the conditional logic, that's where I kind of, um, I get mixed up and it just kind of goes south. Uh, but high level, that's what I would do. Um, since, you know, we're training, uh, I'll kind of walk through the conditional logic, uh, I guess right now, uh, since I know that's where I always get stuck. Um, so if we did that initial sort, um, this is—
Lexical Panda: And what are we sorting by?
Wily Tornado: Uh, so if these are a tuple with 2 indexes, 0 and 1, we're going to sort all the tuples in the array Uh, by, um, like tuple of 0, so the, the start time.
Lexical Panda: Start time?
Wily Tornado: Yes.
Lexical Panda: Okay.
Wily Tornado: Um, is something— am I missing something? Am I flawed?
Lexical Panda: Uh, yeah, I want to, like— but I would— if you, if you want to talk about, uh, what you are thinking, like, I don't want to interrupt it, but But my question would be, what is the reason for sorting?
Wily Tornado: So the point of sorting is that if you sort by start time, then you have a known rule as you iterate through it. So as we iterate through it, we have a guarantee about the element to the front and the back of us. And then based on that, that's why we could do simple conditional logic to determine where we are. And essentially, I think the idea here is that if, like, we can— Like, my idea, my idea essentially was like, do the sort, do the overlapping intervals, and then when you can compress the intervals, however many tuple pairs you're left with, that's how many rental cars you'll need at the minimum. But I don't know, I guess I'll put it back to you. Am I, am I just jumping to a solution that isn't real? For this problem?
Lexical Panda: Kind of, but— and it's not totally invalid, but, uh, why don't we like actually manually do this, right? So, uh, like do it manually, right? So sort it as you are doing now and then walk through that logic of how you are thinking and then see how many cars will we actually need. Let's find that out first, and then you walk through the step and think through, like, does it work, your solution, right?
Wily Tornado: Okay, sure.
Lexical Panda: Um, because there is potential that it could work, but it, it's slightly, uh, it could be slightly more complex than—
Wily Tornado: Well, I think I'm understanding what— because I think it's more like We're not trying to collapse the interval. We just want to see at any given time how many are overlapping, but we're not merging them. It's not like— it's not really merge interval. It's more like, um, we're— we just want to know how many are overlapping at any given time. So it's— so it's like, it's a little different, and we need to, like, bookkeep a little, I think.
Lexical Panda: Right, right. Like, so yeah, let's walk through. Like, let's walk through. Let's first logically find out how many cars we'll actually need in this case, right?
Wily Tornado: Okay, so let's look at this. Um, just walking through this as a pure logic problem, forget about coding. We look at the first, uh, start and end time, 0 to 2. Okay, that's obviously going to be 1 car. Um, So, uh, cars 1. And then when we get to, um, 1 to 3, uh, that's gonna be another car, um, because there's—
Lexical Panda: Yep.
Wily Tornado: There's overlap between specifically times, um, 1 and 2. So, um, So we can think of like times like this, like monotonic increasing tick. And then, um, if we wanted, we could look at how many cars are overlapping at a time as we go. So, um, for the, for the first tick, There's 1 car. For the second tick, 0 and 2 and 1 and 3, they intersect. So for the second— for the next tick, we would need 2 cars. For the next tick after that, there's overlap still between 2 and 3. So that's 2 again. At the next tick, we would drop 1 because 0 and 2 falls off. But they're still 1 and 3. Um, so, well, actually, I'm— I think something's wrong because I, I'm not looking ahead enough now to 2 and 5. Yes. So, um, it's— so it's almost like I want to order this a little differently. Oh, I guess it's already commented. So what if I visualize it like this instead? I mostly want— I'm trying to visualize the space. And then we look vertically. Um, so—
Lexical Panda: The last one should be like between 4 and 7, I think.
Wily Tornado: Oh, yes.
Lexical Panda: Uh, yeah, yeah, yeah, something like that.
Wily Tornado: All right, so, um, so then we could actually maybe put the numbers down here. So at this point, it's how many? 1. And then how many at this point? Uh, 2. Uh, how many at this point? Uh, looks like 3. How many?
Lexical Panda: Well, uh, uh, at 2, right, the, the car comes back at 2 and this guy needs it at 2. So we can actually assume that we can give it to him, right? We don't need a 3rd car at that point.
Wily Tornado: Oh, um, let's see. So, so this guy— okay, yeah, because this guy's leaving. So I guess it's a question: if this guy's leaving, do we count it? Is it like, is it inclusive or exclusive?
Lexical Panda: Uh, by that— so let me clarify in real terms, right? So if the guy returns at 2 And somebody needs it at 2, then we can use that same car.
Wily Tornado: Okay, um, so, so at 2, um, 2 should be 2 because—
Lexical Panda: Yes, yes.
Wily Tornado: Yeah, okay, I get it. Yeah, uh, so at 2 it's 2, um, and then we get to 3, and at 3 it looks like there's 2 people using it at 3. We move on to 4. Looks, it looks like there's 2 at 4. Looks like there's, I think, 1 at 5 because 1 person leaves, 1 person takes it. At 6, um, there would be 1. Wait, um, no, that's 1, 7, 2.
Lexical Panda: Yeah. 2.
Wily Tornado: That's 2. Um, at 7, someone's leaving but someone still has it. I think that's, um, 1, right?
Lexical Panda: That guy's 1. Yeah, yeah.
Wily Tornado: Um, and then, uh, for 8, I guess they're returning the car, so it's, it's 0, right?
Lexical Panda: Yep.
Wily Tornado: And then, um, the total number of cars used, um, is minimized. So the most minimal we would use in this example is 2, because there's never more than 2 cars used at a time.
Lexical Panda: Right. Now let me ask you some follow-up questions, right? So what would be the runtime of this? Because this is interesting.
Wily Tornado: Um, so the runtime of this would be O of n times v, where v is, um, the maximum value, because it's creating essentially a table entry for every possible value.
Lexical Panda: Because you are going clockwise, right? So you are actually doing interval, interval, interval, interval. Like that's how you are going to go, right? Your logic is going to be at hour 0, hour 1, hour 2, hour 3, stuff like that.
Wily Tornado: Yeah. Well, I think, yes. Yeah.
Lexical Panda: So if you have like 24 hours in this overall, like a day worth of reservation, then you would have, you'll just go 24 times.
Wily Tornado: Oh, you're right. Yeah.
Lexical Panda: So that's not too bad because it has nothing to do with cars. You'll just go by like time by time.
Wily Tornado: Yes, uh, but for every time, I think we would go through the dataset, um, or, um, yeah, we may just be able to, um, I, I can visualize it almost like an adjacency list. I, I don't, I don't even know if this makes sense, but that's what comes up. Where, like, with an adjacency list, um, like, 0 through 24, and then the start time is like a node in the adjacency list. But the thing is that that would not be accounting for the whole interval of each item in it, like the end. We would need to— so that wouldn't work.
Lexical Panda: Um.
Wily Tornado: But from a brute force perspective, we, we can do it just by having like 0 through 24 and just iterating through every range. Um, yeah.
Lexical Panda: Um, like, so, sorry, like, which way are you leading?
Wily Tornado: Uh, go Like, take every request and manipulate, or you go by, uh, like, like, um, loop, um, 0 to 23, and then within each one of those loops, um, loop, um, each, uh, interval, and then within that, like, another loop where we, um, loop Like, as we loop each interval, we're like looping the range. And then on every single range, it's like add times range plus 1. Um, so this is the brute force. I'm sure there's a better way, but this is what's coming up for me now.
Lexical Panda: So, okay, let me add one more challenge to this, right? So let's say your idea could work, but then if I say the time is like includes minutes, then what would we do? Um, or if the reservation is for months and months, right? Not just one day.
Wily Tornado: Hmm.
Lexical Panda: How would that impact your approach?
Wily Tornado: Um, well, what it would mean is we, we couldn't iterate by, by bucket size because right now we're iterating by, uh, our buckets.
Lexical Panda: Yep.
Wily Tornado: Uh, so I wonder if there's either another data structure we could use or a way to like invert the way we're iterating through it. Um, so what if instead we, um, I think—
Lexical Panda: Why don't we do like— let me give you— yeah, think through, and if you want, I can give you a slight, uh, approach, and then we can go from there.
Wily Tornado: Um, Okay, what's the hint?
Lexical Panda: Okay, why don't we, as you said, right, start from the beginning, the earliest needed car, right? The sort, like the list, right, from start time.
Wily Tornado: Okay.
Lexical Panda: But then we go to the first reservation and say, okay, this is good. We'll put it into some kind of list called active car. list, right? Active car list.
Wily Tornado: Mm-hmm.
Lexical Panda: Put that guy in. And then we come to, uh, and we note the size of this, uh, this list, the active car list, right? Then we take the second reservation and we say, well, let's see in our active car list if the start time request I know when this starts, right? So for example, our request starts at 1, right? Second request. So we say, hey, the end time of what is the earliest end time of what is in that active list, if it is less than my start time, then I can kick that thing out. Like it's done, it's done, right? Right. And then I put the new car in and I keep track of the maximum size of active cars. And at the end I would know what was the max size we saw during this period.
Wily Tornado: Um, yeah, so if I, uh, let me try to walk through this.
Lexical Panda: Yes.
Wily Tornado: So on line 21, let's take this example. Yeah.
Lexical Panda: And I didn't give you the solution, right? There's like some twist to this, but at least at a high level, if you can walk me through what I just said and maybe refine that, and then we'll talk about more challenges into that. So yeah.
Wily Tornado: Well, I almost feel it's hard because it's almost like we need to iterate through 2 lists at once. That's how it feels. Because there's the start, and whenever we see a start, it's like, uh, cars plus 1, and whenever we, we see an end, it's like cars minus 1. So that's what we're keeping track of. Um, but Um, it's hard because like let's say this was 20, so it's like cars plus 1, so cars is going to be 1, and then we never like see it again. Well, maybe we actually need to do 2 iterations.
Lexical Panda: Um, let me, let me help you, right? Let me actually show you what I'm talking about and then we'll take it from— how about that?
Wily Tornado: Yeah.
Lexical Panda: Okay, let me take this out, right? Let me take this out. Let me just say this is our input. And we— so the first thing we did is sort by start time, right? So you already have this list. And let's keep it at 2 for now. So that is step 1. And then step 2 is iterate through the sorted list.
Wily Tornado: Uh-huh.
Lexical Panda: That's good, right? Then we'll keep active cars. This guy, right?
Wily Tornado: Mm-hmm.
Lexical Panda: And so we get this first guy. We say, hey, are there— this event starts at 0. Are there anything in the activeCardList that ended before 0, right?
Wily Tornado: Uh-huh.
Lexical Panda: If so, kick it out. So there's nothing here, so fine. And then inject our guy here.
Wily Tornado: Okay.
Lexical Panda: Okay. And now we go to the other element, this guy, 1, 3, and say, hey, this guy starts at 1. Are there anything in this list that ends before 1? The answer is no, right?
Wily Tornado: Yeah.
Lexical Panda: Then we have to just add it to this. Oh, that 1, 3.
Wily Tornado: Okay, I think I know how to solve this now.
Lexical Panda: Got it?
Wily Tornado: Yeah, I get it. So, um, We need to accumulate the tuples. And then on each accumulation, we need to do a, like, a take-back loop. Where we— and then, uh, but with, um, early, um, early termination, if, if we get to, uh— Yeah, well, maybe we don't need the early termination because we need to go through the whole thing. But essentially, yeah, we need to do like an inner loop where we're looking at what we currently have. And then evicting. We needed like an eviction mechanism, right? And then we also keep track of max active cars.length, right?
Lexical Panda: Yes.
Wily Tornado: And then that's the bookkeeping for how we know what's the minimum we could have. Yeah. And then I guess I should add a little more definition about like the take-back loop. So, um, so if we have, um, if we Have active cars. And that's in it. And then we get to, um, what is it, i equals 1. Um, so this is the conditional logic. This is where I always mess up. Um, what we're actually checking for this is Is the new start time equal to or greater than any of the previous end times? And, and if it is, take that guy out. Yep. We evict whatever's in active cars. OK.
Lexical Panda: Yep.
Wily Tornado: So if new active car's start time is less than what is—
Lexical Panda: I think—
Wily Tornado: is it greater than or equal? Greater than or— yeah, greater than or equal to existing active cars end time event.
Lexical Panda: Okay.
Wily Tornado: Um, okay. Um, and then ultimately we're going to, um, return, uh, return the max. Yeah.
Lexical Panda: Okay.
Wily Tornado: Um, well, I think I can give this a stab and try to implement it. Yes.
Lexical Panda: And then I have some follow-up questions for— Oh, great.
Wily Tornado: All right, let's do it. But yeah, yeah, this is good.
Lexical Panda: This is good. Yeah, I think you did good there. Yep.
Wily Tornado: Active cars. And I'm going to sort them. In-place sort by start times. And then for every single time, we're going to say If the new start is greater than or equal to the existing end, We're going to evict, and the way to do that in JavaScript is— it's a little awkward.
Lexical Panda: I have no idea, but I want to.
Wily Tornado: Let me, let me think. It's gonna be K and then the number we want to delete. Um, all right, so, okay, so yeah, yeah, that's it. So, um, effect. Um, And then when that's done, we're going to do the push. I want to say active cars dot push times of i. And then what we're going to do is say. Max equals math.max, max for active cars. And then we're going to return max. There's a very small optimization I spot. We don't actually need to push times of i. We could actually just push the end into—
Lexical Panda: Well, that's good.
Wily Tornado: Yeah. So we push that on it. So then when we do this, we don't need to do this array interpolation. We could just Do it directly. And new end isn't actually used, so we don't really need that. So again, we can just get rid of that interpolation. Okay, um, I guess I'll stop there in terms of refactoring. Those were just little obvious, uh, wins. Um, and I'm just tracing through the code, and I think this all makes sense. Yeah, um, if you want, I could try to walk through an example, or however you want to do this.
Lexical Panda: Yeah, I think that's fine. Uh, no, let's not waste time. Like, maybe try to run it, see if you have any obvious errors or anything. We'll catch it.
Wily Tornado: Okay.
Lexical Panda: And then we won't talk about runtime of this. You can use our example, so yeah.
Wily Tornado: Comment out the other result. It's 5. Is that— I don't think that's right though. When we walked through it, It was like 2.
Lexical Panda: Yeah, uh, I think the splice thing might not be working there. I don't think because it is adding everything. Yeah, yeah, yeah. Um, don't worry about that because that's a language thing, right? So yeah, but let's talk about runtime.
Wily Tornado: Yeah, okay. Um, so Well, JavaScript uses quicksort, so that's n log n off the bat.
Lexical Panda: Yep.
Wily Tornado: So let's see if anything in here is more than n log n, and it might be depending on what the times are, right? So, um, for this outer loop, uh, that's just going to be O, so we're just looping through every single time. If every single one of those adds, adds 1. So in the very worst case, it's, um, oh, it's like O of n, uh, times— I guess I actually don't know what that is because it's, it's technically a factorial. Nothing— that's the time, but it's a factorial function where every single one you have to loop through everyone before effectively.
Lexical Panda: And into n, right? N squared.
Wily Tornado: Yeah, I think— well, it's n times n, right? Yeah, yeah, yeah.
Lexical Panda: No, no, no, squared. N squared. Yeah, n squared.
Wily Tornado: Yeah, that's what it amortizes to, n squared.
Lexical Panda: So n log n part. Gets done overall.
Wily Tornado: Yeah, that gets swallowed.
Lexical Panda: Yeah.
Wily Tornado: And, uh, yeah, so this is an n squared algorithm. Um, I think, yeah, and that's just because obviously there's that inner loop, um, that's bounded by n. So that's why that's—
Lexical Panda: Let's kill that. Let's kill that loop. There's no need for that loop.
Wily Tornado: Okay.
Lexical Panda: Um, so think about what we are trying to do, right? What in that loop you are trying to see is anything that— any reservations that has been, uh, already done, return car, right? You are evacuating, evacuate, like evac evicting all of those right in that loop.
Wily Tornado: Yeah.
Lexical Panda: Every single time. So first idea is, do we need to evict all the cars that has been returned, or could we just— because we need only one, right? So if there is any car that has been returned, then we just evict that and add ours. So the queue size, uh, even though in the queue or in the list, active car list, there will be car that has already been returned, but the end state would be it will only grow till how many cars we need, right? It will never grow beyond that.
Wily Tornado: And it— and that's acceptable because we're already at that max anyway. Um, right.
Lexical Panda: So yeah, we don't even need to count the max anymore. At the end, return the size of that list, right?
Wily Tornado: Yeah. Okay, that makes perfect sense.
Lexical Panda: And that—
Wily Tornado: and that also helps with our time complexity because it gives us early termination, and that—
Lexical Panda: so we don't iterate through all of them, and that's how we killed that, um, Now the only question is though, how would you make sure that you are quickly finding the car that ends the earliest every single time?
Wily Tornado: Can we keep the list sorted by end time?
Lexical Panda: Or can you think of a data structure that will do it for you quickly? Always look—
Wily Tornado: Yeah, we could use a, um, Like a min heap?
Lexical Panda: Yes. Now let's put all these ideas together.
Wily Tornado: Um, I don't have a min heap in JavaScript.
Lexical Panda: Okay, okay, that, that is— but yeah, if you— if we put n times into the min heap, then all you have to do is look at the first element. If it is before the start time, then pop it and inject your new one. Otherwise, just inject new one. And by the time you're done, size of your heap is your answer, right?
Wily Tornado: Yeah. Um, I could pretend I have a heap and just code it.
Lexical Panda: Yeah, let's do that. Yeah, that's a great idea.
Wily Tornado: Okay.
Lexical Panda: Um, I'm surprised that JavaScript doesn't have heap writing.
Wily Tornado: Yeah, it's crazy.
Lexical Panda: Um, yeah, at this point it doesn't have to even compile, right? We just pretend. Yeah, that is, um, heap pop and push stuff. Yeah.
Wily Tornado: Um, so let's see. So what I would do in this is I'm gonna need to trace through this again. So when With the existing end. Instead of doing the loop, I'm going to do heap.push and pass in The new end time, and then if. I'm going to say if it's like heap.peek. Yep. That's where I do the logic. Like, if that's greater than or less than or the new start, right? Yeah. Then I do the heap.pop.
Lexical Panda: Yep.
Wily Tornado: And then I can get rid of this loop. Yep.
Lexical Panda: Uh, even that guy.
Wily Tornado: Yep.
Lexical Panda: Even that guy. Yep.
Wily Tornado: And then I could just do, um, keep that size.
Lexical Panda: Yes.
Wily Tornado: Nice.
Lexical Panda: Now what is the runtime of this one?
Wily Tornado: Um, this one is gonna be, um, uh, so I'm a little fuzzy on how much the heap is, I think.
Lexical Panda: Yeah, I, I'll give you that. Yeah, so heap push, um, heap push would take log of n, and n would be the max, the elements in the heap. Um, so is constant, pop is constant, peek is constant. That's right, 1.
Wily Tornado: So yeah, um, yeah, because when you do the insertion, you're effectively building the heap.
Lexical Panda: So yeah, you are like readjusting the element in the heap, so it's log n. You are not building the entire— building the entire heap is n log n again. Uh, just insert one element, it is log n.
Wily Tornado: So if insertion is log n and we're doing that n times, that means we're doing O . That's our time complexity. Our space complexity, worst case, is n.
Lexical Panda: Yes. Yeah. So we managed to get it from n squared to n log n, right? Yeah. Cool, cool, cool. We are almost at the time, so any questions? We can go over a little bit, it's okay if you want to. If you have any questions for me.
Wily Tornado: I don't have any other questions other than like, you know, general advice, what to work on, any tips or hints, stuff like that, but no questions come up for this problem. independently of those kinds of hints?
Lexical Panda: Yeah, honestly, uh, your logic is very sound, right? Your, um, thinking process is very structured. Communication is great. I think you just need more practice. And, uh, another thing that I would say is, uh, read up on data structures. An algorithm at the most fundamental level, right? Regardless of the problem. What has helped me is just recognize some patterns and know the algorithms like DFS, BFS, heap, hash, stacks, List, uh, recursion particularly. Partition is another very important algorithm to remember. I didn't ask you a question around that, but that's pretty cool. Uh, partition algorithm, very nice. And I almost like have memorized the algorithms. If you ask me like 3 in the morning, wake me up, I'll write partition in no time, quicksort in no time. So that kind of gives you that base. And then, then it's just logic, some practice. Yeah.
Wily Tornado: Yeah.
Lexical Panda: Cool. I hope this helped you.
Wily Tornado: I feel like this is tremendously helpful. Thank you very much.
Lexical Panda: No, thank you so much for your time. And I'll do a detailed write-up for you as well. So.
Wily Tornado: Great. Thanks a lot.
Lexical Panda: I'll be sharing this. in half an hour, maybe.
Wily Tornado: Nice.
Lexical Panda: Take care and good luck.
Wily Tornado: All right, have a good weekend.
Lexical Panda: Bye. Yeah, bye.