1000+ Hours of DSA Summarized in One Video (Complete DSA Crash Course)

[00:00:00]Hey everyone, welcome to my YouTube channel. My name is Mayank and this video is going to be a full data structure cheat sheet. So what we are going to do in this video is that we are going to start from very basic that is an array. We are going to discuss that data structure. Then we going to discuss time complexity of various operations in that data structure. The important keywords that can help you identify whether that data structure will be used in interview or not and then all the important questions from that particular data structure. So we'll start from complete basic that is array. Then we'll go to stack Q and similar way we are going to discuss all advanced data structure. Okay. Now all nine core data structure that I have discussed here are enough for cracking coding interviews.

[00:00:37]Okay. So there are lot of data structures but these nine are very important from coding interview point of view and these are sufficient for cracking coding interviews. Okay. And just important consideration in this video I'm going to discuss only data structures not algorithm. And once this video is out I'll create a separate video discussing all the algorithms.

[00:00:55]Okay. So we are going to start only with the data structures in this video and in next video we are going to cover all the important algorithms with all the time complexities. So let's not waste further time and let's get started. So first data structure that we have is an array.

[00:01:08]Okay, an array is like default starting point for almost all problem. Okay, so array is like it's a default starting point and it's the most important data structure and it is the most primitive data structure. Now what is an array? So arrow is a collection of elements that are stored in contiguous side by side memory. Every element has numbered index starting at zero. You can think of it as row of numbered boxes and you can jump directly to any box in one step because you know exactly where it lives in memory. Now I have made sure the definitions placed here or written here are easy to understand. But let me explain you something. So for array the memory allocation is always contiguous.

[00:01:48]Okay. So let's say you are designing an array and you said oh build me an array for size four. So what linker will do is that it will do the memory allocation and allocation will be done in such a way that you said oh I need a area of size four. So what it will do four into let's say size of a int is four bytes then it will allocate 16 bytes of memory. So there is a memory it will take the 16 byt and it will allocate it to itself. Okay. Now it will divide it into four chunks. 1 2 3 4. Okay. 0 1 2 3. Now why it always starts with zero is that because 0 means it's a base address. So when you allocate a memory there is a address starting point. Let's say that is 0 x 5 b c. So this is already pointing to this particular index. Now once you add one to it, you will go to this index. Once you add two to it, then you'll jump to this index.

[00:02:43]Then once you will add one more to it, you will jump to this index. Okay. So when we say allocate the memory and why array starts from zero the this is the reason because zero index is the base index. When you say one then it jumps four by ahead. When you say two it jumps four byt ahead. Okay. So this way it works. Okay. So here's the structure of it. This is what array looks like. And I know all of you would know it but this is a cheat sheet. So I'm going to start from complete basic just that in case if you have forgot that any concept it will help you remember that. Okay. So this is what array looks like. Now direct jumping is possible because we have memory addresses and we can directly say if you want to go to fourth index that is space index plus four index which is equivalent to plus size of n. It can be anything but here we are considering as int. Okay. So it can be something like this. Now let's understand some of the important complexities here. If you want to read an index, the complexity is big of one because it's a direct memory jump. If you want to search something in an unsorted array, it is going to take big of n time because you have to traverse entire array. Then insert at the end will take big of one. Insert in the middle will take big of n because in worst case you have to shift n by two elements and that is approximately big of n complexity. And then [snorts] delete operation is big of n because once you delete anything you have to shift everything back. Okay. Now what are the catch with array? Inserting or deleting anywhere except at the end forces every element after it to shift.

[00:04:18]Okay. If you're deleting inserting from anywhere in array except for the end points you have to make a shift and in worst case that shift can be big of n.

