Seat Allocation at Scale: Coding Interview with a Google Engineer (Python)

I really like how you were able to tweak your approach as you better understood the problem. I noticed you had some struggles with the left equal to middle equal to right Boolean expressions, but you also got out of it. Maybe after some nudges and your own thinking. you are able to like figure out your way through it. Hey everyone.

Welcome back to another episode of Whiteball Confidential. I'm Adam from Interviewing IO and today's mock is deceptively tricky. The problem is allocating seats in a movie theater at massive scale. Now the candidate has about a year and a half experience at a series B startup and this was their

very first system design interview. The session was led by a staff engineer with experience at Google and other top companies. What stands out here is how the candidate lays out functional and non-functional requirements, works through edge cases and space optimizations, and refines early ideas until they arrive.

scalable solution. They also consider how the system would function under heavy load and what kind of logging would be required to make it reliable in production. Alright, let's dive in. Topter engineer for almost like six years so far. I spent some time working for Google and other like companies out here in the Bay Area. I'm your mock interviewer for today. So I just want to like.

kind of give a bit of an intro. And yeah, can you tell me a bit more about yourself? Yep, sure. So I am a software engineer. I have been working for... a year and a half, almost two years, fresh out of college. And I'm working at a Series B startup, but I have a Google interview lined up for like the onsite. So I'm just prepping for that particular.

Yeah. Okay. All right. I'm definitely wishing you best of luck. I've done on-site for Google. They are rigorous, but they are also passable. Yep. Okay. Sure. And yeah, just to get some background. So you mentioned that you have one and a half to two years. So I take that you're targeting for like an L3 or L4 type of position at Google. Is that correct? Yep, that's correct. I'm targeting for an L3.

Okay, just clarifying. And yeah, what programming language are you most comfortable in? I'm most comfortable in Python, so I would go with Python. I think I can pick Python 3 from this list. Perfect. Yeah, please pick the language that you're most comfortable in doing your development in. I am familiar with Typhon Free. And yeah, so just some heads up. Like, if you want to grab some water or if you need to, like, take a break, feel free to do so.

Yep. And also, if you want to use pen and paper to help like crystallize your file process, feel free to let me know. So don't feel like you're constrained. If you want to like... toggle the whiteboard or set the environment to your advantage, you're welcome to do so. Yep, for sure. And I'll try to follow along with you. So don't just feel like you have to be writing fit or if you even want to like dive into pseudocode, you take it how you want to evolve it.

All right. Yep. Love it. I think I'm ready. I see a toggle whiteboard here as well. So if I need to draw something to you, there'll be that. Yeah. I just want to ask, you're familiar with the environment and all the setups, right? Yep.

Okay, all right. Sounds good to me. Okay, so I'll be taking a problem from Leaco.com. And let me know if you have or have not seen this problem. So you can go to... Yes, I have not seen this problem, actually. Okay, perfect. It is from LeakCode. It's called Genema C Allocation. I'm going to copy-paste the word problem description. Yeah, I'll let you take your time to read through the problem and make sure that you understand it. Yep, thank you. I'll take some moments.

So, yeah, given I'm also going to read out loud just to be clear where I'm at. So I have reserved seats containing the number of seats already reserved. For example, if it's like three and eight. Reserved seats at I is at 3 and 8 means that the seat located in row 3 and labeled with 8 is already reserved. So I guess if I were to imagine it like a 2D array, then at row 3 and column 8, that's reserved.

um cool so return the maximum number of four person groups you can assign on the cinema seats so a four-person group occupies for adjacent seats in a single one single row so seats across like three three or and three four are not considered to be adjacent but There is an exceptional case on which an aisle, it split a four-person group. In that case, the aisle split a four-person group in the middle means to have two people on each side. Okay, cool.

So what I'm counting is the maximum number of four-person groups I can assign. So in the example on LeetCode, I can assign that. there are three rows and then on the first row there's four in the middle and then on um on the second row there's also four um And then on the third one, there's also four. So I guess like on the second one, the reason that I cannot pick seven to ten is because it's not split.

in a two and two way it's split in a one and three way so then that is not valid and i have to go with the two and two option um similarly that's why i cannot take from one to four and okay and then for the last one Yep. Oh, because I'm trying to go for the maximum. I also cannot go from four to seven. I have to go from two to five and then from six to nine. Okay. I can see it. All right. Yep.

So I'm trying to come up with a brute force approach. And so what I'm thinking is, so N here is denoting the number of... So I know for a fact that my array, let's say, will be n times 10, right? Whatever n is, I would have 10 slots per a seat. So let's say this is my first. Sorry, I think maybe I'll just number it. One, two, three, and then dot, dot, dot, go to 10. Same for here, dot, dot, dot, go to 10. So, yeah, and then there will be more of this. So I can represent this as a matrix.

And then for the reserved seats, for each of the seats in here, I can mark it on this matrix somehow as taken. So let's say if I just have a bunch of slots like this. I can mark it accordingly on my matrix and then let's say if I were to mark it now I could go through row to figure out how many like what is the maximum number of uh of four of a four person group i can assign here and then

