Design HashSet | Leet code 705 | Theory explained + Python code | August Leet code challenge

[Music] hey guys welcome back to another video and today we're going to be solving the lead code question design hash set okay so in this question we will uh design a hash set without using any in-built hash table libraries and to be specific your design should include the these functions so we must have a function which adds a value to our hash set uh one function which checks whether that value exists or not and a function which removes whatever value we give it so i'm going to start off by going over the very basics so let's start off with what even is the hash set and why would you want to use one so what exactly is a hash set and pretty simply put it's a data it's a set based data structure which stores value but you might be asking well that just sounds like a list or a set what's different now what's different about a hash set is the lookup time so the time it takes to find a certain element is constant time so it's big o of one so let's say we were to look at a a list we would have a lookup time of big go n but this does it in big go of one constant time which is really fast so this is how this is why we need a hash set and this is kind of what it is now how does it actually have such a fast look up time and it's important to understand this in order to create our hash set so this uses something called hashing so let me just write it down so hashing and all hashing is is think of it as some sort of function which takes in a value and gives you a value for that to explain this let's just create our own uh imaginary hash set so i'm gonna make a hash set and it's gonna have a length of five so it's gonna have none so five nuns basically actually uh what i'm going to do is i'm just going to define each noun as a n so n stands for none one two three four and five so we have five nuns and that's our hash set which is currently empty so now let's look at our first function called adding let's say i want to add the number 2. so the number i want to add is 2. how can i add 2 to our hash set i could just put it in the first index and say i'm done but we need a constant lookup time of big o one so in order to do that we're going to run this through this whatever number it is through our hashing function now in real world um in the real world we have different types of hashing functions but for the purpose of this question let's just look at a really basic one so what we're gonna do is we're gonna take whatever number we have so in this case we have the number two so we're gonna take two and we're gonna perform the modulo operation with the length of whatever our hash set is so the length of our hash set is five so we're gonna do two mod five and we're gonna get a value so in this case we're going to get a value of 2. so what does this value mean so what this value means is what it's telling us is go to the second index so we're going to go to the second index so 0 1 2. so this is our second index over here and in the second index we're going to add the number 2. so over here we're going to add the number 2. let's just take another example let's say we want to add the number 3. so we're going to do 3 mod five and that equals to three so we're gonna go to the third index which is over here and we're gonna add the number three okay but now the question you might be asking is what if you have some overlapping what do i mean by that so what i mean is let's take the number seven so we have seven we're gonna put it inside our hashing function so we're gonna do seven mod five right pretty simple and now what is that going to equal to that equals 2 but we already have something at 2 we already have the number 2 over there so we go to second index there's already something so what's going to happen is we're going to append whatever value we have here to that list so instead of this list just having the value of two it's gonna have two comma we're gonna append seven two comma seven and that is what we specifically uh that's called a bucket so it holds a set of values and technically let's say you have a really hash a small hash set and you have a ton of data you want to give it to you're going to have a lot of these buckets and the more buckets you have in general it's going to slow down your lookup speed so you're going to get farther away from constant space so in general lesser the buckets the better but i don't think that matters too much for what we're doing over here so let's just focus on this okay so we have two comma seven so that's how we would normally add our uh numbers or our whatever data we have okay now let's see how can we look up stuff so just for an example let's say we have the number seven so i want to find the number seven and we know that the number seven exists but let's see how we can come to that conclusion methodically so our first step like usual we take whatever number we're looking for take that and put it into our hashing function and that function is the same which is 7 mod 5 the same function and we get a value of 2 again so this tells us go to the second index and you might find seven there now when we go to second index we get a list right and what we're going to do is we're going to iterate through our list and look for seven so is so first the first element is that equal to seven no two is not equal to seven so now we go to the next element which is seven and we found the value seven and we're going to return true saying that yes we found it and it does exist now let's just look for a number which does not exist so for an example let's take the number 1000 and let's do the same steps before so take that number put it into our hashing function so same function 1000 divide mod 5 which equals to zero so this says go to the zero with index so here we're at the zeroth index and if you look at the zeroth index there's nothing over there so in that case we know it's false and the other case we might have so let's just say for an example this has the value of 10. so i would go over here i would go to the list look at each element in the list and in that case also we're not we're gonna we're not gonna find the value thousand so we're also gonna return false so this is for looking up and the next and last one we have is removing so i don't wanna go over each and every step for removing but all it is is we're going to take we're going to use the same thing for looking up so the first step for removing is to look up so we're first going to look for our value and once we find it we're going to remove all of its instances so let's say we go to the number seven so we're going to run it through our function we're going to know that it's at the second index we go to the second index and we're going to go inside of this and we're going to remove the number 7 until that number doesn't exist so we're going to remove this number over here 7 doesn't exist anymore and then we're good so that's how the remove function is going to work and uh i'm pretty sure so once you understand how the theory of it works i think it's really easy to implement it in code so let's just see how we can do that in python this over here is the kind of template that we were given to work around with and my first step is going to be to initialize a variable called size which is going to be the size of our hash set and i chose the size to be 10 000. so you might be asking why so this is the range of values we're given and i thought 10 000 is a good number because uh we're it's going to be big enough that we don't have too many buckets right but there's two sides of this the other side is what if we're only given a few values and in that case there's just a lot of memory which is being wasted so in order to solve this uh people come up with a way where you dynamically change the size depending on how many inputs you're giving it so for this question what i want to do is i just want to keep it a little bit simple so i'm not going to be doing all of that okay so we have a constant size of 10 000. so now i'm going to make our hash set i'm just going to call it table and all that is it's going to be none like we saw earlier repeat it for how many other times this is so multiplied so this is going to have a length of 10 000 in this case so now like we were talking about earlier we always had a function that we would go back to so i want to make that function over here so calculate i'm going to call this function calculate hash value so in python there are in both ways to do this but like the question said that we're gonna not do use any of them so over here is gonna take the key as an argument and all we're doing is we're gonna return the value of the key mod self.size so the key modded by the size same thing as before so the first step for our add function remove function and the contain function is going to find the hash value of the given key so i'm just going to do that by doing so i'll just first do that so over here and over here okay so hash value hv is so we're gonna call our calculate hash value function so calculate and over here we're going to give it the argument of the key right so we're just going to call the key and so in all of these three cases we're first finding the hash value so let's just do the add function first so what we're going to do is once we find the hash value we're going to go to that index so self.table and we're going to go to our hash value okay so now we have two cases so if our hash value is equal to none actually let's just look at that first so if our hash value is equal to none we're just going to add the key as a list so self.table hv is equal to key as a list okay else so in this case uh our that value is not equal to none so that means that we already have a value in there so we already have a bucket and all we're doing is we're going to append this key to that bucket so what we're going to do is we're going to do self.table we're going to go to that index and then we're going to append our key since there's already an existing bucket so that's all it is for our add function so now let's move on to remove so we found the hash value first thing and now we're going to do the same thing so first we're going to see if whatever is at that index the self.table hv is not equal to none because if it is equal to none then there's nothing to remove that thing doesn't even exist so if it's not equal to none then in that case we're going to do whatever so we're going to go inside of a while loop so all this while loop does this so it's going to see so while key in self.table add the index of hue self.table remove self dot self.table hv dot remove key okay so what is this doing so why are we going inside of a while statement instead of just calling this function as it is so the reason we're doing this is when you call remove all it does it removes the first instance of that value or element so let's say we have a bucket which consists of one two three and two right and we want to remove the number two if we only call the remove method it would have just removed the number two and we would be left with one three and two but in this case we wanna remove all instances of two so we're gonna go into a while loop and we're gonna stay in that while loop until two doesn't exist so first we're gonna remove the first two then we're gonna remove the second two and then we're gonna be done with our function so that should be it for our remove function method and now let's go to contains so what contains does is it looks for a value if that value exists it's going to say true or else it's going to say false okay so pretty simple and as usual first thing we found our hash value so if self.table we're going to go to the index of the hash value and we need to check if that's equal to none so when you see if it's not equal to none because if it is equal to none that means our answer is false so we're going to only check if it's not equal to none and we're going to see if the key exists in that list so if key in self.table at the index of hv so if that exists we're going to return a true and if it doesn't exist we're going to return false so instead of writing it like this we can just simplify and write it return key and self.tablehv so if the key exists it's going to return true if it does not exist it's going to return false and if none of these cases are true so if the key does not exist or if the or if or if that element is equal to none in either of those cases we're going to return false so we have returned false and this should be our answer if you want to go over the code i'll put the code in the description below and i'm going to submit this and as you can see our submission got accepted and finally do let me know if you have any questions regarding this or if you want me to do any lead code questions and thanks a lot for watching guys and do let me know what you thought about the video thank you

Channel: Sai Anish Malla

Views: 1,505

Rating: 4.8153844 out of 5

Keywords: leetcode, leet code, leet code 705, leet code Design HashSet, Design HashSet, Design HashSet question, august challenge leetcode day 2, august challenge leet code, python, interview questions explained, leetcode explained, leet code question explained, easy to understand, python for beginners, interview question explained, python leetcode, python interview quesion, beginner friendly, explained, fully explained, hash sets, hashsets, building hash set, hashsets python, python3

Id: w9JhOKb4tyk

Length: 14min 59sec (899 seconds)

Published: Sun Aug 02 2020