[00:04:28]So it has no built-in concept of what come last or what arrived first. So yes, array doesn't have any such concept to store like oh what came first or what was the last element that we saw. It cannot do anything like that. Okay. And in array you are always thinking of positions and not patterns. In array you are always thinking of position. Oh this is the position one, position two, position three something like that. Now when to use array? So array is like a primitive data structure. that is used in almost all places but these are the few keywords if you see them you can think of array in that particular question. Okay. So that pattern is like index sliding window two pointer subarray prefix sum k element and in place. If you see any of these keywords in your interview then array can be that data structure that is used there. So for example when you see monotonic monotonic can be a stack can be a que.

[00:05:21]So same keyword can mean multiple data structures. But what this keyword will help you is it will help you understand which kind of data structures to think.

[00:05:30]So when somebody say monotonic you won't think of tree you will think of important data structure that could be useful here Q or stack. Right? Same way here if somebody says in place then you can think of array as one of potential data structures. Now class interview problems are two sum best time to buy and sell stock very important. This is very important. Okay. Uh this was asked in Goldman Shacks interview. Then maximum subarray rotate array product of array except itself. These are couple of important problems that you must try before moving on from array. Okay. Now what's next? So yeah array is good but what if you want to remember what came last or we want instant access to the last element or the most recent element then array won't be helpful here. Right?

[00:06:15]So in that case we use stack. So in that case we use stack. So stack is used when order matters and last is what you need.

[00:06:23]Okay. So stack is used when we have to store it in a particular order and we want always the last element first.

[00:06:30]Okay. So what is stack? Stack is a leo last and first out container. Okay. You only push add and pop. So two operations that are allowed in stack are push and pop. Now here's one thing. If somebody ask you implement stack, you will implement a stack using array let's say.

[00:06:45]So you cannot go ahead and add anything in middle. Okay. Even though you are allowed to do that because you are using array and it is allowed but still you should not do that because that will violate the property of stack. Currently you're implementing stack with array but but when you use a data structure that is provided by your favorite programming language like like C++ have stack. Okay.

[00:07:06]So the intern implementation won't allow you any other operation other than push pop top. So make sure when you're implementing stack using array you follow the basic principle of stack that is last in first out and operation that are allowed are push and pop and this all are done at one end. Okay and yeah the top operation is also there. So you can think of stack of plates. Okay you always take the top one and it is perfect for tracking what just happened and unwinding later. Okay, so this is a very important thing about stack. All the functions that we see in C++ or any other programming language once they are executed there's a call state that is made. So let's say you said function one okay you set function one uh in a in b okay if you say something like this so you know in even in your linker it will be stored something like this function call then initialize a then initialize b then whatever operation needs to be done it will be done like that and then we'll keep popping b will be pop a will pop function will be pop so stack is a very important data structure and it is heavily used. Okay. So this is what the stack looks like. Uh let's say we have elements like this A, B, C and D. Okay.

[00:08:28]So first A will be there then B will be there then C will be there and D will be there. Now top will always point to D.

[00:08:34]Okay. And getting it is big of one time complexity. Push will always happen from here and pop will always happen from here. Okay. Pop will always happen from here. So here's the 10 complex video various operation push big of one pop big of one peak or get the top element big of one search is big of n because you have to scan from the top to every element and what you have to do is that get the top pop it get the top pop it get the top pop it and that we have to scan so you have to traverse through all the elements so search is big of n then size is big of one if you want to get the size of an stack we always keep the track of it so yeah it's big of one now interview keyword that can help you think of stack is undo, balance, bracket, reverse, backtrack, DFS, call stack, monotonic stack or monotonic or next creative. So these are a couple of keywords that if you see in your interview, you can think of this data structure stack as a potential data structure. Now classic interview problems are valid parenthesis, minimum stack, daily temperature, largest triangle, next gator element. All of these are couple of problems that you should solve before moving on from stack. Okay. See, I'm not saying it will solve these problems only. You will just master interview.

[00:09:47]No, but these problems will be using stack only. So, it will help you understand that whether you understood stack or not. So, these are the problems that you should practice before moving on ahead from stack just to make sure that yeah, you know stack. Okay. Now, stack is all good, but here's the catch.