For each of the row, I just do that and then add it to some kind of answer sum variable. And then in the end, I just try to return this answer. So let me think about the logic to try to pick from a single row. So pick from a single row. So I know that the row is not as simple as like... adjacent slots because the first three are divided from the next four and then it's divided by the last three. So let's say if

So let's say if, like, I need to see the available slots, but basically from 0 to 2, it's a different area. And then from 3 to... six is a different area and then the remaining you know like from seven to nine is also a different area so I think for example let me take an example of the first row here I was given one and four. Sorry, so I think actually one and two, one and three. Is it okay if I take the example from lead code?

Yes, it's okay to leverage the examples from LeakCode. I want you to use those examples since you have graphical understandings and because the minimal example. Okay, awesome. Yeah, so I think I'll just take the first example. It seems simple enough. And then, so I know that this slot is taken. Let me just put a dot in here, like an X. And then I also know that... one three is taken so it's equivalent to this and then the last one uh sorry this one is taken so then i when i look at this i think

I think one of the things that I could do is I could... Basically, there are actually only... I think there are only like three maximum for a row. There are only three possible slots.

that someone could have right so like even if everything is empty on this row right if let's say if this row is not taken at all i think the maximum number of four people group maximum number of four people group is going to be three and correct me if I'm wrong here but it's because first of all the one in the middle will be what we focus on so that will be one group and then

The second one is from basically from index one to index four. So that's another potential group. And then the third one is like from index, like from basically like the last.

the last two of the middle and then the first two of the last section so yeah so maybe I can restrict what I'm checking here since I know that there are only 10 seats in a row so maybe I can just do something like I make a I have a loop and then I go through the four slots here and then I go through the four slots here at any point if it's

at any point so basically it's like a loop of three iterations so like a loop of three iterations and at any point if it's if any of these is like uh picked already then i just I just moved on to the next iteration. So I would start the iteration at index two and then at index three because it's the beginning of this four seed.

like group and then index um so sorry one two three zero one two three four five six seven and then index seven so i think it's going to be two three and seven I'm going to start checking, and then, yeah, in the case where these three are available, then the maximum that I could have for a row is three, and I would just add it to my answer variable in here.

If that's okay. So I think that's a brute force approach that I could come up with for this. Regarding like. the space complexity of course because i'm trying to recreate this whole theater seating it will be uh basically like n times 10 whatever the n is and uh yeah and then i have to loop through like this but it's uh it's still less than n times 10 and for the time complexity i'm going through each row so

And then for each row, I'm having three iterations. So that would be like an O of N time complexity. Yeah. Yeah, I agree. I like where you're starting with the brute force idea. And I think you're definitely on the right track. I think you're like.

on a right track uh one one thing that i'd like to see us is if we can like take a bit of time to try to optimize for either time or space complexity and see if we can get away from having to do an O of N space complexity approach where N is the number of like sort of aisles that's it's the number of rooms so if you notice like on line 25 N can blow up to 10 to the power of 9. So can we like other variables or other constraints to cut down on the space? So it may either be like.

You may either, say, take space from O of N to a better, bigger complexity, or maybe you could cut down space and time by some constant factor or leverage a different variable. So let's say...

N versus N. So let's try to think about that aspect. Yes. So I realized that definitely I don't need to recreate this visually because I can just make a for loop through N and then like... i know that basically like i have a 4i in range something and then for j in range something and then at this index like all like at this coordinate i and j i could check if it's taken by checking against the reserve seats array um

And maybe to optimize checking against the reserved seat array, I can also turn this into a set of coordinates for fast access. So that would be a way to optimize what I already have in terms of space complexity. In terms of time complexity, I'm trying to think if... There's a way for me to make this faster than a loop. Right now, I'm more leaning towards just laying out the...

like basically having the structure in a for loop without having any extra variable to store space. And then when I have to coordinate, check against this reserved seats. And then I can continue with my... loop of three iterations that i mentioned here um but yeah like if this is the number of uh this is the number of rows then i would still at the maximum like check for it 10 to the nine times so

I'm also trying to find out if there is some way of doing this with a better time complexity. I think one thing that I could say is... Could you imagine a case where your cinema, like your movie is really unpopular and maybe only like one or two people are actually sitting in a really big cinema? So what would you? How would that kind of help you? Like a case where you don't have that many movie watchers? Oh, oh, oh, oh, I see, I see. Okay, so it's kind of like a sparse array thing.

Yeah, so maybe I should focus on reserved seats here because the length of reserved seats is obviously way smaller than the length of the number of rows. Maybe how about what if I start with reserve seats? Like maybe I could sort it first or something by the number, like by the row. So and then by the. by the column so that like let's say if I were to have 4, 3 here and then maybe I can have like 4, 6 next and I mean of course like 1, 4 and 1, 7 will go first.

