Reacting to My Google Coding Interview

so i've got an exciting video for you guys today where i'm going to be reacting to my google coding interview so back in december of 2019 i filmed this video with my friend clement now clement is an ex-google engineer he worked there for about two years and at the time i reached out to him and i said hey i'm currently preparing for interviews at microsoft shopify and a bunch of other large tech companies would you mind conducting a mock google coding interview with me we can film it you can post it to your youtube channel and well will be some great practice for myself of course clement agreed to this and he went ahead and we filmed this coding interview so just to give you some context here at the time of filming this video i was in my second year of university i had never done a coding interview before other than one phone screen which wasn't really like a proper coding interview and while i was extremely nervous for this video i had been preparing for the past few weeks even just for this video by answering about 40 or 50 questions on the algo expert platform in case any of you are wondering what that is clement runs this awesome business it's called algo expert essentially it's an interview prep platform and it's what i actually ended up using pretty much solely for my preparation for my microsoft and shopify interviews which i ended up passing so if you guys do want to check that out i do have a discount code it's tech with tim you can get 10 off i'll leave the link in the description but anyways i was using his platform and he had told me before the video hey you know if you want to prepare for this practice doing easy medium and hard questions so i did about 50 questions between those three categories most of them being in the medium and hard category and just so you're aware algo expert has a very hard and extremely hard category as well so i was kind of doing you know middle of the pack questions what you would commonly get so of course i get to the interview and what does clement do he gives me a very hard question to answer so immediately i'm a little nervous i'm like okay i've never done anything at this rated difficulty before but let's give it a shot and let's see how it goes so anyways that's all i kind of want to talk about and spoil before we get into this interview my reaction aspect of this is going to be me just kind of popping in every few minutes and talking about how i'm feeling in a specific situation if i did something wrong if i feel like i maybe did something well just kind of giving you guys maybe my thoughts on the interview but i will kind of let it play most of the time just so that i'm not interrupting constantly and you guys can actually enjoy it if you haven't seen the original video so anyways with that being said let's get started and get into the google coding interview all right so i'm on the computer i'm about to start the interview i'm gonna leave it for a few minutes just so you guys can hear the question you can see kind of what's going on and then as soon as there's some silence or i make a mistake or something like that happens i'll kind of jump in you know discuss that a little bit and then we'll move on all right so uh enjoy all right so tim when we tried to get this to happen this mock coding interview we naturally had to put something on the calendar right we have to find a time that worked for both of us and you know give ourselves 45 minutes or an hour to make sure that we had uh enough time to record this so i want you to write an algorithm that is going to basically take two people's 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 going to basically be in the format of starting like they're going to be lists of tuples or lists of lists of length two so it's going to be something like you know one calendar would look like this where it might be noon to uh let's say 1pm then it might be 3pm to 4 30 p.m something like that it would actually be in military time so it'd be 15 to okay 16 30. yeah exactly okay and so this would be one calendar maybe mine this means that i have meetings between noon and 1 between 3 and 4 30. i'm going to give you a second calendar which is going to be your calendar and then i'm also going to give you some daily bounds because you can imagine that you might not want to have meetings before let's say 8 am or you might not want to have meetings after let's say 6 pm so i'll also give you something like daily bounds equals let's say 8 8 am and let's say 6 pm 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 or after 6 pm okay okay so given so yeah given two calendars and two 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 were actually going to continue that's why i was saying 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 like say you said like you know person one says they have a meeting for like they only want to book meetings from 9am until in this case i guess we'll say you know 20 what is that 8pm then all the meetings you give me will be within those bounds right there'll be no meeting that starts at like 8 30 or 8 45 or something yes and they'll be all like we can assume all valid input right and these are 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 you know okay 3pm is 15. and so it looks like these are sorted right now i'm going to 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 from the beginning of the day to the end you can imagine that that's the order they're going to be given in okay and last thing here so for example you'd be saying i'm looking at input tail highlighted so 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 who has a 12 pm meeting as you can see in the answer the block that we would be able to schedule would only be until 12. okay so okay so yeah okay so obviously that makes sense but um yeah i'm just trying to figure out you know if we if the meeting ends at 11 30 the next meeting can start at 11 30 and then if the meeting ends at 12 30 the next meeting can start at 12 30 so i don't have to do like 12 31 or something like that yes yeah exactly okay awesome okay so i think um my initial kind of idea here is i'm going to look at one person's calendar to all right so i'm going to pause it for one second and quickly just talk to you about what i actually just did in case some of you don't realize why i did that the first thing that i always try to do in coding interviews and what i've kind of learned is that you always want to even if you completely understand the problem ask a ton of questions so i was literally sitting there trying to think of every question i could ask that would tell them that you know i'm thinking about the ambiguity in this problem and trying to get everything down as specific as possible so i don't start solving the problem before i completely understand it so that's why i ask you know maybe potentially some silly questions just to make sure i'm clarifying everything and make sure that i really understand okay first of all these are strings you know i don't have to start at say 11 31 i can start at 11 30. oh am i going to get valid input is there going to be stuff that i have to look for in terms of edge cases that's kind of where i'm starting from and that's why i went through that so anyways let's continue and let's see what i do next is i'm going to look at one person's calendar to start and i actually only really care about the end times because the start time i obviously i can't start and hm 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 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. so in this instance what i would do is say okay so between 11 30 i'll add 30 to that if i can book something in that time so between 11 30 and 12 that's about because 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 uh right now i'm just sorry i'm just kind of talking out loud trying to explore 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 of times they have that's step one that's going to 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 and this person's scheduled between 11 30 and 12 30. then i could go continually so here 4 30 okay so there's no time here so now i'm going to look at the end block here which is 15 the start block here which is 16 that means i now have an hour available there so between 15 and 16 i could book a meeting then i'll look at 17 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 1830 i technically would have availability from 17 o'clock until 1830 because that's the bound that you gave me there and then 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 to 10 well obviously i can't do anything there because that's the bound 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 and i'm just gonna sorry i'm just gonna write some lists down here so let's say i can generate my lists that look like 11 30 so i have an availability i know in person two 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 have an 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 too if it's annoying yeah it's okay it's just it's just a habit of mine to to do it like that and then i would have an availability because now the ocd is going to kick in if i don't do it every time 17 to 18 30. okay okay so so these are my list of available times from this schedule and i think i i mean correct me if i did that wrong but i'm pretty sure that is right for the available times that person two has for person what i should yeah for person two so now what i want to do is compare this to person one so how do i do that so this person has their bounds of nine to ten oh so what i think i should probably do is actually the same thing for person two and i'll already have a function that can do this for me so that will actually mean i'm not going to be repeating really any logic and actually now i'm going to go no quotes so in this case 9 to 10 30 i have a time from 10 30. to 12 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 free blocks of time during which you can schedule 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 oh because now all right so i'm gonna jump in here for one second so if you guys can't already tell what i'm focusing on really heavily right now is just trying to come up with some kind of solution and test it with some kind of input to make sure i'm on the right track before i actually go ahead and start coding these problems for me at least are usually much easier to program than they are to understand so i usually try to take as much time as i can at the beginning even if that is in this case say 10 minutes because i had 45 minutes from the start to really digest the problem understand it and make sure i come up with some kind of thorough approach that i know is going to work before i start actually going ahead and coding the last thing i want is to write all of the code and then get to the end of it try some sample input on it and have that code break so right now you can tell i'm kind of struggling a little bit i've come up with a solution that's somewhat kind of working i feel like i'm on a decent track to getting there but i still don't know if this is going to be the exact right answer so of course i wish i could think faster and just immediately come up with the solution but we're 10 minutes in i'm kind of on one route right now you'll see in a second that clem kind of redirects me almost but let's have a look at what i do now just wanted to clarify kind of why i'm taking so much time at the beginning and not even writing any code i got to figure out what time so this there's an availability 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 ah 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 second yeah no problem no problem yeah okay 11 13. hmm 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. so what i'm thinking is find the beginning time here uh oh okay because what i'm think what's where i'm getting hung up here is like what if i had something like 11 because i guess i could have this like 11 58. yeah 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 going to 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 and then what i'm going to 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 uh 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 it could be 90 minutes and then okay all right so what's once i remove that then what i need to do is say okay so i have blocked from 10 30 to 12 so now i'll look at this first block because these will be still in sorted order based on just the property of what 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 this is a valid range so now i check since 15 is in between these two blocks of time if there's 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 book a meeting but as an example a quick question sorry to cut you off imagine that here you had had a bunch of other uh availabilities basically here from like person two let's suppose if this was person two you had had something like you know 12 30 to i don't know to 14 or or rather let's say you you start over from the beginning let's say you had had you know seven to eight then you had had um you know nine to ten then you had had eleven 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. 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 11 12 well obviously 15 isn't in between those two numbers so i know i can't book anything in here because well 15 is is greater than the end time right um okay so if it's in between these two values which it and i think that's like a valid comparison um just to check you know if it's less than whatever um then if it's in between the two values which it is here i can look at the end time 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 not now does that does that like answer your question what i was saying okay okay great so now that 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 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 is not in between these two numbers but 17 is in between 18 and 17 is not in between 18 and 20. ah okay so that's where that falls apart if i'm just looking at the start time okay so 17 18. 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 that you're 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 these availabilities 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 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 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 imagine you could have instead of at the beginning when you took a calendar like you took this calendar of unavailabilities 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 aren't available right 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 ah okay i know exactly what you're saying so all right so i'm going to take a pause there quickly so you can see clement gave me a pretty big hint there now a lot of people will say that's cheating or you know you shouldn't do that i can say from experience doing my coding interviews a lot of the time what i'm able to get the person to do and this isn't just me trying to be you know sneaky and strategic is i'm able to get them to give me a hint because i talk about everything that i'm thinking about so notice here that even though i'm kind of on the right track and the approach that i'm doing would potentially work it'd just be a really difficult implementation to do clemence heard my entire thought process he knows that i'm kind of on the right track and he figures that it's going to be easier if he simply tells me to merge the two calendars and then continue doing what i'm going to do so just kind of a piece of advice that when you're in these coding interviews talk about literally everything because even if you're completely wrong or you're like somewhat on the right track you know your interviewer may be nice they may be kind of rooting for you because they think you're going to be able to get it and they'll give you a hint like commented and like i said almost all my interviews that i did not necessarily that i needed a hint i probably could solve it without the hint but they gave me a hint and it made it a lot easier to continue going and they wanted to give the hint if that make any made any sense just because of the way that i was explaining anyways we'll jump back in here you'll see that i'm about to kind of go down the correct path but think to yourself right now there's one thing that i haven't done that i don't do this entire interview with the input that would make it a lot easier see if you can figure out what that is 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 going to be very complicated based on what i've been talking about perhaps is that okay yeah 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 going to 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 then we'll insert so i know how to do that so i can insert this in sorted 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 um yeah like as one if you want to write exactly write that merged thing that you just mentioned yeah because i mean i think that makes sense but i got to 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 to 10 30 and then this is 10 to 11 30 right so that's to merge them is going to be a bit of a different process than what i had come up with before but we will sort them by start times uh okay so let's go 16 18. and by the way sorry how much time do i have you still have 25 minutes and don't worry about it for now just you're doing good okay yeah okay great um yeah i just really want to understand the problem before i start doing a massive code right um 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 would have been overlaps that would have been easier so here we start at 9 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 30 uh oh actually 10 so yeah so if i could change 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 going to change that 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 don't i delete this 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 okay so let's add 15 and 16 to our output okay now let's look at 18 16. oh this is greater than this one so what can i do i can merge them okay and i get 18 17 and now what i need to do actually sorry like this uh 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 end 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 two because if it's greater than which one anytime then really then i would take the max obviously would you take the max or the min well if i'm available from if i'm not a oh this is sorry this is a list of my no this is a list of my non-available times yeah this is when this is when one of the two people is booked yeah so this is when they're booked so if i'm booked from 16 to 18 well then this doesn't this isn't really even relevant because i'm booked from 16 to 18 which means i'd be booked from 16 to 17 anyway so i would take the max yup i would definitely take the max okay i'm sorry you just confused me a little bit with that that's okay i i totally didn't just get confused myself okay all right you're good okay great yeah so just taking a sip of water now what i will 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 um yeah so max on left side min on right side so in this case this would be the bounds i want to look at 10 to 8 30 and then i could just see um then i need to look at the first entry in my list and i will i actually need to merge that again so these bounds now are getting me a little bit uh tricky as well so if i have like do and i do like 10 like that i would just i think what i can actually do is just compare 10 to whatever this first start time is yep and then i can just change this almost to be just 10 but if for example this said 930 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 let's actually just keep the bounds even aside because i think i understand where you're getting at but let's even yeah forget about the bounce for a second let's not complicate ourselves yeah okay so i think maybe now is probably actually a decent time to start writing something all right so i'll take a break here quickly so you can see that now we're probably what like 25 26 minutes in something like that and i'm just about to start coding so usually i would be a little bit nervous in this situation because i don't want to take half the time to digest the problem if that's necessary obviously i'm going to do that like i did here as you guys can tell you know i was confusing myself you know like there's a lot of different input and time stuff going on on the screen here but i think at this point i kind of have a clear idea of what i want to do obviously clement has helped a little bit but again the reason he's able to help me is because i'm constantly talking out loud and even if i'm thinking something that's incorrect i'm still saying it just to kind of see how he reacts to it and see if because he knows the answer to the problem if i am on the right track so there is a little bit of kind of confirming with your interviewer that they understand where your head's at and they're not going to let you kind of jump into the code and do something horribly wrong so at least you have the opportunity to kind of get checked a little bit and say okay am i on the right path yes i am okay let's keep going so anyways i'll jump back in here but now i'm about to start coding and again think about that thing that i should have done to the input that i haven't done and that i'm not going to end up doing in this interview that would make things a lot easier for me when it comes to comparing these different values which is like the main step of all of the processes i've talked about to start writing something so i'll run through this one more time just to make sure that i'm refreshed what i'm going to do is insert insorted order into a large list both the availability or the i guess the busy times of person one and of person two yep i'm going to ignore these bounds for now because those we'll talk about later i guess um and then what i'm going to do is do those comparisons that i talked about so i'm going to compare you know not so i'm going to compare the end time to this end time and i'm going to say okay well if this is greater than this i'll merge them together but if this end time in the other list is less than the end time here i can actually just remove this entry altogether um because that will just give me because i'll be busy during that time yep then i'll i'll do the same thing for the next one so i'll look at 12 to 13. oh 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 about for the end time to the next start time if there's enough time there i'll add that to the output yep same thing here right if there's enough time here i'll add that to output okay so let's start doing this um okay and again the capitals here are going to be weird don't worry google docs so define don't worry about the capitals yeah don't worry about the the auto caps and all that define is there a name for this calendar i'll just call it a veil for now i don't know that's fine okay calendar avail um i'll just i'll ignore the uh the bounds for now in my input we can change them later so i'll say person one schedule uh person2 schedule uh and then what else do i need i need time so we'll do that and i time is i'm going to 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 orders so that means i need to make a list so i'm going to say and by the way feel free to feel free to simplify the variables if it's too annoying to type out up to you okay there we go we'll do that so and yeah just case sense okay so book time so quick side note whenever i make variables just kind of a tip i've heard is to make them really readable not only does that make it easier for myself when i go back i can see what i'm doing with all these variables but clement can also understand what i'm trying to do with those so typically it's good to have variable names that are pretty descriptive but obviously in this situation i'm kind of running low in time i probably only have about 20 minutes left before this interview is actually going to be done so obviously in the name of time it probably does make sense to simplify these a little bit but we'll see how stubborn we are with that and if i end up actually you know simplifying all these variable names just for 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 to tell me um i'm going to do it like i would actually do it in java and get like the 1 negative 1 0 based on if it's greater than or less than for comparison so i'm going to say define compare times i'm going to say time 1 time 2. now we need to get our hours so we need to get our minutes so i'm going to say hour 1 equals and in this case it's going to be time one dot splits coin and i think i can actually do hour one minute one is going to 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 uh yeah so that should be fine because i can split up the colon yeah and you can assume assume that these strings are gonna be in such a way that your math here is correct then you don't need to do fancy edge case handling or anything okay good because that 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 to minutes and then do the comparison so i could just do hour 1 times 60 plus okay so let's actually do that uh it's going to be powerful all right so here i've given away what i should have just done to the entire input so you can see i'm writing this kind of complicated function that's going to compare you know string times and return a one if it's greater zero if they're the same and negative one if they're different when in reality rather than having to even write this compare times function what i could have done is just converted the entire input into minutes and then that way it would have been way easier for me to do everything you're about to see but of course i didn't consider that when i was in this problem i definitely should have but you'll see that if it was in minutes that immediately makes this problem so much easier and that's something that i just didn't end up doing uh it's gonna be hour one minute one yeah that's fine okay so we're gonna just say time one i'm going to change that to my initial variable is going to be int hour 1 multiplied by 60 plus minute 1 and then time 2 equals int and that should be actually an int as well minute 1 and we'll say int hour 2 time 60 plus int minute 2 and do a quick check here i think that should hopefully just give me kind of the amount of time in minutes because 18 times 60 since it's 24 hour time that should be right plus int minute yeah i think that's right and then what what i'm going to say is if time one is greater than time two return one one will stand for greater than and then we'll say l if time 1 is less than time 2 return this would be negative 1 which will be less than and then else return 0 which will mean that it's the same so i'm just kind of stealing that from the compareto method in java that they usually use so we'll just say 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 going to have to use those comparisons okay so we'll start by just comparing the start times i guess and just inserting essentially what the earliest start times it are into our list so i'm just going to say 4 oh i need actually i'm going to say p1 which is going to stand for pointer 1 and p2 would be 0 0. i'm going to say while p1 is less than the length of p1 and i'm actually just going to make it p1s i know this is like not the best way to name them but it's just going to save me a bit of time because i have no problem running a bit low while p1 time is less than that or p2 is less than the line of p2s we're going to say if in this case p1s at pointer one start time which will be zero yep so we have to say if compare times p1s and then p2 s at pointer to zero so that should actually compare our time so if that equals equals one which is actually we're going to 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 we'll say booked underscore times dot append and then this should be p p one s p one i hate reading this but that's okay uh and then we'll say p1 plus equals one so p1 plus equals one so that should increment our pointers um so p1 i think yeah i think that actually will work and we'll say otherwise then we can just insert the other one soon as it booked the square times dot append and if they're the same we're just going to default to insert the other one i guess just fine so we'll say p times dot append p2s p2 so quick note here that it probably would have been easier if i simply put like p1 time p2 time as variables notice here that i have like p1sp1 at index 0 and then i'm writing like all of these indexes multiple times so you know usually it's better to throw those into a variable it just makes it cleaner and that's typically better you know coding practice anyways we'll continue and then p2 plus equals one 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 up at this one if we insert this first one and then i compare it this one to this one then i insert this then my next pointer's here then i compare it to this one i insert that my next pointer's here compare this one to this one answer that so i think you're following me with that right that makes sense yep so did you guys catch the bug you can pause it and try to find it i can tell you right now that if you have a look at this or that will probably give it away to you essentially what's going to happen here is i need to actually throw in a clause in this while statement that says you know if p1 reaches the maximum length then just add all the values from p2 if p2 reaches the maximum length like the pointer then i add all the values from p1 i not sure if i do that afterwards we'll actually see if that happens but if i put an and instead of the or then that means that i will end up adding all of them assuming assuming i have that kind of like clause in the while statement or that condition in the wall statement anyways i hope that makes sense but see if you can catch that bug okay so now that we have that now it's time to do that kind of parsing through with the which is going to be a little bit more complicated like we talked about before so i'm going to say 4 i'll just do 4i in range the lan of booked underscore times okay i thought you still have 12 minutes so you're good on time okay great so for iron range the line of book times and let's see but while we're up here we're going to say i'm just going to call this a veil you know what i feel like i'm going to spell that wrong so let's just call this output okay was that so we can store our stuff in there for iron range the lan of booked times now i want to go through my thing one more time so essentially what i'm going to do is compare the ending time of entry one uh to the start time of entry two 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 uh okay so i'm still debating whether or not that's perfect but i think that's okay so for eyeliner book time since we're going to 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 going to be removing stuff from the loop that from the list that i'm looping in that's going to 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 um yes let's do that i'm going to 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 less but kind of the way i'm thinking about it right now i don't have like a better idea okay for how to not mutate it although i think actually like i can probably come up with the output in this for in one loop 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 um 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 let's say i equals zero while i is less than the lan of and this line will update every time so that should be good elen of booked underscore times i'm going to 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 end one equals in this case booked underscore times i one and then we'll say start two equals booked underscore times i zero now what we need to do is say if and one is greater than now i need to use my compare times method yeah if compare times and one start two 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 1 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 going to say n2 equals in this case booked underscore times this should be and this needs to be i plus one on that i plus one and this needs to be one now i want to figure out what i should do here um 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 find 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 yeah so if this is greater than this yeah but this is greater than this one then what i need to do is put 18 here but if this is say 16 30 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 two maybe um i think that works if i just skip past that i plus equals two rather than i plus equals one because if the end time is greater so if and if compare times in this case n2 uh in this game just go end one equals equals one so that should mean that the end time of the other one is greater than this end time then i could skip over it yep 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 the example here 11 30 12 30 because that'll be what 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 that passed me i can just send that into the output list as that should be an answer because i should be able to book a time between that end time and between the next start time i think that's logical so otherwise if so now i actually need to figure out the difference in times i'm just going 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 end one start two is greater than or equal to what did i call that variable but here here tim by by doing this i 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 above 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 else will you not be sometimes skipping getting the answer when you're in this situation but the i think the the thing here is if i'm in oh yeah because you're right because i'm going to skip over two so maybe i just won't even bother doing this and i'll just do the yeah so i do actually need to mutate the list then 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 the list 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 underscore times dot remove um actually dot pop uh this is gonna be i plus one because i don't need that entry otherwise then i'll merge the start time and in the end time so i can actually just say booked underscore times i one equals and two uh 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 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 uh oh and i need to make sure i increment i otherwise that's not going to be very good is it i plus equals 1. 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 tim yeah sorry yeah can you hear me are you let me just pause the timer one second are you still typing in the dock uh yeah okay just okay i'm restarting the timer because it had just freaked out on my end but now i see it all right okay yeah yeah no worries uh yeah i just got a reconnecting but worse like i have all the recording on my okay perfect so it's fine yep okay uh so actually what i've just done sorry in case you missed that is i did i minus one i plus one because now what i'm going to do is if i pop the entry i need to stay on whatever that current entry is to compare it to the next one because i've just removed it um but otherwise i'll increment my counter i plus one so that i can move to the next one then start doing that um since this is getting long i'm going to go down onto the next page okay and now we'll do this next while loop where i'm going to do the comparison thing that i just wanted to pop in here quickly and say i hope you guys can appreciate how difficult it is to code in google docs with like the auto indentation tab issues with like the auto complete capitals that was really throwing me off but anyways just wanted to note that that this is a lot more difficult than say writing on the whiteboard i've done both and writing on a whiteboard is way easier than this there's something that i talked about before like the difference in between so i'll say wow and i guess we're going to 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 say in range booked underscore times um what are you doing in this final four loop this final for loop what i'm gonna do is figure out uh the output so essentially the difference between the end time and the start time of the next entry 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 -1 there because uh when i compare to the last element i have i plus one i don't have an index error okay i'm going to say if in this case diff between and we're just going to assume that i've written this function but for now i've not uh is equals one so actually sorry is greater than or equal to not 30 time so if the difference between this is going to be let's go just to make this a little bit cleaner uh end one is going to be equal to booked underscore times i one yep and start two is gonna be equal to booked underscore time i plus one zero yep so in that instance we can say if the difference between start end one start two and we'll assume this gives us an absolute value difference that that's not gonna be 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 end one start one start two and then return output now i'm like almost 100 sure that this probably doesn't work just because 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 do you mind running me through the uh complexity analysis uh yeah oh sure the complex analysis okay so in this instance we're going to run this loop will run i guess it's going to be o n plus m where we're going to have nbp 1s and mbps p2s yep then for this time this booked list will be the same thing so this will be o n plus m um i minus one skip in it alright so i will quickly pause here before i let myself continue with the complexity analysis here you can see i've just gone over time and clearly this problem was you know more difficult than i've been used to i spent a lot of time at the beginning trying to understand exactly what i needed to do and of course you know that left me with just the amount of time to kind of scrape by with the solution that as i've noted myself probably won't fully be functioning but the general kind of idea behind it is somewhat correct anyways i'll let myself continue with the complexity analysis but clement is nice enough to give me an extra i think we have like five minutes or something to go through the complexity analysis i'm not sure if i make a fix or not so we'll see um if that happens but remember there is one big bug in this program that happened at the very beginning that i think i already went through one skipping it no that's fine so this will be o n plus m and then for this last one this will be om plus m again as max so this should be an o n plus m complex unless i'm missing something uh oh the compare times that this will run constant time my difference between over and constant time i don't think i've done any interior loops inside book times that append that append actually the pop here sorry where's my pop because i know that pop will not run in constant time um this pop here pretty sure will run in on so i could actually have o n squared m because this pop i'm pretty sure doesn't run in constant time 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 n this my average case i think is still going to be m plus m but uh worst case would be n square plus m so that would make the overall time complex the n squared plus m including this pop but pop usually is pretty fast operation implemented in python so that should give me average time and plus m i think that's right uh space complexity and there's another pop in here i'm pretty certain that pop runs in o n of course i could go through this in more detail and discuss when i'm popping and how many elements i would potentially be shifting but the reason i'm classifying that as big o of n is because technically if i pop the first element of a list the entire rest of the list i would need to shift into that position so that would run in o and time if you understand time complexity you probably understand what i'm getting at but of course i wanted to make that clear in the interview bass complexity i'm going to have n 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 you you know very quickly how confident you feel about your code but you sort of told me yeah um yeah if you want let's spend 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 do 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 in 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 then based on whatever that is so if my pointer one in my first list is less than the pointer point or two in the next list i'll pin that in otherwise i'll pin the other one so this one should technically build 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 one then this will always be like greater than the other one so it'll always add until we get to pointer two and then this i think like this condition works fine yeah i think i understand what you mean i guess here here i think you would probably have to add something here compare times to handle that because like what you just said about this once you reach 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 accessing values past the list uh no i actually i won't because i won't increment this pointer unless this specific condition is true so what'll end up happening is if i insert this because it's oh if i insert 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 p1s minus one then i would just add pointer two and then same thing with the other way around yeah something like that you know i'm saying that okay exactly yeah assuming 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 going to 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 that will allow me to do is essentially i'm going to create block like the largest blocks of time that i can that are beside each other if that makes sense so like say i have nine to like 12 30 and this is 12 to 7 and that would be 9 to 17 o'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 yep if the end time of the other one so the one further right in the list is less than the end time so actually i think that needs to be yeah because here you compared you compared n two to n one so yeah yeah i realized i think i did that backwards yeah so if n2 is less than n one then you are popping the value the next values you are d okay that makes sense you're decrementing i and then you still increment it after to 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 n2 over okay so yeah so that negative one was needed to there that's what happens when i guess you speed through okay that last part i think is is fine uh let's jump into the debrief uh why don't you start by telling me like how you feel right now yeah all right so we're at the debrief section i will let myself continue here it's funny i'm interrupting myself but as you can see there you know we kind of went through it at the end usually what i would do if i had adequate time is before i you know say i feel confident i feel like the solution is good i would do what i just did i would walk through the entire code i would try you know a test example on it and and make sure that it's actually functioning properly obviously in this situation i didn't have enough time where i could actually run through a sample input and make sure my code would perform but that's usually what i always do whenever i finish these coding questions again in this situation i was kind of running low on time so it was a big rush at the end and i can kind of credit some of these you know silly mistakes to the fact that i was rushing anyways i guess i will let myself tell you guys how i felt 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 was a lot of stuff that was just like a lot of details to deal with at once like i kind of confused myself a little bit as i went through the different paths 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 this n squared 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'd done a little bit more prep on something maybe this diff more this difficult i would have been able to come up with 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 i feel like i sort of got it but at the same time it's like not you know 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 would have to you know take a little bit of time to grade you so to speak following the actual criteria 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 based on what i'm seeing the main reason is this first of all this is a very difficult question this is actually a question that we have on our go expert i know for a fact that you didn't do it based on the questions yeah you did do but so this is a very hard question on algoexpert 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 inputs there's a lot of different like types of inputs you saw that they're 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 calendar 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 at the beginning and then i was running low on time and then that was just another piece so we just skipped by but yeah i did kind of think of that exactly but but but even that like it's an additional piece of just 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 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 just the the opposite order of operations but then the coding the coding is difficult yes transcribing 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 overwriting 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 you know seems like it's getting you know it's getting close to working probably there are edge 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 like compare times like this is the kind of thing where a must to do something along these lines is the the the diff between here absolute must you know otherwise like you're going to get a gross algorithm you did 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 all right so i'm gonna cut myself off there i know what happens at the end of this interview it's not too interesting but there you go that's clement's feedback for me i mean do you guys agree do you disagree he's done a bunch of coding interviews with you know like literally hundreds of people at google so i trust his word and this was really great practice for me going into like my microsoft interview and my shopify interview because i did not get questions that were this difficult so like clement said this is a difficult question yes some of you will probably look at this and say oh you know i could answer that this way but i can guarantee you it is a lot more difficult when you're on a google docs you can't see the guy's face because we were on like just a call right have my earbuds in and you're just going and trying to do it in 45 minutes so anyways that has kind of been the mock coding interview looking back at this now i will give kind of a summary of my thoughts i think that generally i did a decent job i stuck with what i always try to do which is explain myself as well as possible and you saw the benefits that i gained from that clement gave me a few hints you know i was able to catch some of the bugs i was able to figure out the flaw in my own thinking simply because i was kind of speaking out loud and i always find it's easier to have someone to kind of rebound ideas off of because then you can very quickly determine based on you know even just little things that they say whether or not you're on the right track or not in terms of things for improvement i think definitely the coding was a little bit sloppy uh looking at it now this wouldn't be the standard that i would hold myself to i've just been coding longer coding more in the industry so i would have liked to see you know some better variables just things a little bit more split up easier to read i would have liked if i'd converted the entire input into numbers first or in two minutes sorry so that i wouldn't have had to use say the compare times thing and deal with strings and all of that but overall decent interview and you know this is really good for me looking back to see kind of how far i've come and how i might approach this problem differently now so anyways i hope you guys enjoyed if you have any questions any comments about this please do leave that down below the original video if you're looking for no cuts or for some reason you want to see it is on clement's channel which i will link down below with that being said if you enjoyed make sure you leave a like subscribe to the channel and of course i will see you guys again in another youtube video [Music] you

Channel: Tech With Tim

Views: 132,019

Keywords: tech with tim, coding interview, google coding interview, coding interview questions, coding interview prep, coding interview tips, how to pass a coding interview, reacting to google coding interview, coding interview example, software engineer interview, google, google coding interview with a college student, google coding interview python, programming interview, programming interview questions, mock coding interview

Id: kbwk1Tw3OhE

Length: 68min 44sec (4124 seconds)

Published: Sat Oct 10 2020