[00:10:04]You only test the top. There's no random access available. No way to peek at the third element without popping the above two. and you must respect the order and that constraint exactly what makes it useful. Now this constraint in stack is useful but only for a certain case.

[00:10:21]Okay. So what if I want to insert a delete in the middle with reference and big of one and not just at top. So let's say another key use case you want to insert and delete at the end. Let's say I have there's a there's some data and I give you pointer to that data and you want to delete and insert from there.

[00:10:38]Then stack won't be helpful. So what are you going to do? You're going to use link list for that. So what is linkless?

[00:10:43]Link list is used when we need dynamic size and cheap rewiring. So what is meant by rewiring? We just want to change the structure. We want to move something from one place to another and we want it to do in the cheapest possible way and we want to have a memory constraint or we just want our memory to grow as elements grow then link list is one of the potential data structure for that. Now here's the thing what is link list? Link list is a chain of nodes where each node holds a value and pointer to next. Okay, node lives anywhere in memory the pointer connects them and insert and delete a big of one if you already hold the nodes reference and you just rewire the pointer. Now this definition is easy to understand but let's understand what is linkless in simple terms. Okay. So link list is something like this. You have a node that has two things. Other one is next.

[00:11:31]Okay. And other is a data value. Data value. Okay. So it can be something like this. Each node holds a holds a value and a pointed to next element. So if there's no other element into at the end it will point to null. Now this link list is not contiguous allocation. Why?

[00:11:47]Let me tell you why. Because if it's a contiguous allocation you need to know the block beforehand. [snorts] But link list is dynamic in nature. So you cannot do continuous allocation. So what linker does is that it provides or allocates the memory anywhere in a heap wherever it is available. So it can be like one node can be at address 0x b1 1 0 0. It's a hexodimal address. Other can be at something like this 0 x c 012. It can be something like this. Okay. A and b something like this. So it can be anywhere. It can be scattered across entire heap. And this pointer will point to this. Okay, only way to access is from the next pointer. That's the only way to access it. And by mistake, if you lose the next pointer, you cannot gain access to that particular node again.

[00:12:37]That memory is lost. Okay? And once your program dies, OS will reclaim that memory. But before that, that memory is lost. It is used, but it can never be accessed if you just anyway miss the pointer. So this is what the link list looks like. Each node has a value and a next. Now let's talk about important operations and their time complexity in link list. So if you want to access by index that is big of n because you don't do a random access here. You just have to traverse the entire link list. So if somebody says index five you have to traverse 1 2 3 4 5 then search is again big of n then insert with reference is big of one. So let's say I've given you a reference to any pointer. Let's say this pointer node. Okay. If I've given you reference to this node, then inserting is easy. You can just do next and create a new node and just point it there. That's it. Inserting is very easy. If you have a pointer or a reference to a node, okay? And delete with reference is again big of one. Same operation. And append is big of one if the tail is known or the end is known.

[00:13:40]Okay? Otherwise, it's big of one.

[00:13:43]Now there are couple of type of link list. So this is a singly link list. And we have a doubly link list. Douly link list is something like this. There's a value. There's an next and this is a previous.

[00:13:57]Okay. So above one is a singly link list. This is a doubling link list. Here we have a pointer to the previous element and the last element also. Okay.