So let's say if I were to focus on this reserve seats and sort it. Now I know that I only have to focus on two rows, which is row number one and then row number four. I don't have to care about the rest. I could assume that it has. maximum it can give me the maximum group which is three um so yeah in this case i think i can i only have to check for two rows instead of uh wait there

Sorry, I was wrong. This was the four. So in this case, maybe I only have to check for two rows instead of all four of them. So yeah, maybe I should focus on the reserved seats here and try to go from there. And the sorting, it's... it's going to take more time complexity but I was just thinking that it would be way easier to check if something is on the same row according to the loop of three iteration that I have. So that's why.

okay but yeah like just i think it yeah it's better to check the reserve seats but um yeah so i think that would be my rough approach i I'm also trying to think if I can optimize it in any other way. But yeah, most likely, actually, I think I don't even have to sort. reserved seats to be honest i can just loop through this array and then i grab the rows that i need to check and then i think that'll be it like grab the rows that i need to check

the number of seats available. And then for the rest, then I just add three because I know that they're all empty. And maybe I can turn this reserve seats into a set for faster access. So in that case, I think it would just be all of... with N being the length of reserved seats or something. That sounds like a good idea. Yeah, I think it could work. Let me know if I should go over some pseudocode or maybe I should start coding stuff like that.

I think you should go with what you're most comfortable in. So if you feel more comfortable in pseudocode, go with pseudocode. If you want to get started, dive into code, dive into code. Okay.

Sure. Thank you. I think I'll just dive into the code and maybe I could do dry run and go over it after. So I am going to make a function called like reserve seats and that takes in an array of. Oh, sorry. I'm just going to call it cease. And then I know that this is a 2D array. So let me just make... an array of what to start with. So I'm going to loop through seeds. I'm going to say like for row and column in seeds. I know that actually I think my array could be a set.

I don't, I don't think it matters that it has to be a, it like, I don't think it matters that it has to be an array. So I'm just going to say like for the row here, then. I would just add the row into my set. Actually, I should call it F, not to be confused. And then for the columns, I think I do not care about it at this point. So then I have my like start or like rows to check something like this. Rows to check. And then for.

the seats here, I'm just going to have like seats set. And then I think I can do a set operation around the array seats. So this would be it. And then I would loop through my set of rows to check. So I'm going to say, and actually within each of those, I only care about three things. I'm going to say for a row in rows to check. So for each of these rows, I have an iteration of three. So I'm just going to say for column in range.

I start, so basically, or like four columns in, and maybe I will start with an array. So it will be zero, oh no, sorry, not zero, so. Let me look at the index again. I'm going to start at index one. So that'll be one. And then the second one I'm going with is three. One. three, and five. Yeah. Oh, no, sorry, not five. One, three, and I think is six. Wait, no.

Actually, I'm right. It's fine. I'm just bad at counting. All right. Cool. So then now I have the row and the columns. I'm going to make sure that for the next, so like now I have row and column. And I'm going to make sure that for the next four slots, it doesn't get taken by checking it against the seed set that I have here. So I'm going to say for I... in range 4. And then I'm going to have the row and then I'm going to have the column plus i. So then if at any time this

This array... Actually, it's not an array. Hold on. I think I have to make it like this. Because it's divided by a comma in my original array. So I think I have to say if row and column plus I is in my fit set, then I have to basically break out of this most inner loop and then...

continue with the next set of columns. I think maybe there is some optimization I could do here, but I'm just going to think of it simply as freaking out of it. And actually, I think I need to... have a count within this so i'm going to say like okay if it's in here then i break out of my most recent loop which is this one and then actually i shouldn't break i think

Yeah, okay. I'm breaking out of this for loops. I think it's okay. Otherwise, if it's not in the set, if this is done, then I will have to... plus one to my account. I think breaking here will break out of this loop, so I think I'm good here. because in the end and then it will go on to the next thing but i'm not sure if i'm counting correctly it's all um but okay i'll go over it later so um yeah so that's the road to tech and then

I know the number of rows I have because it's given to me in the form of n. So let me choose. I forgot that n here. So that would be like n minus rows to check. And then this times 3 is my answer. So in the end, I'm basically return C plus... Actually, C cannot be here. So let me just put it outside. And then...

or like basically it's counting the number of flats in each row. So I think it would still work. And then in the end, basically I'm trying to find C plus three times N minus rows to check. Actually, is it three? Yes, I think it's three. So it will look something like this. I want to stop you for a second. I think that's a good question you just brought. Is it three?

Do you think we can take a look at the problem description and verify and check if we're following the requirements? Yeah. Yep, that's for sure. So... So I think you're on the right track, but I think we should look at the problem statement and look at what the ask is. Yeah, yeah. Okay, so... I'll actually remember.

Okay, so I think first of all, what I realized is that my reserve seats is one index. So I need to pay attention to that. So I just take reserve seats is one index instead of zero index. So definitely something you have to do. And the next thing is maximum of four person groups I can assign. Just a second. I need a refresh. I got this connected. Can you still hear me? Yep, I can still hear you. Okay, I just need to reconnect. Hello? Yes, can you hear me?

