Hi. >> Hello. >> Nice to meet you. I'm going to be your interviewer, okay? >> Sweet. >> Okay, so let's get to the coding question. What I'd like you to do is design a data structure that has three methods, insert, remove, and getrandom. >> Okay, so it has insert, remove, and getrandom. Is it storing any particular kind of data? Objects or? >> You can just assume that they are ints for now. We can generalize that later on. >> Okay, so we have insert, remove, and getrandom? >> Right. >> Okay. So you said they're just storing ints, so can I assume insert just takes an integer. >> Right, that's fine. >> Okay, cool. Remove will take in the int, and then do they return anything? >> What do you think they could return? >> So, actually how are duplicates handled? So if I have this data structure and I insert three twice- >> Hm. >> How is that dealt with? >> Well, for now let's just not worry about it. Let's just assume that all of the input is going to be unique. >> Okay. >> We'll handle that later. >> Okay, so in that case, insert and remove can return a bool. For example, if it's inserting a value that's already in the data structure, maybe it returns false, and likewise with remove. >> Sounds good, but- >> Or something. >> Yeah sure, that's a good way of doing it. Let's make it simple. Let's start simple. Let's just have them be void for now if you want. >> Okay, cool. So for getrandom how exactly is that working? It just returns any element in the data structure? >> Yeah, so from the elements that are currently in the data structure you should return one of them at random, so all of them have equal probability of being chosen. >> Okay, so if there are five elements in my data structure it'll be a 20% chance. >> That's right. That's correct, yeah. >> Okay, all right cool. So getrandom will return sorry, a int. All right, okay, so just to double check that I understand this. Let me go over an example. So, if I have my data structure I'll call it my data structure and I insert let's say, 1 and then 5 and then 10. And then I do remove for let's say, 5. So at this point one and ten would be my data structure. >> That's correct. >> Okay, and then if I call getrandom, There will be a 50% chance that the 1 is returned. >> Yep. >> And a 50% chance that 10 is returned. >> Yep, yep. >> Okay, cool. Okay, so let me think about this. The first thing that comes to mind is just I could use an array list so that way when you insert a value you just add it to the array list. And then for remove you can do arraylist.move remove and for getrandom can I assume I have some kind of random number generator? >> Sure yeah, so you can assume that you have a rand function that has a min and a max and returns uniform values between min and max inclusive. >> Okay, cool so if I have that then I can, if I know the size of my array, which I do I can just essentially get a random index using the bounds of the size. And then just return whatever value's there. So, that's how I would do it with an array list. >> Okay, sounds good, yep. Yeah, so what's a complex way to get that solution? >> Okay, so insert I believe you're just adding it to the end of the array list, so that would be constant. Okay, so removes a little trickier because you have to find the element that you want to remove. So if there are ten elements then it's possible you have to kind of of iterate through every one of those elements to search for the value you want to remove. So that would be linear and getrandom would be constant. Can I assume that the random generator works in constant time. >> Yeah, that's fine. >> Okay, cool so yeah I can get the number in constant time or I can get the index in constant time, we're trying it in constant time, then that would be constant. So yeah, let me erase this. So for this would be o of one, this would be o of n, and that would be o of one. >> Okay. >> But, let me see if I can think of a better way to do this. Let me see. So the problem here is that for remove I have to search for the element that I want to remove. But if I use a hash set to store my values, then I can do the lookup in constant time. So okay, so this is with my list. With my hash set I can just insert the element in constant time, because it's a hash set. I can remove it in constant time, and getrandom is going to be a little trickier because I can still get a random index, but a hash set isn't indexed. It's not in any particular sort of order so, I guess what I would have to do for that is if I want to get the third element I would kind of have to just iterate it through it three times. >> Okay. >> So that would be be linear then. >> Okay. >> So basically what you have right now is one solution in which you have insert and getrandom to be very fast, and remove it's a bit slower. And the other one in which insert or remove are fast, but getrandom then becomes the slower one, right? So can you do better? Can you do better sort of in the worst case getting better than linear time? So you're right, the problem with remove was that I had to find the element that I wanted to remove. And the problem with getrandom is that with the map I can't randomly retrieve the element with a given index. So, let me think. I'm trying to think if there's another data structure that would be better than both of those. Let's see, so. I need a data structure where I could still look up the value to remove if faster than linear time. So, I guess the array list, something like a list or a like link list wouldn't work for that. But I still need to be able to access a random element in a faster time, so I need something that's kind of like sorted at least. Not necessarily sorted but at least in some kind of order where I can like access it more quickly. >> Okay, so let me just recap. You have two solutions, right? >> Mm-hm. >> You have one in which, Get-Random, it's really fast. Because you're getting index, right? And then another which you can remove very fast because you have a hash. So can you think of a way to combine those two perhaps, to sort of get the best of both worlds? >> Okay, yeah. What if. Okay, What if I still kept my elements in the array list, but I use the set to track the index use of the values? So, if I add some element to my array list, into like a fifth index, I can kind of keep track of that index that I've added it to. And that way, when I need to remove it, I can just kind of look up where it's located, and I can remove it in constant time. And I still have all the values in my list, so then Get-Random should still work in constant time. >> Okay, sounds good. Let's see some code for that then. >> Okay, cool. I'll just erase this. Okay, so this is my class. Call it my data. Actually so, I guess for this I will need a hash remath instead of the hash set, because I guess the idea is that I want to, not the value to be indexed where it's stored. >> Cool. >> So, I'm actually going to go over an example. So if I insert 5, and 10, and 15, then what I'll do is when I insert 5, I have my map. And it will map 5 to index 0. >> Okay >> And then when I insert 10, it'll map 10 to index 1. And then when I insert 15, it'll map 15 to index 2. And then if I do something like remove Ten. Then I know that my element, the 10 is stored at index 1. >> Okay. >> And I just remove that value index 1. So yeah, that should be pretty straightforward to do. Okay, so let me code this up. So, I have this global variables. I'll have my hash map and my hash set. Okay. That's my map, and then I also need my array list. Okay, so I have my map and my list. So, I'll write the Insert. So for insert, I said, it just adds the element to the end of the array list, and then, I need to update the location in the hash file. Can I assume I have, there's an insert? >> Yeah, sure, whatever. >> Okay. >> Yeah, that's fine. So this point, let's say I insert 1 and then 5. We insert the 1 at the end of the list. And then we put the 1 will map to the size, which at that point is 1, actually. So, I'm going to subtract. So, the 1 will map to the size, which is 1, minus 1, which is 0. So, the value of 1 will map to index 0. And then if I answered 5, 5 will map to index 1. >> Just a quick question. Do you want those to be private? >> Good point. >> Cool. So for a move like, I said, I know where the value is located in the array list. So, I can just remove it from that index. And then I would also need to update the location in the hash map, essentially just remove that key from the hash map. So, first I'll check that the value is in the hash map. >> Okay. I'm pretty sure that array list has a way to remove that. [CROSSTALK] >> Yeah, that's fine. Actually now that I think about this, using RemoveAt is a little problematic because if I remove an element kind of in the middle of the list All the elements to the right would have to be shifted over, and that would actually take linear time, because they kind of all have to be copied over. So, Let me see. Is there a way to? I trying think if there's a way to remove the element still in constant time because, I guess I don't actually care about the ordering, so. What. >> So, yeah. When it's removed from an array list constant. >> When it's at the end, it would be constant. >> Right. >> So what I could do, actually, is swap the value that I'm removing with the value at the end of the list. That way, I can just remove from the end in constant time. So for example, if I'm removing the value in the index five, and there are ten values total. I just swap the value at index five with the value at the last index. And then I just remove, take off the last expense >> It sounds good. >> Okay, so let me rewrite this. So. Can I assume there's like a swap function? >> Yeah, don't worry about it. >> Yeah, you kind of assume that you have a swap function, that's fine. >> Okay, sweet. So this will just swap the index. Where this value is stored and then the index of the last element. >> Right that's fine. >> Okay, so, once I remove the element from the list. I just remove it, kick it out from the map as well. Okay, and for GetRandom, that should be pretty straightforward like I said. I just calculate the random index, so actually, is it okay if I erase this and put a big GetRandom? >> Yeah, that's fine. So, random takes in the range of zero and the size minus one, and it just returns the value of that range randomly, and then that's what we'll return from the list. >> Okay. >> Okay, so that's remove. So let me kind of go over an example just to double check that this is working. >> Sounds good. >> So >> Let's say that I insert 1, 5, and 10. So as I add one, I will update the hashmap with the location. So 1 will point to 0. And then 5 will point to 1, and then 10 will point to 2. And then if I remove 5, then I check to see if the map contains 5. It does, it's here. I swap 5 I swapped the index where 5 is at with the last index. So then the 5 gets swapped. And then I remove the value at the very end which is the 5. And then I kick out the 5 from my map. Okay, so actually a problem that I'm seeing here is that I'm not updating the location of the 10. So I need to do that as well. So what I can do is after the swap, I can just update the location. So actually, is it okay if I kind of just write something off to the side? >> Yeah, it's okay. >> All right. So over here, we just do map.put. So it would be whatever value is at the end so this is where I swapped it. This will be the list.git. Index. Okay, sorry. This will be, so I will swap it and then I'll put the value with the new index I swapped it. So, actually if I get this story, this value ahead of time, And then whatever value's at that index now. And with the actual index. Okay, so, sorry it's kind of messy, but basically- >> I can see what you're doing, yeah. >> After we do the swap, I update whatever values at that index I just swapped to, or swapped from, with the actual that index. So now the term will get updated with the one. >> Okay. >> Okay, that's remove and then get random at this point there's two elements so we're getting a random value between 0 and size two minus one which is one. So a random number between 0 and 1 which is what we want so there's a 50% chance that thess getting selected. >> Right sounds good yeah so how would you make sure that this is correct? >> I guess there are a few different ways to test it. You can, so you pointed out that we don't have to worry about duplicates. But, we can test this with negative numbers, which should be fine. We can see what happens when you remove a value that you haven't put in there in the first place. You can insert a value or remove it, and then insert it again to make sure there aren't any weird side effects of that. Yeah, stuff like that. >> Yeah, sounds good. So, we were talking about the return value of, for instance, remove and I told you not to worry about it but, so. How would you, for instance, return whether the value was found or not, in this case? >> It'd be pretty straightforward. Here, I'd check to see if the map contains value, so if the map doesn't contain the value, I can just return false, otherwise, here return true at the end. >> Okay, cool. Now for more interesting part, which is what happens if you actually have repeated numbers? How would you handle duplication? >> So, that would be a bit trickier, because the concept here is that I am having this map where I map each value to the index where it's stored. But you have duplicates, so if I have ten in here twice, then that value ten, I guess conceptually now maps to two indices, right. At index one and index two. So what I could do is, instead of having it map from integer to index, I could have it map from the integer, the value, to a set of indexes. So instead of this being integer, it gets to be a set. And then that way when I want to remove a value, I can just kind of choose any one of the, those indexes in the set. >> Yep, sounds good. Yeah, and. So also, how would you allow for this to store arbitrary data, rather than just integers? >> So like an object or something? >> Yeah, sure. >> So, it would be fine. I don't think much would need to change. But as long as that value can be included in a HashMap, so as long as it's hashable, and yeah, I think that's about it. As long as it can be in the hash site, and as long as I can do hashtag functions, it should be fine. >> Okay, just quickly then, the complexity of this solution as it is? >> So, GetRandom will be constant time. >> Remove the swap will be constant, and removing from the end will be constant, and then updating the mappings will be constant. So removal will be constant time, and then insert should also be constant, because you're just updating the mapping and adding to the list. >> Cool, sounds good. Yeah, okay. Yeah, thank you very much. We're almost out of time, but I want to give you a chance in the next couple of minutes to ask any questions, if you have any for me. >> Yeah, one question I have is, what's it like being an engineer here? >> Yeah, it's really very nice. We have a bunch of perks, of course, that you know about probably.