[00:14:06]So when we use dlink list we have lot of other operation open because with single link list you cannot go previous or you cannot go backwards. So with doubly link list you can go forward you can go backward however you want. Now what is the catch in link list we don't have random access. So array 7 is instantaneously accessible but link list get 7 will walk through seven nodes. So yeah worst case operation nodes. Now every node also carries an extra pointer. So memory overhead is real but we really don't need to worry about memory here. Honestly memory is not a big issue anymore. Okay. And this is cache unfriendly compared to arrays because node scatters across RAM because it is allocated in heap and since it is dynamic in nature it can be allocated anywhere in heap. Okay. Now interview keywords that can help you identify whether link list to be used there or not. First is reverse. Second is cycle fast low two pointers middle element merge dummy head or paladrome anything like this is mentioned. Link list is one of the potential data structures that you can think of. Okay. Now here are a couple of interview problems that you should solve before moving on from link list and that is reverse link list detect cycle merge to sorted array remove nth element from and and lru cache. So the text cycle is very important here. Okay just marking it star here just to make sure that you know it that it is very important. Now what if we need our data to flow in order like first in first out like a real world Q then we have Q data structure. Q is a first in first out order data structure. Okay. So in Q we follow first in first out. Okay. So it's a first in first out container. NQ at back and DQ from front. Okay. What is the meaning of NQ? NQ means insert. DQ means remove. Okay. So insert is always done at back. Yeah. It's done here. And DQ can be done from the top or the front. Now first person gets served first and the backbone is level by level processing. Okay. So in Q the important thing is that it does first in first out order or it does level by level traversing or processing and BFS use this a lot. If you want to do a level order traversal this is the data structure that you have to use. So BFS uses it a lot. So let's say if you want to insert anything else let's say you say D E F then F will come here and if you want to remove an N element it will be removed like this A will be removed first then B then C then D then E then F okay so this is what the important thing about Q is so NQ operation which is then a back is big of one operation DQ which is at front is also a big of one operation peak front which is big of one operation because we keep a track of it search is again big of N because you just have to dq all the elements look for that element and then nq them again okay then size is big of one because we keep tracking the size of a Q now Q is good but what is the catch with this so catch is no random access is allowed again in Q also we don't have a provision of random access only the front and the back are reachable and if it is arrayback then you either shift on DQ or use a static buffer with fixed capacity and that's why real implementation uses DQ or link list.

[00:17:28]Okay. So in real world Q is implemented using link list or the DQ. So link list is a very good implementation or very easy implementation for Q. Now Q is good and it can be used where you see the keywords like BFS level order cell shortest path by level schedule sliding window and monotonic Q not stack. So that's why I said you saw the word monotonic in interview. Now you can think of two data structures. one is Q other is stack nothing else two data structures and now you have to think which one suits their best without knowing this keyword you would have looked for all the data structures you would be thinking oh can I apply three here but now that issue is eliminated at all okay now classic interview problems uh level order traversal in sliding window maximum task scheduleuler and number of islands important and important level order traversal is a very important question you will see it in one of your interview any one of your interview will see this level order driver. So it's very popular question.

[00:18:28]Now what is next? Okay, Q is good but what if we want to look at something up by name not by position and I need it to be instant. For that we are going to use hashmap. Okay, it's a instant key value lookup and this is the very important thing for interview. Okay, this is a instant key value lookup. So what is hashmap? Hashmap stores data by key instead of by position. Okay, so hashmap stores data by key not by positions. So hash functions convert each key into a bucket index. So lookup, insert and delete the big of one operation on an average. And this tools helps you turn most of the nested loops and big of end time. Okay, this is a very important thing. It helps you convert a nested loops into big of one time when there's lot of repetition. Okay, so this is what a hashmap is. Given the name, it will hash you in a particular position. it will store the value. Okay. So let's say MJ age is 29. So it will be stored in a hash. So when you say what is the age for MJ? It's 29. What is the age for JK? It can be 26. Something like that.

[00:19:35]You can do a random access here. Now important thing is that your hash function should be good. The kind of hash function that you're going to use is going to define how well your hashmap would be. Okay. So hash function is very important in hashmap. it will be a gamecher and a bad hash function can help you make your hash map look very bad because you will end up losing lot of data or you will end up storing a lot of data depending on the implementation.