Yep, I can hear you. Okay, perfect. Yeah, it's a temporary, it's a transient failure. Let's get back to where you were talking. Yeah. Oh, OK. So I realized that I cannot check for the middle part here. If I'm if I if I basically if I decide to go with the first one, then technically, basically, if the if. If column 2 to 9 is free, then the maximum that I could go with is 2 and actually not 3. So there's a constraint here, basically, with the columns.

So I think, let me think about how to do it. So basically there's a constraint here with the problem because if section... One and three is free. The max boot return is two, not three. And the way that I'm counting right now, I'm actually counting. Three for it, which is wrong. So either I take the middle part or I take the two sides. Or two sides. So I cannot take three. It's not three for the case where all the seats are.

empty. So this should not be three to begin with. This should be two and and then yeah the way that I'm counting here is wrong. So I think I have noticed several things. And so I think I'll fix these problems. So first of all is my index. And second of all is that for a maximum, like we can only take a maximum of two.

for a row instead of C like what I said before. I'm going to look at this code again. Basically, I want to make sure that if it starts from zero uh from one and five then it has to be occupied otherwise like from three okay um let me think about this a little bit um all right so rows to check um Okay, so I think I can do two separate loops, kind of. It would still be the same thing, but it would just check them separately.

Well, I have to add a question. Like, do we need, like, there are two loops, but how many, like, cases are we checking in a sense? Like, how many configurations of four-person seatings are available? You sort of talked about a feeding of 2 to 5 and 6 to 9. What are the other configurations, if that exists? Oh, yeah. It has to be blank from 2 to 9. That's it.

yeah yeah if i want to it has to be blank from two to nine which would already include uh the four to seven being oh yeah which would already include the four to seven being blank So, all right. There's three configurations. There's like two to five, four to seven. And you mentioned that. Yes. Yep. So technically, oh, so I see now like.

So maybe I would just need to check basically a loop for whatever in range from 2 to 10, which is like not including, but it's basically from 2 to 9, essentially.

So if it's all blank, then I have two groups here, so I can add two to my account. Otherwise... like otherwise if they're not blank then I need to check if or like have some kind of let's say have had some kind of like variable let's say like basically my variable is is middle empty or something where i can basically also check uh if middle is empty and then let's say when i get out of this

Basically, if I didn't add to and then middle is empty, middle empty is true, then maybe I can just add it to my account as well. So essentially, I would have to check from... column two to nine but that will already give me the information on four to seven already so um yeah i think i could do something like this and then you know like

Maybe middle empty is set to false in the beginning, so it's easier for me to check. So in that case, I think I will just fix this code. Instead of this for loop, I'm saying like for... first column in range to... Actually, I have to fix my index first because everything starts from 1. So row to check would be 1 and then... Okay, for rows to check. I think I can still do this. So I would just say like 2 to 10, essentially. And then from 2 to 10, let's say I have like...

It's middle empty and I'm assuming that it's false to begin with. So now I'm checking...

I'm checking if the row and the column is in my reserved seats or not. So basically at any point if... Let me think about this. So like if this is in... the reservation then um row and column is in reservation then this row and column yeah then basically i cannot add to but i still have to check from so i guess i'll um i guess like i i'm maybe i'm thinking too much i just need to i check it in there i think you're on the right track but you're fixating too much on the single case electric

Your index is 2 to 9 here. I think to get you back on the right track, like, again, you mentioned there's three configurations of seedings with your index strategy. Like, there's seeds from a 2 to 5. They cheat from 6 to 9 and they cheat from 4 to 7, right? Yep. And with this 2 to 10 approach, you know like the 2 to 10 is a combination of 2 to 5 and 6 to 9, right?

Yep. If you didn't have the 2 to 10 available, but you still have to check... configurations into what if you have to check the configurations individually so say two to ten wasn't fully available because someone is sitting at eight or someone is sitting at three right like you could have those two type of cases So maybe if we think about checking groups individually, it could help you with checking the group, the scenario of the groups in total. So what if we can kind of like.

Could we kind of like decompose the problem into constituent cases? Yeah, I think maybe it's better for my thinking if I do that, because I was... kind of confused here so okay i think i then i would say like i would have three case um so then i would make three four loop in here just to have my three case to see like it's left empty it's middle empty and then it's right empty and then i can go from there so the first one is from two to five so i'm gonna say for coin range two to six um

And then the second one would be for column in range 4 to 8. And then the last one would be for column in range, instead of 4 to 8, that would be... 6 to 10. All right, 6, 10. So from this, I can determine if the group can be made. So basically like, so if my row and columns... is in my set then I know that I cannot do this so I have to break. Similarly if my row and column is

In reserve seats, then I have to break from here. And the last one as well. Then I have to break from here. But in the case, it actually managed to... finish i think how do i say how do i check for it so i think i'm gonna um let me think so let's say i'm assigning that Like left is true in the beginning. So maybe like left equals middle equals right equals to true. So if I have to break, then at least I'll just toggle it to false.

