Data Structures & Algorithms #1 - What Are Data Structures?

Key Takeaways

hey YouTube just in case you're new here my name is YK and I was formerly a software developer at Google and now I work on this YouTube channel full time and welcome to my data structures and algorithms series number one what are data structures so a one sentence description of what data structures are would be that there are basically different ways of storing data on your computer and this sentence might not be too clear right now so let me give you a more concrete example here let's say you want to make a system that's sort of like Google Maps for your neighborhood now let's say your neighborhood looks like this so your home is here and there's a store here and another store here and so on and there are some streets too so these arrows show that these are one-way streets there are a lot of one-way streets here and so for example you can go from store to store B but not the other way around and all the other lines here there are not arrows show that they are two-way streets and let's say that you already have each place is coordinates there are latitudes and longitudes stored on your computer like this as you can see from this table you can tell that the latitude of home is forty-nine point two and the longitude of home is minus one hundred twenty three point four and so on now from this table like information you can tell where each location is exactly where each point is exactly but you can't tell how these locations are connected with streets and where the streets are exactly so you need to figure a way to store that information somehow on your computer and there are actually a few different options for this one of those options will be to store all possible paths in a list like format so for example one of those paths will be from store a to home and another one will be home to store a and yet another path will be store a to store B and with that method your data might look like this and from this list like information you can tell that as we saw earlier you can go from home to store a and from store a to home and home to store B and so on but you can't go from store B to home because this is a one-way street and so there's no path from store B to home in this list okay so that's just one option another option might be to list each of these places and for each of those places just list all the places you can go from that place and with that method your data might look like this instead as you can see here we have table like information again where on the left hand side we have all the places listed home store a store B school and then intersection this one right here and on the right hand side for each of those places we have all the places you can go from there so from home you can go to store a store B and intersection as you can see here and from store a you can go to home or store B so these two methods are basically two different ways of storing exactly the same set of data and as you can see they have sort of different structures and so these are simplified examples of what data structures look like now if you're already familiar with data structures you might notice that the first method corresponds to the array or a list data structure and the second method corresponds to the hash table or hash map data structure okay so that's one simple example of what data structures are but this video series is called data structures and algorithms so what are algorithms one way to define what they are would be that there are the operations we can perform on different data structures and the sets of instructions for executing them so one example here might be something like this coming back to the previous example we had let's say you want to find the shortest path from home to school so in this problem by hand is pretty easy pretty much right away you can see that there are three potential paths from home to school one of them is this one just go to store a store B and then school another one is this one store B and this cool and another one the other one is from home to intersection to school and for these three paths just compare the distance that you need to travel for each of these paths and then pick the shortest one and to compute the distance that you need to travel for each of these paths you can for example use the longitudes and latitudes the coordinates of each of these places and find the distance in kilometers so solving this problem by hand is pretty much trivial but if you want to turn this into something a computer can understand you need to be much more systematic about it so to make this strategy something a computer can understand easily you might come up with a set of instructions like this one first of all find all the places you can go from home so in this example that's store a store B and then the intersection and then from each of those places find all the paths you can take from that place so from store a you can go to store B and from store B you can go to school and from intersection you can only go to school and as you go keep track of the distance you've traveled so far for each of those paths and keep repeating this process until you get to the school then if you happen to find multiple paths that allows you to go from home to school then compare the distance that you've traveled for each of those paths and finally find a path with the shortest distance traveled and then pick that as the shortest path okay so that's the result we were looking for in the first place and this is a good example of what an algorithm is basically you have a problem you're going to solve in this case finding the shortest path from home to school and then you have a set of systematic instructions for solving that problem now one thing to note here is that depending on what data structure you're using to store the data that you're performing the algorithm on your algorithm might look slightly differently you might even have in some cases completely different algorithms for solving the same problem depending on what data structure you're using in this particular example we talked about two different options for storing the information about where the streets are and how they connect different locations the first option was to just list all possible paths and remember that the first step in our algorithm was to find all the possible places you can go from home and to do that with the first stair structure this one right here you might actually need to go through the entire list because in this particular list we have three paths here from home but it's possible that we have another path from home right here at the end of the list so you need to go through the entire list just in case on the other hand if you use the second data structure that we discussed we have all the possible places you can go from home listed right here as a group so as soon as we find the home row in this table you won't need to go through the entire table anymore so in this particular example using the second structure actually makes it slightly easier to implement the algorithm that we discussed now there are structures and algorithms are really important to learn because they'll help you write efficient software as a software developer so for example when I was working at Microsoft as a data science intern I had to write this piece of code to retrieve some data and when I wrote it originally it was taking like seven to ten hours and basically it was too slow because we didn't want we didn't want to wait that long so I rewrote it using my knowledge of data structures and algorithms and after rewriting it the new version only took like five to ten minutes to load that data so that's why learning them is important and it's actually useful in many practical situations that you might encounter as a software developer - okay to give you an even better idea about what data structures are like let me give you another example here let's say you're hosting a party and you're expecting a bunch of people and this example is gonna be a little bit silly but just follow along and you're gonna see why I'm talking about this particular example anyway let's say that each person come to the party we'll bring sort of like a small ball with them like a ball that can fit in their hand and this ball will have their name written on it so when David comes to the party he'll have a ball with David written on it and when Kevin arrives to the party he'll have a ball with Kevin written on it and so on and this is just a silly little system that you came up with for keeping track of who came to the party in which order because writing now each person's name would be a lot of work you're just too busy hosting a party so as someone who's studying computer science let's say you're trying to come up with an efficient system for storing these balls so that you can keep track of who came to the party one idea you have is this one you get a very long box with 100 partitions a lot of partitions and each partition let's say has exactly the same shape you know 10 centimeters by 10 centimeters let's say and every time someone comes to the party you're just gonna put that person's ball with their name written on it in the order they came to the party so David's ball will come in here and Kevin's will come in here and so on and this is actually sort of like a data structure that's realized in real life and this actually corresponds to the data structure called array in computer science and here's another idea you have you get a bunch of boxes and this time instead of getting a long box with many many partitions you want to get individual boxes that are connected with strings so the first box is connected to the second box with a string and that's connected to the third box with a string and so on and just like before you want to put these tokens with participants names written on them in these boxes just one by one in the order they came in so David's token will come in here and Kevin's ball will come in here and so on and this sort of data structure that's realized in real life corresponds to the linked list data structure in computer science okay so the natural question here would be which data structure use for this party well it actually depends because it highly depends on the particular situation and the nature of the party really and each data structure has advantages and disadvantages okay think about this situation let's say 100 people showed up to your party and you're pretty happy about it but suddenly you realize that the 98th person is Paul had been misspelled that person's name had been misspelled so you want to fix that with the array data structure it's actually pretty easy you just need to find the 98th partition and that exact location can be calculated easily because you know that each partition is ten centimeters wide so you just need to find ten centimeters times ninety seven actually which is nine hundred seventy centimeters so you just need to walk over from the beginning nine hundred seventy centimeters and then you can find the 98th person's token pretty easily you just need to replace that with the correct token with the link list data structure though doing the same thing would be slightly more tricky and that's because finding the 98th person or finding the 98th box here would be much harder and the reason for that is because these strings are pretty soft and they can be pretty much any lengths so each box can be in any location relative to the previous box so this first box might be in the living room and the second box might be in the kitchen and so on so to find in 98th box what you need to do is you need to count them one by one so you need to say okay this is the first box and then this is the second box and let's find the third box fourth and so on until you get to the 98th person at this point you might say well the array data structure is a better one then well not necessarily so think about this situation let's say you have 100 people showing up to the party and you're pretty happy about it but suddenly five more people show up that you didn't expect with the linked list data structure it's pretty easy to deal with that you can just add five more boxes find five more boxes somewhere and then five more strings and just add them to the last box you had in the linked list data structure and then store the five people's tokens in those boxes with the array data structure though it's a little bit more tricky one option here would be to get another box with let's say 100 partitions again and store those people's tokens there and use the two boxes together or you could destroy the first box you had and then get a box with even more partitions let's say 200 partitions and then transfer all the balls you had for the first 100 people to the new box and then after that add the additional five people's tokens in the new box and in general if you have no idea how many people are coming to the party let's say anywhere between 5 to 1,000 people the linked list data structure might be slightly more convenient than the array because linked lists are so much easier to resize than it is to resize a race ok and this was another simplified example of what data structures are like on a computer and this sort of gives you a rough idea about how to actually start thinking about them and throughout this course I'm going to introduce you to even more data structures and this time I'm going to explain them in a much more technical way using concepts like classes objects memory and maybe even some code snippets too now if you're just getting started with data structures and algorithms one thing to keep in mind that's actually really important is to apply what you've learned through solving problems and the reason I say that is because it's so common for beginners to learn these concepts and not actually be able to use them in a real-world situation because they haven't had enough practice and actually this video sponsor brilliant org has an interesting website for learning these concepts in a sort of a new way ok to show you what I mean let's take a look at their computer science fundamentals course right here which I would recommend for you guys and let's go into the intro to algorithms section and you can see that it covers topics like arrays searching insertion sort and Big O notation and in the arrays section they have a bunch of explanations about the topic and as you continue you'll give you a quiz to test your understanding of the topic so it's definitely an interesting way to learn computer science concepts by solving problems okay if you want to check it out for yourself just go to brilliant org slash CS no joke and going to this link will actually help support this channel and the first 200 people will get 20% off the annual subscription and actually I'm super excited about this because they're the first sponsor I have on this YouTube channel and I feel like I'm becoming a professional youtuber finally so thanks for that brilliant ok as always I'm YK from CS dojo thanks for watching and I'll see you guys in the next video