[00:20:01]So there are generally two popular implementation of hashmap something like this one is a key and value and let's say a new key value come and it's already occupied so it will store an n plus one index key value something like this and other is a hashmap with a q or adjacency list or anything like that. So key came you stored value one then another key came you store value two and then key two you'll store value two two where you two three something like this okay so with this access is big of one with this again you got all the keys in big of one but finding that particular key because you're storing it as a link list or adency list again will take big of an operation that's why I'm telling the hashmap implementation how you implement it is very important now I'm considering a best set function you're using that is a single key to a single value. That's the kind of mapping you are doing. So insert is big of one, lookup is big of one, delete is big of one, contains key is again big of one and worst case is big of n. And that worst case is when all the keys are colliding and you just keep allocating them n+1, n + 1, n+1, n plus2, n plus this kind of index. Okay, so what is the catch here? There's no ordering. You cannot iterate keys in sorted order or insertion order without extra work.

[00:21:21]Okay. And hash collision can decorate it to big of n complexity in worst case.

[00:21:28]Okay. And it uses extra memory for bucket array. Okay. And key must be hashable. That is another important thing here. Key must be hashable. But yeah, generally this hash function can easily do the hashing of any kind of primitive data structure. Now if you're using pair as a key then it's not possible then you have to look for the particular element of a pair that can be hashed. A pair cannot be hashed. So yeah all the primitive data structures are hashable. So you don't need to worry about it. Now important interview keywords are like frequency count seen visited memonize cache group by anagram to sum due something like this. These are the important interview keywords. If you see them you can think of hashmap as one of the potential data structure. Now important questions from hashmap are two sum group anagram longest substring top frequent element subarray sum and lru cache l case cach is very important don't miss it at all okay now hashmap is good but what if we want a sorted order and fast search instant minimum or instant maximum access and we want to do range queries then hashmap won't help and what we are going to use is trees.

[00:22:35]So next important data structure is tree and primarily binary search tree because binary search tree has a lot of use cases compared to a normal binary tree.

[00:22:43]Normal binary is also a very useful data structure but I'm just saying. So what is tree? When hierarchy or sorted fast search is required then this is the shape that you can rely on. Okay. So what is tree? It's a hierarchical structure of nodes with parent child relationship. In a binary search tree, every node satisfies that left sub tree is less than node and right sh sub and right sub tree is greater than node. And that property makes the search insert and delete all operation big of log end time when balanced. Now this is what a tree looks like. If you see this is a binary search tree and this is a binary search tree and all the elements to the left are less than this node and all the elements to the right are greater than this node. Same here. All elements to the left are less than this node. All the elements to the right are greater than this node. Similar thing here.

[00:23:34]Okay. So this is what the binary search tree is. Now here's the thing. The search in binary search tree is big of login. Okay. Insert is big of login.

[00:23:45]Delete is big of login. In order traversal is big of n because we have to visit every node. And height is big of n. Now one challenging thing the search insert delete can also become big of n in binary search tree that is the other issue with binary search tree and when will it be the case when tree becomes skewed it can be left skewed or right skewed. So what I meant by skewed it can be like this 1 2 3 4 5 I got elements in this order. So this is right skewed. Now if you have to insert anything you have to go here or here or here and here and then you have to insert. So in worst case it can take big of end time. Okay.

[00:24:24]So a binary resource tree is big of login time for most of the operation but in worst case if it becomes right skewed. Okay. If it becomes right skewed these all operation also become big of end time. And to avoid this we use balance binary search tree because balanced binary search tree always make sure that it will never be skewed. So balanced binary search tree or balance BST will never be right skewed. It will always be in a way that it takes big of login time from all of the operation.

[00:24:57]But here a normal binary search tree can be right skewed or left skewed. Okay.