And then middle equals to false. And then right equals to false in this case. So then at the end, when I finish checking all of these, I can say that For this row, if left and right, then I know that for my count, I can add two confidently. Otherwise, else if middle. is available then i can just add one um but yeah i think maybe this will clean it up way much more so i still have like the count here um and i check for left middle and right so

By default, they are true, but if they cannot be made, then I switch to false, and I have an if statement here to count, and... Hello?

Um, hi. Can you still hear me? Hello? Yeah, sorry, I got cut again. Okay, you're talking? Yes. I don't know if you caught the last part, but I was basically like making... I'm basically making like... Boolean variables to check left and middle and right and default them to true. And then if they cannot be made, then I just switch to false.

And yeah, so if there's left and right, then I just add two to my count. Otherwise, if there's only middle, then I add middle to my count. And then in the end, I think I can just return basically the count. Or like I can add it to the count as well. Whatever the count already has. I add it with two times and times minus rows to check. And then I can return my count. So I think this was my...

solution. Yeah, I think that this is on the right track. But I want to ask if you think we're missing any educate scenarios, or if you could walk through the following structures. and see if there's somewhere where you may be adding account, where you may not be adding account. So I could tell you, but I want to see if you can catch it. Okay, cool. Yeah. Maximum of. All right.

For a JSON one in single row. Yeah, because I think like the code is mostly correct, but I feel like it could break some edge case scenario. So if you can think about like... An edge case that you might be forgetting, it's going to help you. Yeah. With like a single row or with like a single, in a single row configuration. I don't want to give you an, it's not an edge case where you have multiple rows, but think about.

Somewhere that you're not a scenario that you're not accounting for. Yep. So, I mean, I'm thinking of like an empty row. I'm just like. naming my ideas here not testing on it yet or like a full row um could be the second case or like um a row where I could roll with 2 to 9 field up. 2 to 9 field up. That would not be an edge case yet. So let me think about another edge case. Two to five. Or maybe if it's alternating.

I don't know if I've checked for it yet. I think it will still work in the case that the seats are alternating. Let me think. Four person group in the middle, so two people on each side. I'm not checking for that middle at the standalone case, right? Like Ellis middle, right? Yeah. Can you walk me through why you're checking the Ellis middle at the standalone case?

If not the left and right? Yep. So I'm checking it as a standalone case because in the case where it's an empty row, then you go like... I'm not going to, I don't think I can draw it here, but we're going to have 10 slots. And then I know that... Basically, even when the whole row is empty, the maximum that I can put people in, like the maximum number of four person groups is only two instead of three. So that's why, and I know like two is a bigger number than one.

which is why I checked for the left and the right first because if there is left and right, then I don't even care if middle is available because it already implies that middle is available and that's the maximum group that we can have. If there is left and right, then I just add two, which is the maximum number of four-person groups to this answer. And like otherwise, if... Because if, let's say, if left is...

Actually, I don't know if left is... Yeah, or like if left is occupied on the first two slots and right is occupied on the... on like those two slots as well then maybe middle is still available if it's not set to false here um so yeah i i know that i'm probably like i do have some overlapping party this i'm trying to give

help nudge you without giving it away maybe a good example is what would what's a weird case where you can test a single person sitting in a row where your code doesn't do its counting correctly single person sitting oh oh oh maybe like you plop a person somewhere and you're like oh i'm not accounting for that correctly it's just a single person oh and you have 10 seats right Yeah, maybe somewhere in the middle. I think... I know. If it doesn't check correctly...

So maybe, I don't know if... Well, because first of all... You said something right, which is somewhere in the middle. So let's use that. Okay, so let me try to draw it out. You can use pen and paper or you can use the notepad. I don't mind. Whichever helps. Yeah. Let's think about somewhere in the middle of a single person.

Okay, I see. So I'll draw it like this. So let's say like, I think in the middle that could overlap with this. Oh, oh, wait a minute, maybe here. So I think... I can see why it's breaking because obviously my left is not going to be present and also my middle will not be present but my right is still fully functional. So then in this case, it should return 1 instead of 0, the way that I'm doing it here. So I think I have to change my if statement here.

So I would say, all right, if left and right, then I add two. Else if, yeah, like else if there is the middle or... How do you think about it? Because, yeah, if I take the middle, then, okay, I assume that the middle is not broken, but then there's also a case where there's just left or right. Then in this case, I'm going to add one, but I think this might still be wrong because Actually, maybe not so like left and right in this case it will take These two areas so

This is for sure will be here. So if I go in this middle case, it means that it's only left or right. And in that case, maybe I can just do maybe in this case i can just do an else and then but it's not certain that i could add one to it um um let me think so If it's not left and right, it might not be left and right either. Like, okay, let me think about it. So maybe if it's left or right, then I would still need to add one here. And then...

