Google Coding Interview With A College Student

what's up everybody how's it goin this is a Google coding interview with a college student I paired up with Tim you may know him from his youtube channel tech with Tim he's got a very popular YouTube channel he posts all sorts of videos related to programming check it out if you're into programming which he probably are for watching this video we also did a couple of collaboration videos on his channel so be sure to show him some love but so Tim is a first or second year college student in Canada he's currently preparing for coding interviews at a couple of big tech companies after the holiday break and we decided let's do a mock Google coding interview for all of you now two little notes before we jump into the interview the first one is that I conducted this interview exactly as I conducted coding interviews at Google this is exactly what a phone interview would look like because we were on hangouts we weren't in person it's conducted on a Google Doc I know you all love Google Docs for coding interviews smash the like button if you like Google Docs oh god what have I done I think that's gonna be maybe one or two people who smashed the like button because if they love Google Docs for coding interviews smash the like button anyway but so yes this is what a real Google coding interview would look like the second note that I wanted to say is that tim has actually been preparing for his coding interviews for the past two to three weeks using algo expert my company algo expert oh he's been doing a bunch of the questions I think he told me he did about 50 questions now the funny thing here is that I actually told him to prepare with easy medium and hard questions so he did a bunch of those and you know my being the nice guy that I am I ended up taking a very hard question from algo expert to give him for this interview now I know for a fact that he hadn't seen that question he told me he didn't look at any of the very hard questions so everything is fair game and with that see if you can follow along and enjoy the video Oh in the last five to ten minutes of the video or a debrief session where he and I just kind of analyzed how he did in the interview for real now enjoyable alright so Tim we're about to start the mock little coding interview is there anything that you want to say to the audience yeah so I figured I just gave you guys a little background of kind of my prep for this so maybe you have an idea where I'm coming from so I'm 19 I'm not sure if kalam mentioned that previously I'm currently looking for some internships for the summer so I've been using algo export for probably the past two to three weeks and I've got fairly comfortable doing most of the meat medium and easy problems the hard ones I'm still kind of working towards but I'm definitely getting better and yeah that's kind of the level I'm excited to do this and it's obviously some great practice or when I go and do some other coding interviews out real companies in the future awesome and we also actually did one practice mock coding interview before this so Tim got a little bit of experience doing interviews with me just you know before but for sure with that Tim let's begin I'm gonna start the 45-minute timer now awesome all right so Tim when we tried to get this to happen the smart coding interview we naturally had to put something on the calendar right yeah to find a time that works for both of us and you know give ourselves 45 minutes or an hour to make sure that we had enough time to record this so I want you to write an algorithm that is gonna basically take two peoples calendars you can imagine Google calendars and it's gonna basically return free slots of time during which these two people could have a meeting now here I'm gonna add a few other things to make sure that we're we're really on the same page here you can imagine that our calendars are gonna basically be in the format of the starting like either they're gonna be lists of tuples or lists of lists of length two so it's going to something like you know one calendar would look like this where it might be noon to let's say 1:00 p.m. then it might be 3 p.m. to 4:30 p.m. something like that it would actually be in military time so it'd be 15 - okay 60 and 30 exactly okay and so this would be one calendar maybe mine this means that I had meetings between noon and one between three or thirty I'm gonna give you a second calendar which is gonna be your calendar and then I'm also gonna give you some daily bounds because you can imagine that you might not want to have meetings before let's say 8:00 a.m. or you might not want to have meetings after let's say 6:00 p.m. so I'll also give you something like daily bounds equals let's say 8:00 8:00 a.m. and let's say 6:00 p.m. which would be 18 so this means that you not only have these meetings here but you also don't want to schedule meetings before 8:00 or after 6:00 p.m. okay okay so did then so yeah given to calendars and to daily bounds and I'll give you a sample input in a second and a meeting duration so in our example you know we need about an hour for this interview but the meeting duration could be any duration I want you to return a list of availabilities during which we could schedule our meeting so here's an example and then feel free to ask me anything you want okay all right okay so sorry I'm just looking at that now I thought you're actually gonna continue that's why I was stuck no no no problem um okay yeah so can we assume that any like time you give me for a meeting is within the bounds you gave me what do you mean by that so for example say it like say you said like you know person one says they have a meeting for like they only want to book meetings from 9:00 a.m. till in this case I guess we'll say you know 20 what is that 8:00 p.m. then all the meetings you give me will be within those bounds right there yeah no meeting that starts so like 8:00 8:30 or a 45 or something yes and they'll be all like we can assume all valid input right and these okay so these are strings that's interesting as well okay yep they're all valid inputs they're all strings and they're all in military time so okay 3:00 p.m. is 15 and so it looks like these are sorted right now I'm gonna assume they're not necessarily sorted no you actually can't assume that they are sorted you can almost imagine that like when you open your google calendar you kind of see the meetings in sorted order you know in descending order yeah beginning of the day to the end you can imagine that that's the order they're gonna be given in okay and last thing here so for example you free saying I'm looking at input I'll highlight as you can see here um 10 to 11:30 so then 11:30 is the end 12:30 is the start so I can obviously say that I could have a meeting from 11:30 to 12:30 right like that would be I know this says 30 but that would be valid 11:30 to 12:30 11:30 to 11:30 to 12:30 would indeed be a valid block during which you could schedule a 30-minute meeting but because of the top here you have this person or in this case let's say he who has a 12:00 p.m. meeting as you can see in the answer the block that we would be able to schedule would only be until 12:00 okay okay so yeah okay so obviously that makes sense but um yeah I'm just trying to figure out you know if we meeting ends at 11:30 the next meeting can start at 11:30 and then if the means at 12:30 the next meeting can start at 12:30 so I don't have to do like 12:30 1:00 or something like that yes yeah okay awesome okay so I think my initial kind of idea here is I'm gonna look at one person's calendar to start and I actually only really care about the end times because the start time but obviously I can't start and hmm so actually I do care about the start times but the end times are what I want to start by looking at so essentially I'll look at the end time 11:30 and then I'll look at the next start time and say okay if there is enough time within that block for whatever this I'm meeting duration is so in this case when I'm looking at 11:30 and I'm looking at 12:30 I know I have an hour so that's an hour of free time that I could technically book a meeting so what I would want to do then is check in the other person's calendar if they have time available between 11:30 and 12:30 yeah in this instance what I would do is say okay so between 11:30 I'll add 32 that if I can book something in that time so between 11:30 and 12:00 that's about it that's kind of like the naive approach I think to do that now because this is sorted like I feel like I could search in this a more effective way to find whether they have a valid meeting time right now I'm just sorry I'm just kind of talking out loud trying to explore yeah yeah for myself and get an idea of how I want to do this okay so yeah so I think that initial approach is going to be to look in one person's meeting this will be kind of my step one of the algorithm and figure out essentially all the spare times that they have because if I can figure out the spare blocks at times they have that's step one that's gonna help me towards the final solution which is then just comparing those spare blocks of time to this next person's input so how do I figure out the spare blocks of time well I look at the ending time of one block and I look at the starting time of the next block and then essentially if I have time in between that then I can make another list and say okay so I have an availability in this person scheduled between 11:30 and 12:30 then I could go continually so here for 30 okay so there's no time here so now I'm gonna look at the end block here which is 15 the start here which is sixteen that means I now have an hour available there so between fifteen and sixteen I could book a meeting then I'll look at seventeen and when I actually get to the end block here what I can say is well that will go to whatever our bound is so in this case eighteen thirty I technically would have availability from seventeen o'clock until 1830 because that's the bound that you gave me there and then the same thing here at the front I could treat this as the end time of say you know another block and say okay well from 10:00 to 10:00 well obviously I can't do anything there because that's about okay so once I can do that aspect then what I need to do is compare it to this block here so if I have a non disconnected sorry I'm just gonna write some list down here yep so let's say I can generate my list that look like 11:30 so I have an availability I know in person to schedule and I guess it doesn't really matter which person I do this for but let's just do person two for now at 11:30 to 12:30 I don't have anything at the upper bound because 10 is that upper bound I haven't availability from 15 to 16 so let's do this 15 that should be a string but that's okay if you want you can remove the quotes for now if it's - yeah it's okay it's just it's just a habit of mine to do it like that and then I would have an availability because now the OCD is gonna kick in if I don't do it every time 17 - 18 30 okay okay so so these are my list of available times from this schedule and I think I mean correct me if I did that wrong but I'm pretty sure that is right for the available times that person to house for president what I should yeah for person too so now what I want to do is compare this to person 1 so how do I do that so this person hmmm has their balance of 9 to 10 Oh so what I think I should probably do is actually the same thing for person - and I'll already have a function that can do this for me so that will actually mean I'm not gonna be repeating really any logic and actually now I'm gonna go no quotes so in this case 9 to 10:30 I have a time from 10:30 to 12:00 available and then I have a time from 13 to what is it 16 and then I have a time from 18 to 20 so sorry I forget what oh so the output is all the times that they could possibly have a meeting okay so although all the available blocks of time so it's not necessarily all the 30 minute increments it's basically okay all the three blocks of time during which I do a meeting okay so what I think now I need to do is say okay so my start time I have between 11:30 and 12:30 so now what I'm gonna do is look at the end o because now I gotta figure out what time so that there isn't available to here from 10:30 to 12:30 so maybe what I can do is say if 11:30 is in between these two blocks and I have half an hour between this end time I see now I'm kind of confusing myself a bit because now I have to get I got to get all the available blocks not just the 30-minute intervals okay sorry just give me one sec to think yeah no problem no problem yeah so 11:30 is the earliest possible time I could have a meeting and then if the earliest possible time is 10:30 and it goes to 12 then I guess I could have a meeting from 10:30 to 12:00 so what I'm thinking is find the beginning time here uh-oh okay because what I'm thinking what's where I'm getting hung up here is like what if I had something like 11:00 because I guess I could have this like 11:58 you know technically this this wouldn't be enough time to have a meeting right so what I might what I would do then I guess is just strictly remove that because I can't have a meeting within that block of time so if I can do that first so essentially remove any blocks of time that are less than half an hour then that's gonna help me a little bit more towards the final solution so let's say that's another step so we're going to start by building all of the blocks of available time that either person could have yeah then what I'm gonna do is remove any blocks that are invalid so if it's less than half an hour in between then get rid of them because there's no point we can't even we can't book a meeting in that or half an hour for this example but whatever that time is okay and this will be sorry this will be in minutes right so this will be this would be 30 so 30 would represent 30 minutes if it were one hour it would be 60 okay could be 90 minute and then you okay all right so what's once I remove that then what I need to do is say okay so I have block from 10:30 to 12:00 so now I look at this first block because these will be still in sorted order based on just the property of when I'm adding them in and I'll say if 15 is in between these two blocks let's check if we can do a meeting okay it's not in between these two blocks so let's move to the next block okay so 15 is in between this next block I know that I have enough time in here to do a 30-minute meeting because I know that these is a valid range so now I check since 15 is in between these two blocks of time if there's a half an hour to the end time or whatever that time is so here I'll find 15 then I'll compare it to the end time and I'll figure out what the difference between those two are if that is greater than half an hour then what I'll simply do is go 15 to the end time I think yeah and that looks like that works based on this 15 to the end time if the end time is greater than half an hour because at any point in there I could bla book a meeting but as an example a quick question sorry to cut you off shore imagine that here you had had a bunch of other availability is basically here a firm you like person to what suppose if this was person to you had had something like you know 12 32 I don't know 14 or or rather let's say you start over from the beginning let's say you had had you know 7 to 8 then you had had 9 to 10 then you had had 11 to noon and so on and so forth how would you how would you know that this 15 to 16 here sort of yeah corresponds or can be kind of merged into this 13 to 16 uh okay so well the reason I'm saying that is because the 15 is in between these two numbers so in this instance when I have eleven twelve well obviously 15 isn't in between those two numbers so I know I can't book anything in here because well 15 is greater than the end time right um okay so if it's in between these two values which it will it and I think that's like a valid comparison just to check you know if it's less than whatever then if it's in between the two values which it is here I can look at the end times specifically and figure out the difference between my start time and this end time then what I can actually do I think is take the minimum of whatever the end time is here and whatever the end time end time is here and that is a valid block to book a meeting in and then I've eliminated now from this list this block here I've figured out that I can have a meeting based on this time from I guess what is it 15 to 16 so now I can move to my next block which is 17 to 8:30 okay so now that I'm a nap does that is that like answer your question whatever yep okay okay great so now when I'm at 17 and 8:30 what I'll do is I'll figure out if 17 is in between any of these values so now I've actually I know that you the last one was in between here so I can actually just start looking from here right because I know this is sorted so I don't even need to bother looking at the rest of the list but that's kind of an optimization technique that I will focus more on later so I'll look I'll start looking here I'll say 17 it's not in between these two numbers but 17 is in between 18 and 17 is not in between 18 and 20 okay so that's where that falls apart if I'm just looking at the start time hmm okay so 1718 so if I just look at the start time that doesn't work I need to look at I think maybe the start time and the end time and see if they're in between those two values because if the end time is in between the two values which in this case is 1830 so Tim let's take a quick step back because I think the yours you're on the right track here you have the you have the idea but now you're at this step of of having to kind of figure out where you can kind of merge that these availability yeah right so exactly yeah if we take a step back the first thing that you did you even said that you would have this reusable function is you transformed for each person you transformed to their calendar into a new calendar of blocks of time when the person is available right yes like these times here represent chunks of time where the person is available and yes you filtered these and you said remove any chunk of time that's less than our meeting duration correct exactly yes so basically what you did is you you almost answered the question but just for one calendar in the first step exactly right okay so now let's see if we could if we could simplify the approach that you're going with which I think could work but might be you might have a little bit more complication when you're trying to merge the things imagine you could have imagined you could have instead of at the beginning when you took a calendar like you took this calendar of unavailability x' right or meetings and you went you calculated the in-betweens right you took the things in between and these were your availabilities and then you filtered them imagine you had in this calendar you had a mixture of both calendars so you basically you you you do the opposite of what you did instead of first finding the availabilities imagine you had first merged both of these meetings or both of these calendars rather you merged both of them when when you have the meetings you you kind of you mix them such that you have all of the blocks of time when one or both of the individuals are in avail you write one or both are unavailable and then you do your step of calculating the in-betweens which at that point essentially gives you the answer does that make sense uh okay I know exactly what you're saying so you're saying I'm I'm doing this two times and then trying to merge why don't I just make one big list do it once and then I don't need to even bother with this merge step which is obviously gonna be very complicated based on what I've been talking about perhaps that okay yet perhaps so I'm thinking what I so if I can actually I want to write like a merged version of this so I need to merge them in sorted order so to do that I can do it's almost like you would do it in merge sort right where I'm gonna just insert this one then I'll check in here if I can insert it if I can I'll insert it then we'll go to the next one don't wait insert so I know how to do that so I can insert this in sort order so now if I have one that's in sorted order then I can calculate the in-between times then I can filter and then whatever blocks of time I have in my remain like what in my filtered list are the times that they should be available I think that makes sense I really I just want to write these yeah like it's one if you want to write exactly right that merge the thing that you just mentioned yeah because I mean I think that makes sense but I gotta visualize this first to be able to figure it out right because okay so now it gets a little bit complicated just because this goes from 9:00 to 10:30 and then this is 10 to 11:30 right so that's sort of merge them is gonna be a bit of a different process than what I had come up with before but we will sort them by start times okay so let's go 16 18 and by the way sorry how much time do I have you know you still have 25 minutes and don't worry about it for now just you're you're doing okay yeah okay great um yeah I just really want to understand the problem before I start doing a massive code right okay so what I think now so now that I have these together now I gotta come up with a better way to figure out which blocks of time are available because there will be some overlaps and some of the times whereas in the other ones there wouldn't have been overlap so that would have been easier so here we start at 9:00 we go to 10:30 so what I can do is actually look at so I'll say 10:30 is my end time my next start time is 10 so what I'll actually do is make this the next start time if this start time is less than the end time then that way I know I'll have the availability from 10:00 uh actually 10 so yeah so if I could so say I could change this to be 10:30 then that makes a little bit easier because then now I know from 11:30 to 12 is fine and then okay so this is greater than this so if I could change this to be 13 this should be giving me valid I'm just gonna change them to make sure it makes sense and here if here Tim I would almost argue do you even need to do that or can you even just some no I I don't I delete that I don't need to and and just merge the two times together that's exactly that would probably make more sense so essentially if if I could go back to what I had so if I have this if this time is greater than this time then merge these two entries so I think that'll be my first step in the process so then we now have this new list so now this is my last end time this is my newest start time so now I have from here to here since this entry is less than this I'll check if this block of time is the amount of allotted time we need and if it is I can add that into this output next we go from 12 to 13 and then since these times are the same I can merge them so I can go like that and now what I can do is now look since these times are the same I can merge them again okay so let's merge them like that and now okay so this is less than this so is it more than half an hour it is ok so let's add 15 and 16 to our output okay now let's look at 1860 oh this is greater than this one so what can I do I can merge them okay and I get 1817 and now what I need to do actually sorry this 18 so that okay so this is where it's a little bit confusing for me it's because these are the same start times and then this down time is actually greater than this end time right so since this is greater than this I need to check if this is greater than the end time too because if it's greater which one do you time then really then I would take the max obviously would you take the max or than that well if I'm available from if I'm not a this is sorry this is a list of my no this is a list of mine on available times yeah this is when this is when one of the two people is booked yeah so this is one they're booked so if I'm booked from 16 to 18 well then this doesn't even this isn't really even relevant cuz I'm booked from 16 to 18 which means I'd be booked from 16 to 17 anyway so I would take the max yep I would definitely take the max okay sorry you just confuse me a little bit with that that's okay I totally didn't just get confused myself okay now you're good okay great yeah so just taking a sip of water now what I would do is look at the bounds that I have so what I can do with the bounds is simply take the min of whatever these bounds are so in this case I'll take oh sorry I need to take the max on the yeah will it be the max on the left side the min on the right side I think that makes sense yeah so max on the left side mean on right side so in this case this would be the bounds I want to look at 10:00 to 8:30 and then I could just see then I need to look at the first entry in my list and I will actually need to merge that again so these bounds now are giving me a little bit tricky as well so if I have like D and I do like 10 like that I would just think of what I can actually do is just compare ten to whatever this first start time is yep and then I can just change this almost to be just ten but if for example this said 9:30 then I would just need to scrap this whole thing so actually what I think I could do is probably just compare all these blocks of times to whatever the bounds that I have and if they don't fall within the bounds I'll modify them or remove them and for now for now let's actually did you keep the bounds even aside because I think I understand where you're getting at but let's even yeah forget about the bounds for a second let's not complicate ourselves yeah okay so I think me now is probably actually a decent time to start writing something so I will run through this one more time just to make sure that I'm refreshed what I'm gonna do is insert in sorted order into a large list both the avail build or the I guess the busy times of person one and a person too yeah I'm gonna ignore these bouncer now because those will talk about later I guess and then what I'm gonna do is do those comparisons as I talked about so I'm gonna compare you know not so I'm going to compare the end time to this end time and I'm gonna say okay well if this is greater than this I'll merge them together but if this end time in the the other list is less than the end time here I can actually just remove this entry altogether um because that'll just give me because I'll be busy during that time yeah then I'll I'll do the same thing for the next one so I look at twelve to thirteen although this will be a big list so we'll do that all together and then when I get to the end of that what I can do is literally just compare what I talked to before the end time to the next start time if there's enough time there I'll add that to the output yep same exact here right if there's enough time here I'll add that to up okay so let's start doing this okay and again the Capitals here are gonna be weird don't worry Google Dog soda fine don't worry about the Capitals yeah don't worry about the auto define is there a name for this with a calendar a Lakota Vail for now I don't yeah that's fine okay calendar avail I'll just I'll ignore the the bounds for now and in my info we can change them later so say person one schedule person to schedule and then what else do I need I need time so we'll do that and a time is I'm gonna write this in Python so time is actually fine as a keyword okay so now what I need to do is I need to insert these into sort order so that means I need to make a list so I'm gonna say and by the way feel free to feel free to simplify the variables if it's too annoying to type out up you okay there you go we'll do that so and yeah just case sense okay so book times so now I need to get into the issue of how am I going to compare these string numbers so I almost want to make a function just to compare these two tell me I'm gonna do it like I would actually do it in Java and get like the one negative one zero based on if it's greater than or less than for comparison so I'm gonna say define compare x is a time one time to now we need to get our out first and we need to get our minutes so I'm going to say our one equals and in this case it's gonna be time one dot splits : and I think I can actually do our one minute one is gonna be time one dot split that should actually decompose that because I know and I'm guaranteed that I'm gonna have these zero zeros and will I have yeah so that should be fun cuz I can split it the : yeah and you can assume assume that these strings are gonna be in such a way that your math here is correct and you don't need to do fancy edge case handling or anything okay good cuz I was gonna make it a lot more complicated for not even really part of the problem okay so now we'll have our one minute one so we can start by saying if and actually I could literally just convert these two minutes and then do the comparison so I could just do our one times 60 Plus okay so let's actually do that it's gonna be our one minute one yeah that's fine okay so we're gonna just say time one I'm gonna change that to my initial variable is going to be int hour one multiplied by 60 plus minute one and then time two equals int and that should be actually an int as well minute one and we'll say int hour two times 60 Plus in minute - and do a quick check here I think that should hopefully just give me kind of the amount of time in minutes cuz 18 times 60 it's in this 24 hour time that should be right plus int minute yeah I think that's right and then what what I'm gonna say is if time 1 is greater than time to return 1 1 will stand for greater than and then say LF time 1 is less than time to return this would be negative 1 which will be less than and then else return 0 which will mean that's the same so I'm just kind of stealing that from the compareto method in Java though they usually use this way this would be same okay and now what I need is to create this kind of schedule thing so how do I insert these times in sorted order well I'm gonna have to use those comparisons okay so we'll start by just comparing the start times I guess and just inserting essentially with the earliest start times it are into our list so I'm just gonna say 4 oh I need actually let's say p1 which is just gonna stand for pointer 1 current P to be 0 0 I'm gonna say Wow p1 is less than the length of p1 and I'm actually going to make it p1 s I know this is like not the best way to name them but it's just gonna save me a bit of time because I know probably a bit low yeah while p1 time is less than not or p2 is less than the line of p2 s we're gonna say if in this case p1 s at pointer 1 start time which will be 0 yep so we have to say if compare times p1 s and then p2 s that pointer to zero so that should actually compare our time so if that equals equals one which is actually we're gonna say negative one this will mean that we are less than so p1 less than p2 yep so then we'll insert that into our book time so say books are there squared times dot append and then this should be P p1 s p1 I hate reading this but that's ok and then we'll say p1 plus equals 1 so p1 plus 1 so I should increment our pointers to p1 I think yeah I think that actually will work and I will say otherwise then we can just insert the other ones music booked the squared times got a pen and if they're the same we're just gonna default to insert the other one I guess I'm not just fine so set P times dot append P to s p2 and then p2 plus equal to 1 okay so after this is done assuming I didn't make any mistakes then this should actually give me that sorted list now I'm kind of doing this the way that you do it like in merge sort where you just compare like you know this one to this one and then you know our next pointers about this one if we insert this first one and then I compare this one to this one then I insert this then my next pointers here then I compare it to this one I insert that my next pointers here compare this one to this one into that so I think you're following me with that right that makes sense yep okay so now that we have that now it's time to do that kind of parsing through with a lip which is gonna be a little bit more complicated like we talked about before so I'm going to say for I'll just do for I in range the line of booked money scored times okay I don't use not 12 minutes so you're good on time okay great so for I in range the line of book Tom's and but while we're up here we're gonna say I'm just gonna call this you know what I feel like I'm gonna spell that wrong so let's just call this output they're gonna thought so we can store our stuff in there for I in range the land of booked times now I want to go through my thing one more time so essentially what I'm gonna do is compare the ending time of entry 1 ah to the start time of entry 2 if this time is greater than this then we can mush them together but if this time here is um what do you call if this time here is actually less than the other time then I can straight up just remove this entire entry okay I think that makes sense okay so I still debating whether or not that's perfect but I think that's okay so for our I'll end a book time since we're gonna compare to the one above but I could actually technically be removing stuff so I almost just want to say do a while loop because if I'm gonna be removing stuff from the loop that from the list that I'm looping in that's gonna cause issues so I almost want to use a while loop instead and then if I remove something just leave the pointer or whatever the index it was out before yes let's do that do you can say I do you need to do you need to mutate this booked times list or can you mutate maybe the output list I mean up to you whatever you feel more comfortable writing yeah um I don't think I need to mute like I definitely don't need to mutate the book times list but kind of the way I'm thinking about it right now I don't have like a better idea okay now to not mutate it although I think actually like I can probably come up with the output in this one for in one while I'm looping through I don't think I actually need to even change this or do another loop which is kind of what I was planning to do but I might confuse myself a bit while I'm coding that in the interest of time I would probably go with well there are two arguments here but I would probably go with what's least confusing to you yeah okay so I equals 0 Y lies less than the Len of in this Len will update every time so that should be good you learn a book there's four times I'm gonna say now I need to compare the end time of entry whatever to the next entry which actually means that this should be a negative one here okay so now we're gonna say start one or actually and I'll just say and one equals in this case booked underscore times i1 and then we'll say start two equals booked under squared times pi zero now we need to do is say if and one is greater than I need to use my compare times method yeah if compared times and one start - I gotta remember what I wanted to do there so if the end here is greater than the start here I need to modify the list otherwise I think I can actually just look at the distance between this and the start time and figure out what that should be okay so if this time is one so that essentially means if the end of my other one is greater than the start of my other one now what I want to do is figure out what the end of the other one was so I'm gonna say n2 equals in this case booked under squared times this should be and this needs to be I plus one yep I plus 1 and this needs to be one now I want to figure out what I should do here actually I don't even think I think I could just like skip to the next entry if this if it's the case that the other end is greater yeah so if I'm looking here and I do let's have fun an example here like I'm kind of mad that I've got rid of my example if I did like 15 what is it 17 yes if this is greater than this you know but this is greater than this one then what I need to do is put 18 here but if this is say 1630 then what I can do is literally just skip over this entry I think because there will be no availability in that time so I should go I plus 2 maybe I think that works if I just skip past that I plus equals 2 rather than I plus equals 1 because if the end time is greater so if and if compare times in this case and 2 in this game just go and 1 equals equals 1 so that should mean that the end time of the other one is greater than this end time then I could skip over it yeah otherwise so if the compare times actually so if it is isn't the case that I have that edge case so let's say we have an example here 11:30 12:30 because that'll be what do I get into the else statement then what I can do is calculate the difference in time if that is greater than whatever that value is a pass to me I can just send that into the output list as that should be an answer because I should build a book of time between that end time and between the next start time I think that's logical so otherwise if so now actually to figure out the difference in times I'm just gonna write like a pseudo function that says like difference in time and like I'll I can code it later five times I'll say if diff in time and we'll go between and one start two is greater than or equal to what did I call that variable but here here ten by by doing this hey I get that you're trying to you're kind of like trying to skip ahead here and basically get an answer right off the bat but in the case of bug here you won't have done this so will you not basically be like by doing by trying to get the answer immediately in this elf will you not be sometimes skipping getting the answer when you're in this situation but I the I think the the thing here is if I'm in oh yeah cuz you're right because I'm gonna skip over to so maybe I just won't even bother doing this and I'll just do the yeah so I do actually need some you take a listen I guess from what I was doing because I was trying to go back to the other approach but I guess I'll just mute ablest so rather than skipping over one what I'll do is just remove the next entry in this instance and then merge the times otherwise I'll do something else so we'll say else then what I need to do is literally say in this case I can just remove that next entry so I could say booked under squared x dot remove actually dot pop this is gonna be I plus 1 I don't need that entry otherwise then I'll merge the start time in the end time so I can actually just say booked under squared times i1 equals and - yes yes okay so now I've done this let's just I mean assuming this is right I've generated a list and now what I can do is literally just do the the blocks in between and then add them to the output assuming that's right again not 100% but I think it's okay so now we'll just loop through again oh and I need to make sure I increment I otherwise that's not gonna be very good is it i plus equals one I think that's fine because if I remove the entry then I shouldn't increment I but if I don't remove the entry then I should and I should I'm sorry here at 10 yes sorry yeah can you hear me are you let me just closet the time or one second are you still typing in the dock uh yeah okay just okay I'm restarting the timer cuz it had just freaked out on my end but now I see it alright okay yeah no worries I I just got a reconnecting but worst like I have all the recording on my own yeah perfect yeah okay so actually what I've just done sorry in case you missed those I did I minus 1 I plus 1 because now what I'm gonna do is if I pop the entry I need to stay on whatever that current entry is to compare to the next one cuz I've just removed it um but uh otherwise I'll increment my counter I plus one so that I can move to the next one then start doing that since this is getting long I'm gonna go down onto the next page okay and now we'll do this next while loop where I'm gonna do that comparison thing that I talked about before like the difference in between so I'll say Wow and I guess we're gonna go I equals 0 again or I could probably just do a for loop to be honest I don't think I need to do a while save for I and range booked underscored times what are you doing in this final score loop this final four look what I'm gonna do is figure out the output so essentially the difference between the end time and the start time of the next entry knot and then if that time is enough I will simply add that block so the start time and end time of the other entry to the output list and then that should be good so I need to do minus one there because when I compared to the last time and I have I plus 1 I don't have an index there I'm gonna say if in this case diff between and we're just gonna assume that I've written this function but for now I've not as it was one so actually sorry he's greater than equal to not thirty time so if the difference between this is gonna be let's go just to make this a little bit cleaner and one it's gonna be equal to booked underscore times I won yep and start to is gonna be equal to booked underscore time alright +10 yep so it not instance we can say if the difference between start and one start to and we'll assume this gives us an absolute value difference that that's not me negative um then what we'll say is add that block otherwise don't even bother okay so then we'll say output dot append and in this case we should just do and one start one start to and then return output now I'm like almost a hundred percent sure that this probably doesn't work just cuz I think I've confused myself a lot throughout like what I was doing here but the logic for my solution I think makes sense but I don't think this code will be a hundred percent just I feel like I should say that do you uh do you mind running me through the complexity analysis yeah sure the complex analysis okay so in this instance we're gonna run this loop will run I guess it's going to be Oh and plus em where we're gonna have NBP 1s and mbps p2s yeah then for this time this book the list will be the same thing so this will be O n plus M I minus 1 skipping it no that's fine so this will be o n plus M and then for this last one this will be L M plus M again as Max so this should be an O n plus M complex a unless I'm missing something oh the compare times that this will run constant time my difference between overrun constant time I don't think I've done any interior loops inside book times that append I depend actually the pop here sorry where's my pop because I know that pop will not run in constant time this pop here I'm pretty sure will run an O n so I could actually have o n squared m because this pop I'm pretty sure doesn't run in cost of some I don't know but since it's a list and it has to potentially move something it would have to potentially shift every element in the list over depending on where I pop from yeah that could be and this my average case I think is still gonna be n plus m but worst case would be a n square plus M so that would make the overall time complexity N squared plus M including this pop but pop usually is pretty fast operation implemented in Python so that should give me average time n plus M I think that's right space complexity I'm gonna have M plus M and then output will be I guess yeah so I guess that's constant so n plus M okay so yeah I think we just ran out of time sometimes you know interviewers will go a little bit over time so maybe maybe I would ask something you know very quickly how confident do you feel about your code but you sort of told media yeah if you want life spent actually like two more minutes going over the code and then we will get into the debrief and sort of end the interview but out of curiosity if you very briefly walk through the code you see any place where you think you have a bug for sure okay so my first main piece of logic I'm fairly confident and although I would like to debug it a bit to obviously make sure this is just going to essentially build that sorted list of all the times that both people are booked so the way this logic works is essentially the same way that merge sort works so what I'm going to do is compare the entry in my first list at pointer one to the entry in my second list at pointer two and that based on whatever that is so if my pointer one in my first list is less than the point of point or two in the next list I'll pen that in otherwise I'll pen the other one so this one should technically built that sorted list since I have these two pointers I won't add the same element twice because what I'll end up doing is like once I get to the end of list 1 then this will always be like greater than the other one so it will always add until we get to pointer 2 and then this I think like this condition works fine yeah I think I understand I guess here here I think you would probably have to add something to your compared times to handle that because like what you just said about this once you reached the end of one of the lists this will always be bigger or something yeah not really because you will eventually one of the lists will finish so to speak before the other one and your condition will still run so you'll be accessed on now use past the list no I actually I won't because I won't increment this pointer unless this specific condition is true so what will end up happening is if I insert this because it's oh if I answer that because it's less than okay you're actually sorry you are actually are correct yeah I'd have to do something like I don't know why I thought that was gonna work if pointer one is you know greater than or I guess is equal to the line of p1 s minus one then I would just add pointer two and then same thing with the other way around yep something like that I'm saying that okay yeah something that okay so that's like that's a good bug to catch I was kind of speeding through this one okay so now this piece of logic here is essentially trying to kind of mutate that list to find the blocks that we can use for the next part of logic which I'll talk about so what this one is gonna do is compare the start time and the end time of the blocks that are beside each other because we know that they're sorted so what that will allow me to do is essentially I'm gonna create block like the largest blocks of time that I can that are beside each other if that means so like say I have nine - like 12:30 and this is 12 to 7 and that would be 9 to 17 of clock right that's what that's doing or at least I'm trying to do in this block of code so I'm comparing the times if the end time is greater than the start time of the other one then what I'll do is compare the end times out if the end time of the other ones the one further right in the list is less than the end time so actually I think that needs to be yeah cuz here you compared it you compared n2 to end one so yeah yeah nothing I realized I think I did that backwards yeah if n 2 is less than n 1 and you are popping the value the next value Ames your D preventing that make sense your Z commenting I and then you still incremented after 2 basically like keep moving forward exactly exactly yeah and then here this is just this is just mutating that list so it's moving the end to over okay so yeah so that negative one was need to there that's what happens when I guess you speed through okay that last part I think is fine let's jump into the debrief why don't you start by telling me like how you feel right now yeah for sure I mean obviously guys like you can probably tell based on kind of my mood and what we're going through I don't feel great about this solution this problem was challenging for me to kind of comprehend just because even like this string input was like there's a lot of stuff that was just like a lot of details to deal with that ones like I kind of confused myself a little bit as I went through the different pass I'm happy I came up with a logical solution that makes sense I think the time complexity is actually pretty decent I didn't do anything too crazy with I mean I have his n square but that's just because of that pop but I didn't do anything too crazy with the complexity so that's okay I felt I explained my logic pretty well I asked decent clarifying questions but like just you gave me a little bit of hints for the solution I think maybe if I had more time or if I've done a little bit more prep on something maybe this different this difficult I would have been able to come up with it a little bit faster and a little bit cleaner you kind of get my like vibe from that yeah yeah so so listen I'll give you my input I think you did really well I think your your your assessment is probably how I would feel if I were you like you're kind of like oh yeah like I sort of got it but at the same time it's like not it's not picture-perfect but yeah what you should take away from this because again from my point of view you actually did very well I don't have to you know take a little bit of time to grade you so to speak following that yeah right area that we're given but you would probably get something along the lines of a higher or a strong higher decision here at least from me okay base no.1 and see the main reason is this first of all this is a very difficult question this is actually a question that we have on algal expert I know for you didn't do it based on the question yeah we need a dupe but so this is a very hard question on a legal expert the reason that it's very hard is exactly what you said first of all there's a lot of information there are a lot of impious there's a lot of different like types of inputs you saw that there are strings they're not numbers they're military time you have these daily bounds which by the way the daily bounds you can simplify the problem by just creating artificial meetings at the beginning and end of each person's calendars using the daily balance if that makes sense that's kind of what I figured yeah that's what I figured out that's kind of what I was trying to figure out the beginning and I was running low on time and then that was just another piece so we just skip by B I did kind of think it up exactly but but but even that like it's it's an additional piece of this complicatedness or complexity and then the thing that's difficult about this problem is not so much the algorithm because the algorithm or the logic is fairly intuitive and I think you you came up with a version at the very beginning that I think would have worked fine I just pushed you in a slightly different direction that I think is a little bit simpler but you were doing this in the opposite order of operations but then the coding the coding is difficult yes transcribing of this into code is difficult and I think you did a very good job like you pointed out the part of the code that's probably the the most shaky is this middle part here with the popping yeah and the the fact that you're kind of over writing this this thing and there's a way to do this without the popping that we don't need to get into here but I think that you you explained your logic soundly and you managed to transcribe it into something that it seems like it's getting you know it's getting close to working probably their cases here that aren't handled but it's getting close to working you also did a good job of using helper functions and that kind of thing to your advantage compared times like this is the kind of thing where a must to do something along these lines is it the the diff between here I'm uh absolute must you know otherwise like you're gonna get a gross algorithm you didn't have a little bug in the in the merging but that was you you caught it near the end and again it's like this is the kind of problem where it would be a lot to ask to expect a candidate to code this entire solution perfectly in just 45 minutes all the while solving it so this is like this is more than what I would expect especially if you're if you're going for an intern position where we don't necessarily you know have the same bar as let's say a senior position full-time senior position so yeah overall I think you you did a good job okay well I mean that's okay that's great feedback definitely makes me feel a little bit better because yeah I was kind of thinking about this I'm like this is a lot of like stuff that could go wrong with just the amount of information without being able to do some tests and kind of dig through the different edge cases and all that stuff so yeah that's great and you also you also communicated very well you asked a lot of clarifying questions well you you went through the example and by the way again this is one of those problems where you saw that you didn't get into coding until there were like 20 minutes left right sometimes it's better to take your time to figure out everything and then get into the coding then then the opposite but overall I think you you handled your time well and you organize your code and all that you know decently well and if there's one lesson I would say to take away from this one perhaps the most important thing of a problem like this is the way that you organize yourself and the way that you organize your code and everything maybe here it would have been even cleaner to have like different functions for the merging for this what I call flattening and so on but with you you separated it in a way that made sense but yeah so overall again like good job and you know to all those of you watching who who may be like whoa this is such a complicated or such a big question again you wouldn't be expected to solve it you know perfectly with zero bugs zero anything in an interview especially for an intern position but even for a full-time position Wow okay awesome yeah I mean that's some great feedback for sure cool with that ten thanks so much for for doing this coding interview thanks for sacrificing yourself for the YouTube audience and I think you're gonna you're gonna nail your your real interviews when you get to them well I really appreciate this has been some great practice and some great feedback and I mean to everyone watching you know like listen to a lot of feedback that he's giving because that definitely like this helps me a ton to do some stuff like this and I would recommend to you guys do practice out loud like do practice where you talk through your thought process could even see a few times here right I kind of getting stuck explaining what I want to do that's something that think I mean maybe you can say is really important is that the interviewer knows what you're doing I think I did a decent job of making sure that you were falling along with kind of what I was thinking but I was definitely hard for me throughout this process was not only trying to come up with the answer but also communicated in a way that you know he can understand what I'm saying exactly and by the way though the last thing that I'll add is just you know like we said this question is on algo expert and if you look at the solution on algo expert you'll see this like picture perfect perfect variable names perfectly written solution that is the ideal to strive for but it's not what would be expected of you in a 45-minute interview so that's that awesome well thanks again clintus some great yep thanks so much Tim if you made it this far I want to thank you for watching the video I really hope that you found it useful informative fun enjoyable awesome funny not stressful smash the like button worthy see you in the next one

Channel: Clément Mihailescu

Views: 1,289,874

Rating: 4.8740678 out of 5

Keywords: google coding interview, google coding interview questions, google coding interview preparation, coding interview google, coding interview, mock coding interview, technical interview with a google engineer, google coding interview python, real coding interview, google software engineer interview, Tech With Tim, tech with tim interview, google software engineer intern interview, google software engineer internship interview, google interview, coding interview questions

Id: 3Q_oYDQ2whs

Length: 59min 56sec (3596 seconds)

Published: Thu Dec 26 2019