[00:25:01]Now plain BST degrades to big of n if inserts arrive in sorted order and it becomes a link list. So balanced variants are avial tree and red black tree. So balanced binary history has two variant that one is a tree other is red black tree. Now they are important but generally not that important from interview point of view but yeah you can study red black tree if time permits it's a very good data structure you can still skip AVL and you can study red black tree but yeah most of the questions can easily be solved with binary search tree now tree nodes are always scattered in memory because tree is a heap allocated data structure it is like a linkless and so it is not a cache friendly okay or the cache suffers in case of tree. Now interview keywords that you need to look to make sure that tree is used here is hierarchy, parent, depth, recussion, DFS, in order, pre-order, post order, least common ancestor and balanced. Least common ancestor is important question. Balance is important question. Balance makes sure a question is like oh tell me whether this tree is balanced or not or tell me in this tree this sub tree is balanced or not or tell me in a tree are all sub trees balanced or not. So something like that question will be there. Okay. Now class interview problems are maximum depth same tree invert tree least common ancestor validated BST level order traversal serialize and path sum. These are a couple of interview questions that you should try before moving on from tree to make sure that you have understood tree very well. Okay tree is good but what if I don't care about full sorting. I just need the minimum and maximum all the time instantaneously. Okay tree is good.

[00:26:37]Yeah but I don't care about full sorting. uh in PST we have full element in a sorted order but I don't care about it I just want the minimum maximum element in just best possible type that's all I want so in case of binary search tree in worst case it will big of n and in best case it will be of login getting the minimum or the maximum element but how can I optimize it I will use heap for that I'll use heap so heap provide instant access to minimum or the maximum element because it uses the priority Q or the pri it's a priority machine actually. So what is a heap? So heap is a binary tree. Okay, important thing it's a complete binary tree. Now what is a complete binary tree and normal binary tree? This is a normal binary tree. This is a complete binary tree or this is a complete binary tree.

[00:27:29]This is a complete binary tree. Okay.

[00:27:32]And this is not a complete binary tree.

[00:27:34]Okay. So here important thing is that a complete binary tree with partial ordering and in min heap every parent is less than its children. So the minimum element is always on the root and vice versa for the max heap. Okay. And it takes big of one time to peak that element. Insert and delete and extract a login time because we have to do a bubble up or a shift down and they are stored in array. Okay. So heap is stored in an array. Okay. Okay. So if you're implementing heap from scratch, you will implement it using array. But if you're using it in your interview, you don't need to implement entire heap all over again. What you can do is that you can use priority Q because priority Q is a kind of heap only. Now this is what a heap looks like. The parent element will always be greater than its child. Okay, this is greater than its child. Same case here. Same case here. Okay, and getting this element is big of one. And once we remove this the again heapify operation to make sure the heap is always in order so that the biggest element or in case of max heap or the minimum element in case of the min heap is always remain on top will take big of login operation or big of login type. So peak getting minimum maximum element is big of one. Insertion is big of login.

[00:28:54]Extraction is big of login. Hippify which means building from scratch that will take big of n operation and search an arbitrary element will again take big of end time. Okay, because it is not sorted at all. Now the catch only root is guaranteed to be minimum or maximum.

[00:29:11]You cannot search for arbitrary element quickly. A heap is not fully sorted and you can't swap between minimum and maximum heap on the fly. Pick one at creation. Okay, important thing that I forgot to mention that if you created it as a min heap, it will always remain a min heap. If you created a max heap, it will always remain a max heap. You cannot swap like, oh, I created a min heap, now I want to turn it to max heap.

[00:29:34]That thing is not possible in heap.

[00:29:36]Okay. So, you just have to decide which kind of heap you want to use from the beginning. Now, here a couple of important keywords for interview like top K, K largest, K smallest, priority, median, stream, merge K, minimum heap or max heap. So these are the couple of interview keywords that if you look in your interview question you can think of heap as a data structure. So like top k this question I was solving yesterday only. So it was like number of elements were there they were repeated you have to find the top k elements and and two elements are repeated same time let's say my uh name name so name is repeated twice my is repeated twice then you have to return them in a lexioraphical order okay so my will come first name will come second. So there the heap was used.