Actually, so if middle, I would also need to add one here. So maybe in this case, I need to check instead of checking for... This is kind of wrong. to check but i think i can do this and um and i need to you consider like nothing a way to help you Sorry? Are you familiar with the term nested conditionals or nested expressions? Yes. Do you think that could help?

Yeah, I think that could definitely help. I could do an L if here and then an L if here, I think. Yeah, so I'm thinking that, let's say, like, if... If three of them are true, then I don't care about the case where middle is true. I only care about left and right. So it would still work. And in this case that I'm trying to present here, left would not be... Basically, left and middle are dead, but then because I say left or right, right should still be available. So then I could add one.

Other than that, I think maybe there is, because like, let's say if I were to put it here, so now I know my... My left is dead, but then my middle and my right is alive. But in this case, I would only return one instead of two, right? Because... Sorry, hello? Yeah, I'm still here. Sorry, I think I accidentally toggled the whiteboard. So in this case, I think...

If I have this case, the area that I'm highlighting, I think we only want to add one in here instead of two because we have four people and we either pick the four middle seats or we pick... the one to the right so in this case it's still just going to be one because we're not counting the number of ways i can assign so i think i think this if else statements will work um yeah

Okay, I think it's almost there, but I think that's the case where, like, that edge case that you have highlighted, well, it's an... I feel like what if else if like, if the if fails, the else if evolves, but I'm not sure if it, I feel like in a lot of programming languages, like two else ifs can evaluate consecutively. Oh. Is that correct? I'm not always sure, but I feel a bit worried about that. It's okay. Maybe in Python, if one of those else evaluates, it breaks out.

I don't always know. But I feel like you're on the right track and I don't want to get too bogged down here. So what I want you to do instead is to walk me through a test case example. So if you could take, if you could walk me through one of the examples, like. one or two examples from above or create your own examples and show me how you'd be going for the code uh yep i think i could do that so

I think maybe I'm going to use this example that I have down here. Yeah, and regarding the ELIF, maybe I could opt to return early. That could also be an option since I only want to pick one from here. I mean, I think the elif in Python is not going to be run, like, if it picks one, it will not run into another. I think it will work. I'm going to pick this case where I only have one reserved plot.

So it would be at, so this is one. So I think I only have one row. So let's say like my n is equal to one. And then the reserve seats is one, three. So this is going to be what I have for my case. And for this case, I'm expecting the answer to just be one because even though I have all the remaining... seats uh i cannot pick all of them with either these four or these four so expect one okay i'm going to do a dry one um so i think my n will be one

And then my seeds that are taken will be one three. So that'll be a 2D array. So I have to do one three. And then the rows to check is just a set. And then after I go over this. seats here it says the rows to check is like maybe i can make it two just to make it clear maybe just one first all right so uh the rows to check here will give me basically just the first row so it's going to be one so this is my set oh my set will just have one in it and then um sorry it's on this line here yep

And then for the seed sets, I'm turning this array into a set for fast access. So it's going to look like a set and then with one and three. So my account is zero. Now for the row and rows to check, it's going to be one. And then I have left, middle and right that to true. So now I'm going from two to six, which means I'm checking. one two and then one basically everything so like one two one three actually one two one three one four one five all right so one four one five

So I have these four slots and I'm checking if it's in this seats and I do because 1-3 is in there. So because 1-3 is in there, I set my left to false. So at this point... My left is false, but middle and right, it feel true. Oh, sorry, keep toggling it, something. Well, yep. And then for foreign, sorry? Yeah, continue. uh yeah so now i think for four and eight there's some overlap here but it's like one four one five um one six and then one seven

And in this case, none of this is in here. So I never said middle to false. It would still be true. And then for the last one, it would still be the same. So in this case, only the left part is false and middle and right will be true.

So now I go into this check. So my left and right is not both true. So then I go to the next one. It is left or right because it's either... false here and true so it will go here and then it will add uh count to be one and then oh i think i shouldn't add this in actually i don't think i think it's Okay, but my rows to check is a set, so I think I have to take N minus the length of rows to check here for it to be exact. So now I have my, when I go to this line, my C is 1.

And I'm trying to add it with whatever, like to multiply by the number of rows minus the row that I have to check, which in this case, since rows to check is a set, I just... turn it into like get the length so it's one and it's one minus one so it's zero so it's just one plus zero equals one so i think in this case it return

And theoretically speaking, if I toggle the configuration so that you had 10 rows, but only one of those rows was occupied, how would that change your answer? What would you prefer for a C in that case? Yep, yep, for sure. Let's say at the end of this, my count was still 1, but now if I were to have 10 rows, then it would be 1 plus 2 times 10 minus 1.

So that would be 1 plus 18. So I think that would be 19 slots. Yeah, so I think because... it's 19 slots because i have one for a row but then for the other uh hold on i think i'm a little confused but um yeah i think for the other nine Each of them have two. So that would be 18 and plus one, that'd be 19. So yeah. Yep. I think you're on the right track here. Okay. And do you want to briefly go over the time and space complexity of your approach?

