Problem type

Meeting Rooms

Interview question

1) Given a list of meetings, determine the minimum amount of rooms required to schedule all the meetings. 2) Given a m*n matrix of positive ints, the value of each point in the matrix is the height of that point. Given two villages in the matrix, find a point to build a “Water supply tower” so that water can flow to both of the villages. Water can only flow from high to low or equal to equal. If there are multiple answers, return the one with the highest height.

Feedback about Professor Squirrel (the interviewee)

Advance this person to the next round?

How were their technical skills?

4/4

How was their problem solving ability?

4/4

What about their communication ability?

4/4

Saying Strong yes. Great questions, thinking out loud, good intuition nice code, func names and vars, modular talked about time/space

Feedback about Rocket Samurai (the interviewer)

Would you want to work with this person?

How excited would you be to work with them?

4/4

How good were the questions?

4/4

How helpful was your interviewer in guiding you to the solution(s)?

4/4

Great interview; thanks!

Rocket Samurai: Hello.
Professor Squirrel: Hi. How's it going?
Rocket Samurai: Going good. How are you?
Professor Squirrel: Great. Thanks.
Rocket Samurai: Yeah, so we have interviewed the last time. So has anything changed from last time? So that we can do this interview like some context.
Professor Squirrel: Right, right. Yeah. So just to remind you, I'm a master's student who's just finished my master's, and I'm looking for my first full time position. So like entry level, software engineering roles. And the only thing that changes last time is I have actually a bunch of interviews coming up this week. So yeah.
Rocket Samurai: Yeah. I think it's cut off. Right. When you told me about you were looking for entry level positions.
Professor Squirrel: Yeah, I mean, that's basically the summary is that I'm like a new grad, looking for software engineering roles, the only thing that's changed is last time is I have a bunch of interviews scheduled this week. So hopefully, be pretty prepared for those.
Rocket Samurai: Yeah. And it will be and be good to like, if you have LeetCode premium. If you can filter questions by those companies and look at just like, get an exposure of like, what kind of questions they are asking most frequently.
Professor Squirrel: That's okay. Yeah.
Rocket Samurai: So yeah, so they'll follow the similar format as last time, we can do a couple of questions, depending on the state. And then we'll reserve like last five to seven minutes for feedback.
Professor Squirrel: Yeah. Great.
Rocket Samurai: For the first question, let's do this one. So let's say you're given a list of meetings. And based on the list of lists on this list of meetings, we want to find out what is the minimum number of meeting rooms, which are needed to host all these meetings? Let's say an example is like this scenario given bunch of meetings, start time and end time. And then the output is two because, like, the first two meetings, they overlap, so really, at least do to host those two meetings.
Professor Squirrel: Okay, great. Just draw like a diagram here. Okay, okay. Questions about the input are the start and end times guaranteed to be whole numbers?
Rocket Samurai: Yes.
Professor Squirrel: Okay. Sure. Are the time intervals open or closed? Meaning like, if I have a meeting from one to four and one from four to five, do those conflicts or are those fine?
Rocket Samurai: Yeah, good question. So they do not conflict. So you can you can place them in the same meeting room.
Professor Squirrel: Okay, so I think that's kind of all I need to know. So we have a bunch of intervals. And we want to know, so the sort of geometric interpretation of the data is like, I'm thinking of like drawing these time intervals on the number line, like I've done here. And then, once you've done so the minimum number of rooms needed to schedule the meetings is just the deepest stack of concurrent meetings because basically like, I mean, it's pretty intuitively clear, I think that if you have five meeting rooms, and there's at most five meetings at once, you can always, you know, you'll you'll have enough meeting rooms. And then similarly, if you had only four meeting rooms, but there was five meetings going on at one time, and you'd be stuck. I guess this is like, the assumption is that there's one room for meeting is that true?
Rocket Samurai: One room per meeting? Yeah.
Professor Squirrel: I figured. Yeah. One room for meetings. Yeah. Okay, great. So I think all I should have to do is sort of why don't know yet how to do this. But what I want to do is to compute the sort of, yeah, like I said, the deepest stack were like the widest overlap. Once a minute with is not the right word, but the most number of visuals that are concurrently intersecting. So you think about how I would do that? So I guess naively, we could think of this as like an intersection graph where each node is an interval, and each edge is the edge relation is whether two intervals intersect. So we can get an n squared time solution. But I hope to do better. So idea, intersection. O(n^2), check all parents and then sorted, we want to find the largest. The well actually finding the maximum clique in a graph is a hard problem. So maybe this isn't a nice approach. Let me keep thinking. Suppose for now, we sorted the input by start time, because that's probably useful, then we can do something that's kind of left to right. And if we were to do that, let me think. I guess you could have maybe like two queues, sort of like, you process the input, in order to start time. And then you keep a data structure, probably a queue of currently open intervals, like intervals that you currently that are currently running meetings that are currently running. And in that queue is instead sorted. If it's like a priority queue where it's sorted by end time, then I should be able to efficiently sort of, every time I see a new start events, before I process it, I can like dequeue from the queue as many times as I need to make sure the excuse me the intervals that have already closed or not. Still in the data structure, and then like I mean, it's not exactly a sliding window, but sort of making it like that where I'm actually I can make this even more simply. Oh, yeah. Yeah, of course. Okay. Okay. So so that's, that's a little overkill, but like, so. So, let me do this worst idea. Think each interval as a pair, forgot to ask this but is every interval well formed and non empty? Like is end always strictly greater than start?
Rocket Samurai: And end can be equal to? So if it starts at one. Yeah, it longer than that one more than the start.
Professor Squirrel: Okay, perfect. That sounds good. Yeah, so think of each interval into pairs and forget this idea. Like that one. So it's easy to introduce a pair of events like starting events, start events add in. And then if I just process a stream of events, sorted by timestamp, and then you just like increment, global counter, incur on start, or end and then return The overall answer. Okay, so this idea I feel like will work and get this linear well, and O(n log n) time we can get guessing is optimal. Probably hard to prove. But I'd be surprised if you could do this in purely linear time, unless the input was already sorted or something. Is it? Is it safe to assume that the input is already sorted? Or No?
Rocket Samurai: Input can be any order.
Professor Squirrel: Yeah, okay. So it will sort of ourselves. And I'm pretty happy with the time complexity. It's not like I really am bothered by the O(n log n). So yeah, I think I'll start getting into the code because I think I have a pretty clear idea. Do you want any more explanation of the of the approach or does it make sense where we're going with this?
Rocket Samurai: Yeah, this looks good.
Professor Squirrel: Great. Great. Sounds good. Language here. Okay, so interval starts can the start and end times be negative integers? Are they always non negative?
Rocket Samurai: They are only positive zero positive. Or something. What does what does that have openly? Never heard of it?
Professor Squirrel: Yeah. It's a jargon for mathematics. That means like, if you have the interval from one to four, that half open interval includes one and excludes four so like, or the kind of outside of the the interval since it's we could take less inclusive would be a synonym. Okay, and then the function is meeting for meeting the list interval. And you want to think we just let's think about this. So yeah. So start. See here, meetings, I want to iterate over this, I guess this topic, technically, already running code and contribute or just writing.
Rocket Samurai: No just writing.
Professor Squirrel: So I want to iterate over all the new things. And then...
Rocket Samurai: We want to run it because there's a different language. So...
Professor Squirrel: Yeah, that's fine. Fine, we can do that. Okay, so iterating over all the meetings. And then for each one of those, I'm going to produce a pair of events that map the meeting and into the two events, which are how do I write this really, I could do like this. So start to use or write so starts in the Start and End editor. So this is, let's this, I wanted to sort of so let's say this could be a list or a vector. And then this way we can make your code is doing what we want and we can print things so let's plan to do that and then come back to the answer for the... say. So, right so there's a list of would it be okay for 13579? And this to enter into and that's that and then and then so that as well. And then we want to run on an apparently. Okay, let's see if that pops into definitions of names. I'll delete the first one at the top of the file. It's complaining interval is not debuggable I'm guessing events and their parents here to destruction, but otherwise, good? That's nice. Yeah, this is okay. This is an updated version of.... That's fine rep here. And the complaint notes, which is a virus that's doing that they do that fine. Yes, true. Complaint is turns. Oh, and I'm doing in here. Okay. Great. So, our input here is the first thing printed. It's the three intervals and then we're printing events on line 63, which is these start and end times in sort of mixed in this heterogeneous data structure list really, but we'd like to start so let's say we're gonna be unstable b took a simple way to do this, I think. Yeah, I really like this, I mean, time I think actually, is a little differently than I do. But I'm so sorry, me. So that's probably sort of for us. Let's see, there's no method sorry. Call the method there we go. Okay, so now we have this mixed list of events but it's also sorted. So we're getting pretty close commented the print statements and all we have to do now I think is to say like, let's needs rooms equals starting zero and then like for the in events the start time actually plus and minus equals one. And at the end, we want to know the maximum of memory so write it like this. And enter the into this and then a B that wants to max rep or just like or number. Okay, so that's what I expected. Want to see here. Is it the braces that have too many? What's the second line here? Oh, it's a comma. Okay, so the code ran, but we didn't print anything. So might as well actually show what the answer is and should be two and this two. Yes, I think might literally just be done here. I want to check the edge cases though. I haven't thought deeply about open and closed intervals. But before we get to that you have any questions about the code we have so far because a lot of it is using this like it iterators in sort of rust specific syntax, so yeah.
Rocket Samurai: Yeah, I can make some. Yeah, looks. I mean, using a map, and then you have mapping on it. And then whenever you have a start even do an incrementing it and decrementing it and then and then you're trying to find max across all of all of these matches, I get the idea.
Professor Squirrel: Yeah, exactly. So like, it's like this anonymous function, which takes an event. The last expression is the return value of the notice function. So for each event, we return the current number of rooms. And then of all those, we want the maximum. Exactly.
Rocket Samurai: Okay. Good. Yeah. So what I like that extent, considering you don't necessarily have to write them.
Professor Squirrel: Yeah, I guess importantly, you should do like an empty list, which I think we've handled because we have this like default value for the maximum which handles empty lists. And there's, you wanted to ones where the input is sorted isn't sorted? Like a big input for performance? If you're, if you're trying to kind of manually verify that it takes linear time, for example, or n log n time? Yeah, like lots of disjoint intervals, lots of really heavily stacked intervals. And, yeah, I think that would be pretty good.
Rocket Samurai: Sounds good. So let's move on to a different problem. For this one let me copy the question. On line number one. Inside line number three, so you're given this input on line number seven, which is given a grid, right on the grid, you each point, the first two elevation, like the height at that point, right. So if you look at 0 0 is at height, 1 01 is the height one, and so on. So each of the locations is the height. And what we want to do is we want to find out, you're also given this grid and two inputs, right, so the two inputs are two locations on this grid. So in this case, three, one and three, three, which refers to this four, and this two here. So those are two villages. And we want to find a location within this grid, where we can place a water tank, which flows with supplies water to both these villages. And the rule for water supply is that water can only flow from high to low or equal to equal. Okay.
Professor Squirrel: Okay, so let me set it that just this example. So there's sort of like this mountain top seven, where it turns out, we'll probably want the water tower to go in this, this allows water to flow left to six, right to four and down into this valley, but it's kind of lost in the valley because it can't make its way back up. Or it kind of flows down this left branch to four and flows homes. Right, finished two, I'm sorry. And it reaches both of them. And then we win. And if that were not possible, we're going to find that out too, I think. Is it? Can we assume there always is a successful like points, or is there some inputs? Is it allowed that the input has no valid output?
Rocket Samurai: Yeah, you can have a grid in which you might be able to find an answer. So that is totally fine. And if there are multiple answers, you want to return the one with the highest height.
Professor Squirrel: Okay. Okay. Great. Great. Great. Okay. So, see here, so our answer? Break ties by weights. Okay, interesting. So I guess conceptually, what we have is a grid graph. And I guess it's like a directed graph where a point would have an outgoing edge to each of its four neighbors. Actually, wait a second. So how many? One question is can water flow diagonally are only in the four cardinal directions?
Rocket Samurai: Yeah, only one direction.
Professor Squirrel: Okay, great. Yeah. So a point would have an edge to each one. For neighbors where that neighbor is no taller than the current points. So that's sort of, that's the implicit graph structure in the in the input map. And then with that, the the goal here, I guess, is that we have two target destinations. And we want to find a source that has a path to both targets. So I mean, you could do this by running a traversal, starting at every single point. And then if you find one, points, like one starting point that reaches both endpoints, then you win. But then you're like, doing a linear number of searches, each one is taking a linear number of times, you're doing something quadratic in the input size, which is probably less than ideal. So I have a vague sense that maybe you'd want to do the searches in reverse. Like, if I take the, the the mirror graph, I forget what the word for this is. But if I take the opposite orientation of every edge, then I want to do like a mountain climbing traversal, where I start one traversal from village one, and I see everywhere village, one can reach if the definition of outgoing edges is ascending. And then I do the same privilege to and then I'll have two sets of basically candidates positions for a water tower. And I want to take the intersection of those two sets to get a point, you know, one or more points that are valid candidates for both approaches. Now give us a linear time algorithm. This is only two approaches, and each traversal is linear. So I think that's what I want to go with here. There's a lot of details actually write the code, but because concept is pretty clear in my mind.
Rocket Samurai: Yeah, sounds good. And what do you mean by linear?
Professor Squirrel: Yeah, so linear here is linear in the input size, which is n by n. So O of n by n is what I mean by linear. Thanks for asking.
Rocket Samurai: Okay. Yeah, you can start coding.
Professor Squirrel: Great. Great. Sounds good. One question are m n n both nonzero and assume? Yeah. And, and the points have given us the positions of the villages are both like invalid indices, they're in range. That's great. Great. Okay, cool. So that all sounds good. Okay, so... Okay, so maybe I'll have a datatype for like the map here structure map, or the grid is like, this list of list of are the heights ever negative?
Rocket Samurai: No, yeah.
Professor Squirrel: Okay, great. So how do I say this our tower, location water tower, and so on. So take the the graph sort of thing and then it'll take two points. Okay, so... So building one say, estimation 1.2 points where I'll make that be just like this for now at least look like that. And then the goal here is to return a point where I can put the water tower but it's really good still returning none which is like a nullable. Okay, okay. The idea here was first solves one and the intersection. Okay, so start race so I'll do like a depth first search or something from from this function. How would that look I would say let queue equals a new list with starting points in it then while inserts are no... Yes. So So basically everything that I can reach when I reach something I just want to check the neighbors so like for neighbor and something connect this neighbor me more and so, okay so you have to figure out a way to generate all are ascending neighbors so function like this we could then like filter that's reasonable let's yeah okay. This function would be what would it be like? Oh yeah okay so minus 10100 minus 101 is like the directions and for each of those this is like the for each of those like gonna make these use size signs we can worry about underflow so we're gonna let i equals zero plus DI okay equals one plus DJ and then like if range day this should be like a platinum filter these guys and all in connection range which is just the cool thing points just like the zeros i and j okay let's pack so i rows is calling and I think that's the basic neighbors function they do like return all also yes returns before neighbors and then an edge cases like the boundaries of the graph. It's it returns fewer. So like if I was in the top left corner, this would return only two neighbors. So that good. The next thing I want to do is be able to filter over which of the neighbors are actually ascending. So a function that comes out of this always gets he sort of as a comment and then I wanted to say so please, okay, I know that is cool. Okay. So then I kind of want like so, neighbors have a p but then my filter on. P two should have stopped I'd get a few one like either greater or less than two so I want to climb down below to find things that are taller than me so I can do this that's what I want there. So finally all neighbors of P which are points P two cents apiece usually least as large and some mountain climbing and and that should be what I want and then I just need to call it twice and take two intersections and then return so one is new intersect these two guys so like I think literally section two is an iterator and I want the max so max by key so not unwrap because the so this is correctly be empty if it's empty well, Max Yeah, yeah, I think this is actually just what I want. So I mean, that might be it. Modulus and compiler service so yeah, why don't we just sort of compile and see if this works and obviously doesn't see here done all the way to the top. So hash set is imported. Like this main function now no compatibility, I call it something else I call it cur. Yeah, in range ticks. Sure. Where am I doing? This I could say and what else? So line 23-27 says oh yeah, so this is for that and pointer copy. Back kind of in the it's true. So easy to pass such and the comparisons here will actually be the same where it's. Okay for that okay, semicolon summer and notice like oh yes your neighbors this is true. Okay, think about this so technically it's fine well do this should work off okay, we'll need to take ownership of some things just move the point network regardless no method named intersection there is a method of the similar name to just misspell it in in stir. Okay. In protection looks like he or she did that twice is really twice. Okay, lastly, I get a point I wanted a huh? I'm getting the I see copy well, so the code compiles to start all comments at the other sessions and send. Okay, great. So let's try to run this code. Input is... That's a great point okay, so wants to say like a map and then sort of like yeah, let's try running this. So we got one two, which I guess was what we wanted. Cool. Okay, so yeah, it seems to just work.
Rocket Samurai: Awesome. So yeah, like. So once you're done with this, can you explain what this is? And then we can move on to one more problem?
Professor Squirrel: Yeah. Sorry. So you said the runtime?
Rocket Samurai: Not, not the runtime, but just like what additional test cases?
Professor Squirrel: Oh, yeah. Tests. Great, great idea. So the smallest edge cases like, one single point? I guess I didn't clarify this in the question. I'm assuming I'm allowed to place a water tower in a village? And if that's okay, cool.
Rocket Samurai: That's a good question. Yeah, let's say like, we want to find a water tower, which is outside those two villages.
Professor Squirrel: Ah, interesting. So then that's, we can do it too. So we just have to make sure to kind of filter the list here.
Rocket Samurai: So don't worry about changing anything. Yeah, that's the discussion. You don't have to change.
Professor Squirrel: So what we want to do is just make sure that we're never returning either village themselves. So we would do the same calculation of things we can reach. But then from the intersection, we exclude both P one and P two, or desk one and S two. So just filter by naught equals point 190 1.2. And then that would make sure we, we never choose those two points, and we choose anything but it and potentially this makes an empty iterator, which we then returned nothing, and otherwise will still return the right thing. Breaking Max. Does that make sense?
Rocket Samurai: Yeah, no.
Professor Squirrel: One's he won. He could get so that'd be that. And then yeah, test cases. I guess. Like I was saying, like a grid of size one. With this interpretation, there's no solution. So that's one test case, a grid size like or would be maybe the smallest. Where there is a solutions, you test a couple of grids assess for maybe test like a column grid, where there's like one dimensional you know, inputs and where both the case where there is a solution where there isn't and then similar for a single row input. And then so those are all the kind of smallest edge cases and then other than that, just testing medium sized inputs, tests, some graphs that are like, you know, kind of maze like like, not super trivial to, to traverse and then test like one big input for performance and like that.
Rocket Samurai: Okay. Good. So, for the last question. For this one, we may not have enough time to write code. So on line number one, let's say you given an array and a window size, so you have a 123456 and you have a window, window size, let's say three. And then we want an output, which is going to be the max of each window from left to right. So the first window is 123. Max that is three. Second window is 234. Max of that is work. And then four this question.
Professor Squirrel: Great, that sounds good. So is the window size a parameter or is always three?
Rocket Samurai: Yeah, it's all input. It can be dynamic.
Professor Squirrel: Great, great. Yeah. So it's not become something like endeavor to then it starts to matter what data structure that we maintain the window. And so naively, we could do this with how do I say, just doing a linear scan through the window to find the max. But that'll take us n squared time. Tonight, thanks. So let's see. So instead of doing that, I'm guessing we want to do something sort of online sort of sliding window we are left to right, where we maintain a data structure like probably a priority queue, which we inserts. Nothing, not a priority queue. You think about that, actually. Maybe, maybe an ordered map like a binary search tree or B tree. So we want a collection of the numbers we've seen so far. And we want to be able to insert one number, when like, we kind of update the window to extend it by one and also remove one number. When we're shrinking it by one like or so that we're fighting it over by one and keeping the size the same. So it's obviously data structure that allows an insertion and deletion by the key, which is the number. But then beyond that, we also want to know the maximum efficiently. So so he's actually not a good choice for this because I think insertions and deletions aren't aren't trivial. I mean, it's possible, actually. But most heaps, you can't delete from the middle of the elite access to the top. But that's an implementation choice. But so so let's say not a heap, but instead, like an ordered map, which and rest of the tree map are between stack, let's say, so this, this is like a hash set, it's beginning. Well, let's see, I guess not a set, maybe we'll get a map from like, value to like the frequency of that value, or something, or like a gizzard sign or not, but so there's like a frequency is kind of a sliding window. Which is like this. And then so that way, I can maintain the sort of state of the window and I can update it in log time, each iteration of the loop to compute each output and W updates. And the computation of the maximum is also log w, then I'd get an algorithm that's like n, n minus w iterations, but like, say something like n in the worst case, and then minus W. I already like this. I'm not sure if this is over complicated, but MSW, and then a log w, this is like, what you would end up with, with this approach the zipper, it's pretty clear, that would work?
Rocket Samurai: So few questions on the frequency map? Can you talk more about it? Like? Is it maintaining the counts of each value?
Professor Squirrel: Yeah, exactly. So if we had, like 12314, and the window size was like, four, first window is one, two coffees and 301. Copy. And then as we update the window, this will go to get another copy of one, this becomes like, become, too, and we actually know we lose a copy of the same. But then the final window would look like we would lose a copy of two and we get a copy of for the last does that make sense?
Rocket Samurai: So you shift the window and then you update the frequency. And then based on the the also the dues reduce or increase the frequency, so and then you find the max. Because it's a binary tree, you'll be able to find the max. How do you find the Max like, you look at node.
Professor Squirrel: This is a binary. Yeah, it's a lot like a binary search tree, like the B tree ideas is, is just sort of an optimization of the concept of The binary search tree the, the main idea is the same. So essentially I you just, I mean, you just call the helper function that does it, it's because it's in the standard library. But the what that would be doing is it would be traversing like the the right spine of the tree. And then basically, you go, you go to the right until you can't anymore, and then you stop there. And it doesn't have to be a leaf, but it will be the largest key in the tree. Does that make sense?
Rocket Samurai: So yeah, and that would be, what would be the maximum that so if you want to find the right person road? Yeah.
Professor Squirrel: Yeah, yeah. So is a self balancing tree is probably like a red black tree or AVL tree. A maximum depth is logarithmic in the size of the tree, which is why log W.
Rocket Samurai: Just make sure. Yeah, I've never been anybody give me this solution. So I'm just thinking. Okay. And then find the one the highest value. So are these the frequency? So are these indexed by like the value or indexed by the frequency?
Professor Squirrel: Yeah, so keys are values. Values are frequencies.
Rocket Samurai: But when you do your, when you do your, when you try to find the max, right, so will they be searching for the maximum? I'm assuming that the maximum key the highest key, exactly the...?
Professor Squirrel: Max key, but I guess it's important to mention that deletions from the tree, you have to check like after decrementing, you have to say, is it now zero? And if so remove the key because you would not want something like this? Because that would mess up the algorithm. So just make sure that all the values are nonzero.
Rocket Samurai: Makes sense. Yeah, so this sounds good. But sometimes, like some interviews can ask you to use like a data structure which you can write from scratch. So this one, you have to sort of rely on the library. So it's good to think about, can you use something else to write the code for this? So that you can think about it later? Or you can look into solution? And there are like two approaches. One of them is linear time, and one of them is invoke W.
Professor Squirrel: Okay, interesting. Yeah, I have to think about that.
Rocket Samurai: If you want you can think about it. You have like two minutes?
Professor Squirrel: Sure. Sure. Sounds good. linear time is interesting is kind of surprising, almost. Because, oh, maybe if you had linear extra space, you can do something clever. Where are you? Like keep a stack or something? I don't know. Like. I'm not entirely sure. But there's probably something quite clever.
Rocket Samurai: I can give you one hint, which is that you want to maintain a data structure which stores all your max candidates at that point. So when you iterate over these numbers, wherever your i is selected on line one, if you look at if you ingest one, then you update your max candidates, one, if you look at and then you look at two, and then you see whether you need to do do something with this max candidates, like do you need to update the list? Or do you need to keep adding to it?
Professor Squirrel: Right. Okay, let me think about that. So the thing is finished a little tricky is like you had like, three to one. And then like, but the the initial window is it has three things in it. But you'll have to somehow know to to reduce the max once you shift the window to like, the second iterations. So tricky.
Rocket Samurai: One insight here is so let's say like if you have an input, like key to one, and then three to one, so let's say like you look at three, right, so three goes into your max candidate. Data. Three is there and then you look at two. So you decide whether you want to keep two or whether you don't really need to keep two so because two is smaller than three, so do you. Do you think you'll need to preserve two in this max candidate list? You think it doesn't matter?
Professor Squirrel: I think I might, because like, these are all was the two is relevant during this window like this should have to.
Rocket Samurai: Exactly. So because yeah, because two can do can be an act in the future I did one three slides out to can be an X in the future. But let's say like this number was now nine, right? So now you have ingested two and you're looking at nine. And so far your Mac candidates has three and two. So nine is coming in, what do you think about nine? What do you need to do?
Professor Squirrel: Well, I guess, nine is like better in every dimension, because it's both bigger. And it's farther along in the list. So I'll have it I'll have access to it for like longer time. So they're the whole list. So are they less like packed with their index? So three, zero to one. And then when I see nine, and I know that it's bigger, sort of like a nine is recognized. To and then. So I'll compare until I find that then. Interesting. So I'm clearing the stack. And then if I find things, I see I see. So okay, I think I have a general idea that like, and then later, you'll see you'll put a stack in this case. And later when you see like, one three, you know that one doesn't dominate nine, two, you won't clear nine in the stack, but you will push one to the stack, I think.
Rocket Samurai: Yeah, because one can connect in the future. Like because one comes up.
Professor Squirrel: Yeah, exactly. Exactly. Is this actually more like a cue is sort of a stack because you're kind of popping to the left as well, when you're like invalidating. Like the, the time that thing has left to live. So yeah, I'm guessing it's like you like a circular buffer thing. And, and you're like, both sounds kind of tricky. Hard, hard to read the code, maybe. But you're popping from the left, when things expire. And then also you're clearing the queue when you find something that kind of strictly dominates the contents of the queue, or like you're clearing as much of it as you need to. And then I guess, something like that. Yeah. Wow. Yeah.
Rocket Samurai: Yeah, let's talk. And definitely look into like mono cue and mono stack button. Okay, cool. Just kind of like, semantics of like adding things to the queue, clearing them. And then your max is always going to be available max or min is always going to be available on your left or the right. Yeah, so that button is no queue and monster. Okay. So I think like, today, like overall, like, it was great. You asked a lot of good questions. You wrote really, really nice code, function names, model new code, I think it was similar to last time. Except that maybe like the debugging was faster this time, right? Yeah, just be. Whenever you're going to like actual interviews, just be aware of like what last version, you'll be running in, like code accordingly. Right, so that you don't have debugging. And then we talked about time and space that is good on your own. And one minor feedback would be just like, whenever you're done coding, try to talk about like walk through, take an example. Do a walkthrough with it, and then talk about additional cases. Yeah, that'd be just being proactive after you write the code. Yeah. Great. I think yeah, that is it from my side. Like you solved all the questions, good intuition and all of them.
Professor Squirrel: Yeah, awesome. Thanks. Thanks so much for the practices and super helpful.
Rocket Samurai: Awesome. So yeah, have a good day and all the best. You too. Bye

Netflix Interviewer

Binary array partition

Heuristic Panda, a Netflix engineer, interviewed Orange Storm in Python

Watch interview

Slack Interviewer

Transformation dictionary

Spasmodic Pizza, a Slack engineer, interviewed Winter Griffin in Python

Watch interview

LinkedIn Interviewer

Reverse word in string

Space Dragon, a LinkedIn engineer, interviewed Ice Gyro in Java

Watch interview

Airbnb Interviewer

Missing item list difference

The Legendary Artichoke, an Airbnb engineer, interviewed Supreme Werewolf in C++

Watch interview

Ready to practice with a mock interview?

Book mock interviews with engineers from Google, Facebook, Amazon, or other top companies. Get detailed feedback on exactly what you need to work on. Everything is fully anonymous.