[00:30:18]Okay. So this heap is important structure. So when they say top K think of heap first. Okay. Now popular interview questions are kth largest element top k frequent which I saw yesterday on lead code and if two elements have same frequency then written them in lexiographical order. So that was the question that I solved yesterday and it was asked in sales force and it was a very important question. It was a medium level problem.

[00:30:40]Okay. Then merge case sorted layers find medium and k closest points. So these are a couple of important keywords that you need to look for and if they are there then think of heap there without any second thought because I've saw a lot of questions like top K top this top that and most of the time heap was used okay now heap is good but if my data is complex and there's a many to many relationship like a social media network or road map then heap won't help here okay then what we are going to use is graph so now we have graph so graph contains of node and edges or vertices and edges and there is the connection and connection is the whole point here.

[00:31:17]So they are set of vertices connected by edges E and any topology it can be directed it can be undirected it can be weighted it can be unweighted can be cyclic it cannot be uncyclic okay and tree is a kind of graph actually so tree are special cases social media network road map prerequisite web pages are all become graphs okay so tree is a kind of graph actually honestly I'm telling you now this is what graphs looks like this is a vertex. This is an edge. Okay. So this is a vertex. This is an edge. Now graph can be a couple of types like one this is undirected. This is undirected.

[00:31:56]Okay. But now if we have direction something like this. If I have direction something like this. If all vertices have direction then this is a directed graph. Okay. Now this is currently directed and unweighted. But let's say now each edge has a cost. Let's say this cost you 10. This cost you 20. This cost you five. This cost you five. This cost you 7. This cost you 7 8 9. Now this is directed and weighted graph. Okay. So these are the couple of kind of graphs that we have. Okay. Now there's a cyclic graph and uncyclic graph. So if we say this graph so this is a cyclic undirected.

[00:32:34]Okay. This is cyclic undirected and unweighted graph. Okay. Now let's say I added a like this. Now this graph doesn't have a cycle because you can go till here but from here you can go till here but from here you this path is not possible. So a cycle is not there. Okay.

[00:32:51]So this is now uncyclic directed unweighted graph. Okay. Now most of the times undirected graph can have cycle but it's not always sure if all the nodes are connected in a undirected graph then most of the time it will have cycle. But for directed graph you have to look for the edges for the direction.

[00:33:08]Even if it is all connected, you cannot guarantee that there is a cycle. Okay.

[00:33:12]Now let's look at the complex video couple of operations like BFS traversal big of vertices plus HS. DFS traversal vertices plus HS algorithm E log B cycle deduction V + E that is traverse all the vertices and H's. So in worst case it will be HS that is V square. Okay. And topological sorting again V plus E.

[00:33:34]topological sort sorted graph or topological sorting or something like this is also important but you know I find it little hard to understand I don't know for some reason other people find it easy but I find it hard I don't know why okay now graphs are good but what is the catch graph can be cyclic disconnected weighted negatively weighted directed and all of the okay it can have any of those combination okay now you always need a visited set to avoid infinite loop yeah that This is an important thing actually when you're traversing a graph okay you need to make sure that you have a list of visited nodes because what will end up happening is that you will end up visiting same node again and again if you don't use this visited list so something like this let's say your graph look like this okay and you're traversing you went here now from here it has two options here also and here also okay now this is an undirected graph so what can happen is that your algorithm keep repeating between them it can keep circling between it. So that's why we keep a list of visited nodes. So this is visited.

[00:34:37]Even if it get circles here, it says, "Oh, this is already visited. I can move on." From here also, it will try to go back till here. But it says, "Oh, I have already visited it. Let me go in other direction." Okay. So visited list is very important especially when you're using the DFS traversal for the graph.

[00:34:53]Okay. Now if it has weighted path, we can use this cast. But if it has negative weights then bellman for is another algorithm that takes big of n cube of time and here n is the number of vertices or big of vertices cube. This is the worst case time complexity of bman. Now interview keywords to look for before you can conclude that oh craft will be used here versus network connection path root islands important component cycle dependency topological and sortist. Okay. If you see any of these keywords, you can think of graph as a potential data structure there.