So I think for the space complexity, I still have to create a set. But since basically I'm basing the set... of this array seats here. So it will be the number of elements in the seat. That's what I'm going to have for my space complexity. So number of elements in seats. And then for the time complexity, it will be um because i'm looping through each of the row that is present in the seat and then um and then of course i'm doing these checks but since like

It's been limit. So I would say the time complexity would just be also the number of elements in seats. So I think in this case, I have the same time and space complexity, because the check for if this coordinates is in the set is O of one. And then even though there is some overlap in this for loop, It's an order that I know it's at most 10. And I'm doing it here like 12, just checking 12 slots here. That's a fixed number. So I would say this is my final space and time complexity.

Mm-hmm. Yep, this sounds reasonable to me. I think that this looks good. So, like, basically, like, if C was equal to S, we have a space complexity, but... It's in linear time, OFS, and linear time complexity approach as well. Yeah, okay. So, we still have some time left. I do want to ask, like...

If you want to make any optimizations or you can see places where you think you would clean up the code, if you were to put this in a production-grade setting, what are some things that you would try to do? In an interview setting, we tend to make code more concise, but if I reviewed your code or if I was concerned about code quality, what are some checks or modifications that you'd make?

Yep. So I think, so my first observation is that this part from line 87 to line 100 is very similar to each other. So maybe I could make a helper function that helped me. like that returns whether this range is true or false, right? Like whether I can have like seats occupied in this range. So I would have like a helper function, like say,

can range, or like it range available or something. And then I would put that code from line 89 to 102. It looks oddly similar. I'll put it into this helper function. And then this would... takes like output a boolean and I think that would help me really clean up the code because for the column here I only care I only care about it when it's like

in this range and then in this range and in this range. So like basically I can just assign three variable to this helper function and get my answer. And I think... I think I can keep this piece of logic in here. And I think two is also like a random variable that I just made up here, but I could make it.

a constant that is like the maximum number of seats I could grab for an empty row of groups I could grab for an empty row and then like assign it here at the beginning or something like max groups per row.

and then assign it to two. So at least it's not too random when someone see that I'm adding two here. And then I'm thinking of... this so like rose to check and then for this set um I'm not sure if I could clean it up further but probably i'm just curious like what you would what you would do in such a setting um sorry can you repeat that it was i just want i just want like sort of uh

delve a bit into your brain and see what type of modifications you'd make. But I do like the suggestions that you took a look into, like the content or what seems to be random and putting a modular function. yeah i mean i also think that maybe if it's not 10 if it's like a bigger number um

But then the problem kind of changes because it's not a group of four anymore and it's not 10. Then I think I need to... somehow have the mess variable and know where the partitions are but that's like a different like it's a generalized but way different problem then yeah i see okay

I guess another way that I could kind of stress test you a bit is if we had to develop a locking posture for this reserve C. What's the... What's some information that you'd log if you had to do analytics or you wanted to take a look at trends over time with your seat reservations?

I see. So like if I want to look at a time series of my seat reservations or something like that. Yeah. Like say an end customer or like an internal team member comes and tells you, hey, I want to like have have you output. like data or just any type of messages or outputs that indicate that help me like parse out or grab statistics what's what would you kind of do okay it's open-ended it's not right or wrong

Okay, yeah. So basically, I need to store data somehow, but I also need to know what the data would look like for me to even be able to graph it. Let me think. So are we trying to track the count of like the groups of four over time or are we trying to track the seats that are reserved over time? I guess. That's a good question. Let's say the groups of four. Okay, okay. So I see. If we're trying to track the group of four, the maximum group of four, yeah, then maybe in this case, I think...

I would think that saving the count is not enough. Maybe I want to have like a more granular view of where those seats could be. So I think...

In here, I just saved the calc, but maybe I could also save the index range of where they're available. For example, if I pick left and right, well... yeah or like maybe i maybe i return like some kind of enums that let people know which part could be taken so um so then maybe like for this for this one I'm doing since since left is taken it could be middle or right and then I would do middle and then right something like that but then I'm assuming that we would track like

possible empty section right like with the definition of section being either the fourth in the middle or the two and two um but yeah like so I would say like maybe if I were to break it into like two and two versus like, sorry, I think it has like autocomplete, but versus like group of four, then... Hmm. Maybe I could say like, maybe I could say like, oh, for each NN2N2, let's say it has like left versus right. So maybe for this, I could say what are the possible slots.

So if I have middle and right, I would say middle, which is four. And then I would say like two times two on the right. So something like this. Yeah, I think that makes sense to me. I can see that you're on the right track. I think I was speaking more like from like the context of a logging posture and like seeing the frequency that we run into each type of assignment.

if that makes sense oh oh oh i see like the frequency of assignment yeah so that way if an end customer comes and it's like how often do you run into each educate scenario they could like sort of do a grep or some type of fuzzy index search and they could see hey i ran into left and right at so and so frequency or i ran into only left bookings so often or i ran into the middle bookings

