Mock Google Coding Interview with a Meta Intern

bro yeah but don't worry this is gonna be fun for one of us for me can you like call me calm me down before we start I'm nervous I haven't coded in a in a loan it's ever since I failed my last Citadel interview all right bro if I fail tomorrow I will be calling you okay pause this is frying pan he's a college student who recently finished an internship at meta and today we are doing a mock Google coding interview the day after we conducted this he actually had an interview at Bloomberg for a new grad position but if you're new to the channel I'm neat code I started working at Google as a software engineer about a year ago my channel is all about helping people prepare for coding interviews by the way if you're preparing for coding interviews definitely check out neatco.io it's a site that I created to help you Ace your next coding interview we also have courses for algorithms and system design and actually the question I'll be asking frying pan is from this list anyways moving on with this mock interview I'm trying to emulate how a real Google coding interview goes so this is meant to be as realistic as possible I'm gonna give pan a data structures and algorithms related question and I'm gonna expect him to solve it it's okay if I have to give him some hints but he should be able to solve most of the problem by himself if he wants to get a higher rating and either after he finishes coding or we run out of time I'm going to do the debrief which is basically tell him how he did what he could have done better I'm going to give him realistic feedback on how he can improve for next time and I'm also going to give a binary decision on whether I would hire him or not hire him so without further Ado let's get started okay so I'm gonna start the timer right now okay okay so this is a question I want you to design a class that supports these three operations so the first operation is inserting a value and you can assume that there's no duplicates allowed so you might be given a duplicate but you don't want to actually store the duplicate the second thing is removing a value from this class and where it gets interesting is I want you to be able to get a random value that is already inserted and among the values that are inserted I want it to be of equal probability so just these three operations okay okay um all right so let me just repeat the question back to you to make sure I understood it from what I understand I have to create a class that essentially has three functions one is to insert an element second one is to remove an element and the third one is to get a random value that is currently in the class is that correct yep that's exactly right nice are these values like integers or strings or like animals like are they specific something yeah you can assume that they're integers okay all right great so then let me ask you this question are there gonna be a lot of elements we're inserting or um is it just gonna be a certain amount uh you can assume that it's like a reasonable amount like less maybe like in the terms of millions but it's you shouldn't run into like any limitations like with memory or anything like that okay so let me ask you another question is there going to be more insertions done or more removals done or more get randoms done uh you can assume that they'll be like of equal quantity like equal proportion okay thank you very much I'm gonna ask you one final question before I start coding Can I code in Python sure okay here we go so the first thing I'm gonna do is create a class wow there's Auto capitalization in this Google doc I don't know why you guys perform your interviews in Google Docs I think it's very stupid but all right so class um um okay so let's just call this a store class store and we're going to start with the Constructor is there a way to turn off this Auto capitalization sir this is really annoying yeah you can just pretend like we can ignore the capitalization you can just assume hey try to ignore it I'm just gonna say it's not very inclusive of you because I have OCD and this is pissing me off all right so uh Constructor in it and this will be the Constructor so here we go what is what are the variables we need here right we are inserting values and removing values so we need a data structure to store these things so let's think about what we actually can use for this we can either use an array so if we use an array um inserting removing will be um okay so it will have to it will be all of one on average but um since we're inserting a lot of elements um okay I will have to keep growing in size and it might be useful for the get random since we have an index okay let me just think about this for uh five seconds yeah okay so if we use an array to insert these values and we don't want duplicates so let's say we just use an array and we insert values um removing a value would be all of n since we have to find the actual value so let's say we use a hash map to insert these values we can make sure that there are no duplicates and we can make sure that inserting and removing is on average um very fast of one no that sounds good to me okay the third thing we have to consider is we need to get a random value out of everything that is inserted um how to get a random value with equal probability yeah when it comes to getting random I'll actually help you out here and just let you know that you can assume that there is a method let's call it random dot choice I think in Python and it takes some list of values and it'll return you a random number with equal probability from that list I actually already knew that but thank you very much for the reminder so let me just start by initializing a hash map equals to inserting values uh okay this so the next function will be insert def uh insert and for the parameter it will just be a value right we're passing one value to this function Okay so let's see um I think we can just insert it directly like this um value inside of it I think this can actually just be a set um since starting a value removing okay so there's nothing um for the input is it just one value or is this uh something else during the insertion yeah you can just assume that it's an integer okay okay then I think what we can just do is add this value to the set and okay and then for the remove and just remove value from that move a value so these will be a very quick operation no duplicates I think this is fine since it's set so if there's already one it will just replace it or not put it in um and then for the get random uh get a value that is already okay so if there's a function that you can just get something from a list randomly I guess the easiest way is to just convert this set into a list and use this function on it okay so we can just do return um yeah return um random.choice list self done and yeah let me put this uh here since these are class function hey um so we can also also add some checks for uh this set like to see if it's like empty or not before removing um or to see if this map exists but I think that's fine since by initializing this class uh this map will exist so yeah this will be o of one insertion of one remove and um this will be of n for the get random and yeah [Music] yeah that's correct so this definitely works is it possible to get the get random function to be a bit more efficient okay so uh this random.choice is or then correct like it has to iterate through the entire list to uh give an answer yeah well let's assume that the random is actually constant time so where your function is becoming a linear time is converting the entire set to a list I see I see okay okay all right hmm okay so let me think about this um since the conversion is it cannot be avoided if we use a set I'm assuming uh for this to store these values we probably have to use an array so um the problem with using an array is the removal will be uh not efficient anymore is that an issue or do we want all these functions to be of one is that what we want yeah that's a good point because if we do it the way you kind of proposed we can get the get random to be more efficient but remove will then be linear time so we don't really improve anything assuming that each of these is called like an equal amount of times which you clarified so yeah you're on the right track I is it possible that we can get all three of these to be constant time okay let's see um okay so I think we probably have to use a combination of uh data structure here so let's say we have an array where we store these values and um yeah we insert and we remove values from there um so let's say we have a hash map that stores the index of each value then um when we remove we can just remove it from the hash map and take a note there and then we know that it's not in the array anymore even though it's like technically still there um then we can fix the problem of removal being slower so then removal and insertion will will both be on average of one but then for the get random there will be there will be integers in the list that are not supposed to be in there okay so um how do we make sure that those integers are not taken into account um okay what if every time we have a value we want to remove and we know where it is in the array right so let's say we switch the place of this element to the beginning of the array and or to the first element that is still supposed to be inside this array so then we can essentially segregate segregate separate all the values that are technically not supposed to be in the array and all the values that are supposed to be in the in the array so once we have all of this separated um what can we do then okay so I'm thinking if we have all of this separated right we know where the separation is we can probably know um the last element that is not supposed to be in this array from there until the end oh oh yes so we can do from there till the end uh use the random choice on on those but then we still have to slice the array so that's still kind of O of n it's like a bit better um does that make sense yeah I think you're definitely on the right track uh I guess I have a question so you said earlier that the problem is we can't remove a value from an array in constant time right yeah why is that the case because uh it could be in but on average will now be constant time since if it's in the middle of the array we have to move all the elements at the end um and like push them back yeah that's true is there any case where we're moving from an array actually is constant time oh if it's at the end of the array it'll be constant so if that's the case wait what does that tell me okay so if okay so if we do that and at every time we remove something um we switch it with the end of the array and then we remove it that will be all of one and then we can just use the random.choice on the original list because they won't have all the values okay I will start coding now okay sounds good okay okay all right so uh okay so the first thing is we'll initialize a array self Dot um we'll call this value okay we'll call this values and it's going to be an array and we're also going to use a hash map to store the index of each value where each value is okay so now for let's let's go for insertion how will insertion work here so I think the first thing we need to do is check if it's already in there so if the value that we want to insert is in self.map then we want to return since we don't want any duplicates right so um is this the correct Behavior we want so if there's a duplicate we just do not insert the new value yeah that works yeah so once we have this [Music] um um I think we can just perform the insertion so self dot uh values we can we can put append value now how do we know what Index this is because we have to put this in a map um so the value of this will be equal to the index so this index will be I think the length of this array since it's the last element so length of self.values minus one perfect I think this is correct for now value in self-dot map if it's already in there we return otherwise we append it to the values array and we store at what Index this value is okay mm-hmm okay so now let's go to the remove function the remove function um we first want to check if it's in the map at all right so if value is in self.map then um well if it's if it's not in the self.map we can simply return okay now if it is if it is in that means it's um it's an accurate value that's also in the array okay and then we want to remove that so um we can find at which Index this value is by using the map so self.value uh self.map value to get the index of where this value is inside of the actual array and then uh here is where we need to perform the swapping okay okay um okay so let me think about this how do we perform the swap hmm okay so I think we just remove it to the last element um and to do this we can simply um do um the last let's save the last element so um last value is going to equal to self dot values minus one and then um we can put this new value at that place self.values um value equals to um values minus one okay and we want to put this one back so self.map um last value is going to equal to index oh okay let me just make sure the swapping makes sense so I'm getting the last element from this array saving it and then replacing um and then adding this new value I need to add it to the last the last index so I'm adding this new wait a second value okay so now I'm adding this new value or no we're removing this value so yeah I'm I'm adding a value that I want to remove to the last index of the values and then I'm putting the previous last value at um the index of the other element I'm trying to remove okay and then at the very end of this we can then remove um said value we want to remove and so I think we can use delete how to remove an element from I guess we can just use I don't know if delete is the correct keyword but I'll just set it to uh none for now yeah I think delete is fine delete is fine okay delete self.values minus one oh I delete the last value from the array okay and inside of the get random function we can just simply do a random choice self dot values does this make sense yeah this makes sense so a quick correction actually I said it was delete but I thought uh we were talking about the hash map but for the list itself uh you can just use pop okay yeah great oh you true yeah okay and um okay so I'm missing something here is we need to also update the map um so in order to update the map we're gonna do uh Delete self.n map and uh value and this deletes it from the map okay so let me just make sure in the insertion we're appending to the values and we're also updating the map and in the remove we're also updating the values array and also updating the map um perform the swapping oh uh do you want to walk through a couple like test cases yeah for sure okay um okay so let's say we insert um um three uh four five five okay let's just say we insert three four four and then uh we want to remove three and that's it we answer also five and then we remove three and then we uh get random okay so then obviously we we first we initialize the class and then um let me write down self.values this self.net okay so to keep track of the values first we insert three now and in the insertion a value in self-map it's not in the map it's going to append to the values array so we have three and then it's going to put it in the map so in the map we're going to have a three with indexed index 0. okay after this we're going to insert four insert four again or actually the first four um it's going to be the same thing so append value four to the value array and put it in the map so four with index length of self dot values it's two minus one is one so here we go then we insert four again it's already in it we just return then we insert uh five so same thing it's going to append five to this and um self-taught five is going to be two value of two okay and at this point we want to delete three right so going into the remove um function we can see that three is inside of it so now we get the index of three which is x equals to zero and then the last value is equal to five go to five and self-doubt values minus 1 is going to equal to the value so here we're going to update 5 to um value we want to delete which is three and then um self.map last value equals to um whoa hold on um equals value okay so I think I'm missing something here so we need to also re-put the first element that we deleted back inside so self.values at index is going to equal to um last value right so um this index is zero I'm going to replace three with uh five which is the last values value okay okay at this point um we're updating the map so self.map last value which is five we're updating the index back to zero and then uh we pop from the last uh array so it's only five four now and we also delete uh three from the map okay and at this point uh we get the we get something random and it's going to get something random from five or four there we go yeah perfect we got it yeah that was a good catch let's go so I have a question a couple of questions so with this remove yeah actually uh no I mean it looks good I guess I my other question is so this solution works perfectly if we don't allow any duplicates but what would happen if we did allow duplicates like we could have multiple threes multiple fours and in that case uh the probability would still be the same actually like we would still want the you know the random to be proportional to how many times each value has been inserted so we don't have to change the get random but how would you change the rest of this code to allow for duplicate values okay so in that if if that's a scenario that means uh the four here that we Implement so there's going to be two fours um in the array correct in this example I have down here yep okay so that wouldn't work with the current one because uh in the hash map I can only have I cannot have duplicates so in this case I think uh what comes to mind is instead of uh associating each value with just one value one index I can put an array here and um instead of counting okay so if I use an array I can store multiple indices so if I have a four I have I can have a four at index one I can have a four at another index and by having that um yeah then we just have to uh update the so in that case the remove can just uh Delete any of these fours right it can be the first four four or the second four the third four it doesn't really matter and I think that's that's pretty much it I can just replace the one with an array to uh keep track of the duplicates so and that's exactly correct yeah so and yeah yeah in the insertion I would obviously check if it's already in the self map I would append to the array um does that make sense oh that sounds good hey no we can code that up oh okay we code that up all right I thought we're just talking all right all right so if that's the case um in the insertion we're gonna start here if value is in self map uh return so obviously we're gonna change this um [Music] okay so instead of using a um initializing like this here I'm going to use collections not default thick uh and I'm gonna put a list in here so I can just append directly to an empty list for every value so if the value is already in the self map um I'm just going to do self self map value dot append uh uh length of self dot value uh uh minus one and also obviously appendix to the values array boom okay and although okay so maybe this is the only thing self.mapt.values um okay so actually we don't even need this um we can just do this so we're just going to directly um append it to a value in the map if it doesn't exist it's going to be an empty list and this is going to be the first element associated with it if it does exist well it was it's going to be the same thing and append it to the value array okay this is this works for the insert now for the removal if the value is not in self map um return that's that's fine uh we have to change something regarding this swapping because now what we're returning is um an array and delftmap.value okay so we're just going to return the first index to and we're going to delete this first index so the index is going to be um the first index of this value whether it's duplicate or not okay so then um this is fine it will all work we just have to change the the map so the map last value equals index we're going to do append instead of equal um yeah okay and cell values.pop delete self okay so in the delete here we have to change it so self dot map um value this is going to be an array we don't want to delete this entire array so what we need to do is delete the specific index inside of this array and something we can do to make this better is use a set instead of a list so I'll just use a set here um and we're going to since order the order doesn't matter here I'll just use a set and it'll be faster for insertion and deletes so self dot values append so we're going to do add and here we're going to add and self.map Dot value we're going to remove this index move index okay um okay all right so I think this works uh do you want me to run this through an example again uh sure yeah let's go ahead and do the same example that yeah perfect okay all right so let's start over so self-doubt values uh we do an insertion we're going to go quicker here um we add um uh into the map first so the map will have value three with a set of um it'll be zero or it's index and then in the values array we're going to just append three so no problem and then we're going to do it the same for four so four is going to be like this and then after this uh we're gonna add another four so um it's gonna go self.map value add to this so 4 is going to add um two here okay actually I have to do this append before adding it so that the length is accurate okay so now that we have uh everything in the values array and the map um yeah we have the duplicates and then we add five uh five is going to be here and um five is gonna okay all right perfect and okay instead of the the leading three we're going to delete four here to see how it works for because the deleting three will be I think pretty trivial so deleting four will be the one that has two that has a duplicate um okay so if value is not in southern it is in so index is equal to self.map uh value zero okay so zero here um I cannot use zero here how to get the first element hmm how do I get one element out of a set um yeah maybe I do need to use a list I think we can just assume that there is a way to remove it because I think otherwise I got it I got it sir I got it we can use dot iterator parentheses dot next to get the first element of the set now yeah that's great yes bet you didn't know that now we're gonna do swapping okay so uh index is gonna equal to the first element which is one um last underscore value is going to be equal to the last value of this array which is five at this point we're gonna do self.value index which is one equals to last value so self dot values index is uh the first four is going to equal to five boom and then self.map last value um last value is five so this one we're going to add this index uh-huh where we have to add one here but we need to delete the previous one so we also need to do self of self.map last value remove um um remove the last length of self.values minus one so yeah so this is three so we remove three okay and then uh we pop from the value so we pop wait wait self.values index which is three okay I don't think I did this line so self.values index which with indexes three is one wait okay uh I think there's a problem here so index here is one self.values last element is value okay okay I forgot to do this so 5 is going to be equal to four here at the at the end so then when once we pop we're gonna pop four from this and then we're gonna remove um this value which is four we removed we're going to remove the index the index which was one here so we're going to remove one from this and we're done please tell me there's no more follow-ups uh we have like four minutes left but I think this code looks good yes uh do you have anything else you wanted to change [ __ ] no no I'm kidding but I think let me add another follow-up let me ask you a question is this code thread safe uh probably not correct in order to make this code thread safe we need to add locks for the insert and the remove and the get random and that will be all thank you very much did I get the job yeah so we finished with four minutes remaining so yeah let's do the debrief now okay uh I wasn't taking notes actually usually in like a real interview your interviewer will take notes so first like I gave Pan the question it was really open-ended I just said like insert a value remove a value and get a random value and he clarified that these are like what are we inserting and I said numbers like integers specifically that was good by him I think he could have done a little bit uh I forgot what exactly his clarifying questions were I think it could have been like slightly better uh talking about like the edge cases of like what if we don't have any values that we can remove well he handled that in his code but what about if we don't have any values that we can get a random value from uh the way we coded it we assumed that there's always going to be some values inserted which is the case but true that was more of like an assumption that he made but he didn't like like specifically clarify that but I think it worked out uh as he was coding he when he finished he talked about like the time complexity and you know without without being prompted to like before he even coded he was talking about ways to make it more efficient I think that's good because you could easily go down like the wrong track with these problems and if you go too deep without asking any clarifying questions you might have to like restart your entire solution which will waste a lot of time he didn't have to do that because well like this problem you either use a list or a hash map so you can't really mess up but you know it could happen with other problems so running through like the test case he did really good I think on just like keeping track of everything just like explicitly writing it down when I say like do a test case like in real interviews people will actually mess it up a lot like sometimes people won't write any notes like as they're running through a test case and like they just lose track of what they're doing and sometimes I'll even lose track like I don't even know what they're like saying anymore so I think pan did a good job of like making it pretty obvious to me what he was thinking about the entire time like what was going well and like what the time complexity was what data structures he was planning on using like just everything so overall and like you got the correct solution for the first question and the follow-up I guess you needed like a few hints but the fact that like the solution is correct I'll give like a binary decision of whether I would like lean towards no higher or higher and I would say for this problem I would definitely give you a higher let's go we passed I guess Citadel thought otherwise wow you had to add in there what the [ __ ] I'm sorry what the [ __ ] okay I have a question for you I have a question for you in your real interviews do you talk the same way [Music] no of course not bro I wait what's wrong with how I talked yeah I mean like nothing nothing it was good no it's my turn to interview you Nicole I have a hard DP question for you okay let's go that's gonna be on next time it's coin change all right that would be next time or you should stream and we can stream together yeah this was fun honestly just like reading chat at the same time I was just reading chat like during the entire interview and I would like glance over and just see if you had anyone

Channel: NeetCode

Views: 785,886

Keywords:

Id: 46dZH7LDbf8

Length: 47min 3sec (2823 seconds)

Published: Tue Nov 15 2022