[00:35:26]Now, classic interview problems are number of island, clone graph, core schedule, word letter, Pacific at test, very important, Pacific at length, this is very important. This is a lead code, hard problem. And then network delay.

[00:35:38]Okay. Now, this is all about graph and graph is good. But what if all I need is a ultra fast prefix search over string.

[00:35:46]So we want a data structure for prefix search in a string and a data structure that is specialized for string or something for autocomplete. Okay. So for this we use try data structure. So this is a try data structure. It is a prefix tree. Now it is a tree where each s represents a character and walking from root to a mark node spell a word and any node in the middle represent a shared prefix. insert and search operation is big of n where m is the word length and it is independent of the dictionary size. So what I meant by saying that it can be shared prefix. So let's say this is the case a string c a t c a r. So a is a shared prefix between c a t and c a r. Okay. Now insert word takes pig of n type where m is the length of the word.

[00:36:41]Search word is again same. Prefix exists is same. List by prefix p plus k where p is number of walks and k is the result.

[00:36:48]And delete operation again which is the length of the word. Okay. Now if you're relying only on the strings then a particular level length can be of size 26 in worst case a b c d e up to zed. So it can have 26 keyword. So from here we can have 26 different lines. From each one we can again 26 different lines. So yes but if you're only talking about alphabets and case insensitive. Now if you say case sensitive then yeah again more cases then you say oh I consider a b c d capital a capital b capital c 1 2 3 4 and special character like hashtag or anything like that also as a keyword then it can have longer level but yeah I mean in like a normal case where we are talking about case insensitive alphabets it can have maximum 26 level okay or 26 separate branches. Now what is the catch here? Ham memory uses every character can spawn its own node per one per branch. Okay. And that can be the case when it is very sparse. So let's say if we have something like this C A T N M A T and similarly we have separate sparse characters. So you know in this case try won't even make a sense. It's better to use hashmap here. [snorts] Yeah I mentioned it a huge space waste on sparse alphabet. more complex than hashmap and for oneshot lookup hashmap is always usually faster. So you have to do some minimum lookup hashmap is a better option but yeah if there's a pattern like cat cm c a r something like this in that case this will be faster.

[00:38:26]Now interview keywords to look for is prefix autocomplete suggest starts with dictionary word longest prefix word break exor if anything like this is there then try is one of the potential data structure that you can think of.

[00:38:39]Okay. Okay. Now classic interview problems are implement try word search to important word search to important design and add and search word replace word and maximum s okay this is again very important so these are the couple of important problems from the try data structure okay and you must solve them before you say oh I know try or I'm good at try not good actually you can say oh I understood try you must try these many problems before moving on from the try data structure to another data structure Okay, so this is it. This is the toolkit. I mean these are the important data structures that can help you cover 90 to 95% of your coding interview problems because all of them will comprise or can be solved using these data structures only. You don't need to study anything else. Now segment is one of the another important data structure which I haven't mentioned here because this is a variation of tree but it also have questions but it's not that frequent as frequent these data structures are. All right. So this video is entirely about data structures. Now I'll have a separate video for algorithms also so that it will be like a part two where part one is all about a crash course on data such as part two is all about a crash course on algorithms and that will make a complete crash course on DSA. Now I'll try to make sure that second video is also out soon because it's a placement season I know and this video will help you a lot and yeah that's it. If you like this video, give this video a thumbs up. If you haven't subscribed to my channel, please subscribe to my channel. And if you think there's something incorrect in this video or you want to have some more improvements for my next video or you want me to include something in my next video, if you have any doubt in this video, just comment it down below. I'll look at those comments. And again, if you haven't subscribed to my channel, please subscribe. Thank you and all the best.

[00:40:25]>> [music]