only so often. And by getting that logging posture, I could crunch the data and try to see how a company could evolve its boarding structures or its boarding algorithm. Oh, I see. Yeah, but that's okay. This is open-ended, and I think you're on a good track here, which is Enum Idea, which is also returning the sections that were taken or the sections that were occupied.

This action is sort of taken. That's another good formulation. Yeah, I mean, I was going the Enum way because I think this is just a count, but... if we want to identify the bisection or like something more granular, then having enum would be more useful. Okay. Yeah. Yeah, that's fine. Again, so...

I think that we're almost over time or we are over time. We're at the mark of one hour and four minutes. So I'm going to give like a couple of minutes for like Q&A. But before I give like... I like to give feedback verbally in mock sessions. I think verbally feedback is better. But before I give you feedback, I want to hear from you what you think you did well.

And then what you think you could have done better. So let's start with what you did well from your side. I think in this case, when I first saw this, I didn't do it before. So I was a little scared I couldn't do it at first. After going into the example, I was able to come up with like a rough brute force solution. And I think that was good.

And I think like at first I was able to talk about my time in space complexity. So like and it was pretty clear in my mind. So I think that was the good one. But what I could have done better definitely. make more edge case examples um i didn't think about edge case much because i was very worried with like getting the solution down first and trying to do a dry one um And then I guess like this for loop kind of trips me up a little. It was like.

It was not too confusing, but I was overthinking that, oh, maybe I don't want to have a duplicate check here. But since it's also just two items, it's not bad. So maybe I was too focused on like... the too detailed like stuff um yeah but overall i think that's about it okay that makes sense Uh, yeah, my verbal feedback is similar as well. I think that you did really well on this problem. Personally, I think, like, it is Lika medium, and I really like it because...

So I was given it personally in an interview in the past. And I think it's good because it's a real-world scenario that forces you to read a word problem. parse out a word column and turn up a solution and the solution is that like overly complicated in terms of data structures the complexity is in set or even in hash maps

So it's actually more of a test of how you handle a real-world problem with constraints. So the handling of constraints and even knowing how to leverage sparsity to get to a more optimal solution. It's a good problem for testing. how well someone can optimize their algorithm to take your operations. I think overall, you did really well.

I think like if I had any suggestions, there's an educated scenario of thinking. So I noticed that the way that I try to nudge you more was to really think about the edge cases. Yep. And as well as like also kind of thinking about. I think what I mentioned, like the idea of sparsity or the idea of leveraging like other constraints, it's to really look at the problem statement and to see like the information that you can use to your advantage.

But I mean, overall, I don't have like strong negative feedback. I have mostly positive feedback. Like you have code. I'm fairly confident that if you fruit doesn't leak code. and maybe made some modifications, you can get this to pass. In fact, after this interview ends, I want you to put this on the code and get this passing.

Okay. I think you did well with reasoning about the time complexity, your space complexity. You got it to really efficient solutions. I think your Python code is readable and it's very concise. I really like the... conciseness of the rules engine and the way you handle your algorithm, I really like how you were able to tweak your approach as you better understood the problem. So initially... I noticed you have some struggles with the left equal to middle equal to right Boolean expressions.

Or the rules engine from 107 to 112, but you also got out of it. So it's not like you were stuck on it fully. Eventually, maybe after some nudges and your own thinking, you were able to, like, figure out your way through it. So, kudos to you on that as well, and just general persistency throughout solving a problem. Yeah, I also make really thinking about your approaches, like...

You were thinking about, even though you didn't go through throttling, you did consider throttling, which is a good thing to think about. And, yep, you also think... and you did some really good thinking with the empty row scenario so really understanding the empty row scenario helped you in this problem where you had two feet where you had like you eventually you figured out app you figured out you're not supposed to return

three times the number of, like, empty rows. It's supposed to be two times the number of empty rows. So you got that too. Yeah, overall, I think your performance here is really good.

Okay, thank you. I was a little concerned because I thought in 45 minutes, I have to solve two mediums or something, or maybe more. So I was very concerned about TAM as well. Yeah, but I don't know, maybe for an interview is only one question per... Per 45 pounds? In interviews, you could get like one medium, but the medium could be taken in a way to really stress test you. So you can't necessarily say like, just because I only got like one medium means that I'm like underperforming.

oh i mean it is the cake that like when you usually finish fast like you would get like two mediums or something or you you get like a medium and then you wouldn't be expected to solve the second one you just be expected to explore it a bit If that makes more sense, right? Okay, I see. Well, yeah, I mean, I was able to stress this to you in some other way. So we had some remaining time and I did ask you like how you would change your code or like what is...

Or like that question about like stakeholder or customer. Okay. And yeah, I really like how you also typed out and laid out your thought process and how you visualize the problem. So that was done really well too. So I was able to follow along and understand your file process. You're really good at technical communication. All right. Thank you.

All right, that's all we have for today. Thank you for watching. And if you want to get immediate feedback from the same people who make hiring decisions at companies like Google, Meta and OpenAI, hit the link in our show notes to book your session now.