{S30} May2025 Warmup Basic Data Structures

Ajouté : 2026-05-23

[00:00:02]Hello everybody. Uh welcome to May 2025 S30s cohort SWE DSA oops concepts. All right and uh before we get into the discussions for today firstly we'll be having just a warm up today. We'll just start slowly.

[00:00:21]Uh there is no particular problem that we will be we'll be doing. Let me mute everybody else. Okay. All right. There is no particular problem that we'll be doing.

[00:00:31]We'll be just doing a chitchat. We'll be just having a discussion. Um but uh it's it's going to be a serious discussion.

[00:00:38]It's basically trying to inculcate the first principle thinking in your mind as a computer science engineer. All right.

[00:00:46]Uh but before going to into discussions, uh let's look at some housekeeping rules. Um your cam has to be on always without exception. If you're going to say that my CAM is not working, then I'll be judging you as a computer science engineer. That what kind of engineer are you whose CAM is not working. All right? And that starts now. If your cam is off, kindly take permission from me in advance. That okay. Okay. The the one exception is there uh for not having your cam on is the is the young mothers. All right. If you have a young baby um then um then I'm going to congratulate you and you can switch off your cam because for the obvious reasons um uh guys you don't have a privilege if your cam is off I should not be congratulating just 2 minutes sorry an sure uh if you have questions there will be specific times that I will be taking the questions that okay this is what I'm going to discuss and in between I I'll say that okay let's have the questions um but if something is really troubling you you can uh interrupt in between also um what else from tomorrow we will start with the with the problems um the first problem will be uh design het or hashmap uh and uh all of you should have been uh onboarded. I think some of the students are not onboarded but most of you are already onboarded onto the platform.

[00:02:30]Kindly go through the onboarding videos that how the classes will happen the recorded lecture le lectures and where you can access the recordings. It'll take a little bit of time about two hours for me to process the video and upload it and then it'll be uh you know posted on the on the back end. Anybody any questions about the logistics?

[00:02:56]I had one about the interruption actually. Sure. So let's just say you're teaching one topic. When when is the right time for me to interrupt you? Like will you take a special 30 seconds to you know do you have any question then I'm supposed to answer the question uh ask the question or it's like I I literally just unmute myself, stop you in your flow and then ask the question.

[00:03:15]What's the thing? Don't stop stop me in my flow. All right. I'll give you time.

[00:03:18]All right. Correct. Okay. Yeah. That's what if it is uh you know really troubling you and you can put your hand up um on Zoom. I'll be able to raise hand. Okay. Got it. Got it. Thanks.

[00:03:29]Um all right. Let's start then.

[00:03:34]Heypender. Yes. Uh what's the role of a co-instructor?

[00:03:39]The co-instructor is basically she is one who is looking at your PRs. All right. and the co-instructor will be if you have any doubts um and you are posting it in the slack channel that okay this is the doue then she will be taking that out um a lot of times I will be available but when I am not available she will be taking that out all right and most of the questions that we will be asking is um we will be taking it in the class only even if you are uh you know off offline like after the class hours if you have any questions I will say that okay let's discuss it tomorrow in the class only uh but if there is an emergency or something like that then Shindanda will be jumping in she is a very um experienced instructor as well she also does DSA uh classes from last four years all right so it's a privilege to have her as well all right let's start we are going to discuss about the first data structure that is arrays How would you define arrays whatever comes to your mind in any okay the firstly the uh the discussions are going to be language agnostic you think in generalized terms all right if there are some differences between Python C++ or Java I will be discussing it explicitly but think from the first principles not at the language level but how would you go one step down all right so what are arrays how do you define arrays What comes to your mind when we say arrays of elements collection please go ahead. Yeah. Uh collection of elements of similar data type or it could be different but they are stored in a contiguous sequence in a memory. similar data type. They can be but you said of different data types as well but keyword is basically they're yeah they're stored in contiguous. Yeah correct. All right. Different uh contiguous.

[00:05:48]Okay. When we are talking about arrays we are talking about static arrays.

[00:05:52]Okay. Any other features of arrays?

[00:05:57]Collection of same data type uh elements. All right. collection of same data type elements. Fine. Has to be it has to be of a specified size. It has to be of specified size that okay for the static arrays we define the size. For example, for the static int array the data type array is equal to new int array of let's say size five. All right. This is the way that we define a static array. fixed length data structure.

[00:06:27]Absolutely. Uh containing elements of homogeneous rate. All right. Similar data type but we'll see. All right.

[00:06:35]Shimoli is not entirely incorrect. We'll see that how do we generalize it. All right. If we have and we need to define the memory prior. All right. We have to define the memory prior and but uh how do we where is this definition of the memory right here when we have declared the array like this? Five. Let me let answer.

[00:07:02]It's the five which is given in the pars. But that's size. But what's the memory? Mhm. Uh it's like five into two.

[00:07:11]The size of int will be two, right? So it will be size into two. Four. Four bytes, right? Yeah. Okay. All right. So we will have the memory. But once we have declared the array like this, what does this represent? How will it look like in under the hood in the memory? What will this Okay, so let's say this is be a stack of memories or a stack of memories. Is the stack same as that of array?

[00:07:44]Uh no, not really. But it will be like a group of memories. No, it's it will it will be continuous memory. All right.

[00:07:54]So, it will be continuous memory. So, that is one of the features of arrays.

[00:07:58]Don't forget it. Okay.

[00:08:01]Contiguous homogeneous data type fixed length for the static arrays. We'll talk about dynamic arrays. They are called array list also list in Python also. All right.

[00:08:19]What's it called? What's a dynamic array called in C++?

[00:08:25]Vector. Vector. Dynamic array. Vector.

[00:08:29]All right. The vector. So when we have defined it like this, remember there are some things that we can apply on the arrays. Right.

[00:08:38]There are some if I do array of two is equal to two. What happens?

[00:08:48]What? We get the memory location of uh zeroth index and then uh plus two times which uh two times the size of the data structure to get the address of the location. Okay. We get the address of the location. We get the address of this location. Huh?

[00:09:07]Yeah. So, how do I get the address of this location?

[00:09:11]So, uh with the index index, let me get the index. Give me the exact way that it happens. Yes. Go ahead, Bari. You are on the right track. Go ahead. Yeah. When we say array of two, first we get the address of the base. Let me stop. Where is the address of the base?

[00:09:30]How do I get the address of the base?

[00:09:34]Isn't array an object? And uh we get the it's uh it the array is directly mapped to the base address which is stored in stack or for the program maybe anybody where is the base this is the reference this gives me the reference of it gives me a pointer it gives me a reference to the base. So we when we declare an array basically it gives me the it is pointing to the base address 420. All right I am writing it 420 under the hood it is much bigger it's a hexa string that we have as an address but for our purpose for our understanding I'm representing it as 420. All right. Anybody who is saying uh object please come out of the word of JavaScript. All right. It is an object.

[00:10:37]It is an object. But we have to see at the memory level how does it how does that object look like? All right. So 420 if I define array of 2 is equal to five. What happens? What is this called?

[00:10:57]Assignment.

[00:10:59]This whole thing is called a index.

[00:11:02]Index. Index. Index. We have an index.

[00:11:05]Index two. There is another another word for it. What is that?

[00:11:13]Offset.

[00:11:15]What did you say? Position. Offset.

[00:11:18]Offset. Great. All right. So, we have index two. I have to go to this index 012.

[00:11:24]It's me defining the indices on the whiteboard. Under the hood computer, the the memory doesn't have indices. It has base addresses. It has memory locations.

[00:11:34]How do I get the memory location of index two?

[00:11:40]You add it to the base. We have the base address [Music] plus two plus the size the size of the size of the data. Size into index size into index 2 into four.

[00:11:57]Why four?

[00:12:00]Because the end is integer by size four by that is four bytes. Make sense? So this is where the data type comes in. Somebody's not going to unmute yourself. You're not awesome. All right. So we have the base address, we have the offset, we have the data types. What's the size of a the data type that we are going to store in this array? So it gives me 428.

[00:12:31]So this is 420 420. This address is 4 to4. This address is 428.

[00:12:40]So now when I define this the system knows that we are referring to 428 memory location. At that memory location I have to put pi make sense and what's the time complexity of this? We'll talk about time complexities in details. It's a constant time complexity of one. It's constant big of one constant time big of one basically a formula basically a mathematical formula that we have and if I do this array of seven is equal to five when we have defined the array like this what do we get index out of box array index out of box error all right so so what happens 420 + 7 into 4 All right. So we get 448 which is out of bounds and we get all right when you have spoken you can mute yourself.

[00:13:47]Okay. Awesome. This is what happens in the arrays. It is a continuous memory location. Remember these three features continuous memory. If it is not continuous memory then we'll be not able not able to do array 2 is equal to 5 in one. All right, because I know that 420, 424, 428, 420 the memory loc allocation is contiguous in the array. A fixed data type and a fixed size that we define in the static arrays. Now what we are going to discuss is the dynamic arrays, array list, list list in Python and vectors in C++.

[00:14:28]You are given a static array. From a static array, you have to build a dynamic array. Few things that you have to take care of it. You have to don't think how it is implemented in your language.

[00:14:41]First, firstly think that you have to write an object which is called array list. How would you how would you define that object?

[00:14:53]What will be the data members? exactly the methods that you will be implementing on that array list to behave it like a dynamic. All right. So I have an array list. What will be the data members that I'll be having?

[00:15:10]There'll be one constructor. It would have an array of size. Constructor will come when we have defined the data types. Now firstly let's define the data types.

[00:15:20]The address location and you and the address of the next size. Yeah. Size of what? What should I write over here?

[00:15:27]Array list. Size of array. Size of array list. Okay. Size. Address. Probably a variable. Address of the next location.

[00:15:36]Address of the next location. What is the address of the next location? And how do I define it?

[00:15:44]like the pointer storage where yeah log space of okay what will be the parent data structure for implementing a dynamic array integer integer like if why would I define a link I should have a node right why would I be using a link So uh I think I think I think we started at the top. Let's start from bottom up rather than going top down. All right.

[00:16:25]Top down is that okay what is ar list and what will be the methods that you'll be implementing? Your language has array list or list right? What are the methods that you have on the on your dynamic array or or a list? What are the methods that you have? We can add an element. We can add an element. Insert. You can call it add insert. What is the usual usual uh time for adding or inserting?

[00:16:51]If we if we insert it and the end would be off.

[00:16:58]What else?

[00:17:00]Remove. Remove. Remove. Bro, if we are removing from the anything else index of length size. Okay, fine. Length size. Okay. What else? One critical thing in your nest. Update. Replace.

[00:17:19]Get get an element. Get an element. Get what is the time time complexity of getting an element sequential? You don't have the pointer there. So it's a constant of one says of and which language you use?

[00:17:40]Which language in Python? Which language you use in Python? When you do list of two, if I have a list like 1 2 3 4 5 in this list, if I do list of two, it gives me what?

[00:17:55]Uh two uh three. Three. And what's the time complexity of that? That's ofen of search it I think.

[00:18:08]Search search your your Google and let me know what if you don't know where the position is.

[00:18:20]I'll answer your question. Then how will you get here? We know the position or not.

[00:18:31]Yeah, we know the position. It should be for do we know the position over here?

[00:18:38]Yeah, right now we know but let's stick to this. Let's stick to this. What will be the time complexity of that? If we don't know, we should order one. It's order of one.

[00:18:51]That's why that's why we are using the list. That's why you are using the list.

[00:18:57]All right, that's why you're using the the arrays, static arrays, so that we can get the reference. If we know the offset, if we know the index, if we know the index, then I should be able to get it in one. Make sense? So if I want to to implement all these things, what should be the parent data structure under the hood?

[00:19:25]And then should it be static array? It should be a static array. Why a static array reference must be fix size and like you can get any element in big of one. If I want to reference an index that is of one. Yes. If I want to reference an index, if I want to get a value at a particular index, I can get in of one. All right. So if I define the initial size of the parent data structure over here in the constructor we will be able to define it. But what will be your def your decision that how much will be the size?

[00:20:04]Two two why why two?

[00:20:13]because it keeps doubling um exponentially.

[00:20:21]No, how you how should you make the decision? Depends on the input data depends upon yeah good depends upon the input and how would you how would you explore the input just like in one go like how many like elements we get according to that. So you look at the use case or you in the interview scenario you ask a clarifying question. You don't decide upon int also firstly if the interviewer is telling you that we want to define an array list. Firstly you ask what kind of data that you want to store in that array list. What's the kind of customer input or user data that is coming into that and what's the frequency of it. All right. Based upon if initially only you are having thousand elements then it is it is preposterous. It is very naive to start the data structure with length two. Make sense? Generally in languages in most of the languages it is started with 64. All right. So you look at the you do the clarifying questions based upon that you take your initial decisions.

[00:21:32]Once you have taken your initial decisions, we will talk about the methods that have to be implemented.

[00:21:37]Firstly, we will be having a constructor. For example, an array list. For now, bear with me. I'm writing private over here. Array list a method in which I will be defining the initial sizes of the parent data structure over here.

[00:21:58]Now if we have to implement a method that is length length of an array list which looks like this in Python over the hood that's how we define on the whiteboard but under the hood it looks like this let's say we have defined the initial size of the array as five only what will this have the base address firstly 420 20. If you have to get the length, let's say that in this list, for example, this is the push operation that you have in any of the languages, you are pushing one, you are pushing two, you are pushing three, you're pushing four. This is the size of the parent data structure that you have defined.

[00:22:50]But this is a list. If you want to see the current length of the list that is there or current size of the list that you have, how would you get the size?

[00:23:05]We'll expose a function. Huh? Expose a function. We'll expose a getter function. So we will have a function over here that is let's call that function as length, right?

[00:23:23]length function. What will be there in that function? We'll just return the counter variable. We'll just return the counter variable. Good. So, where is the counter variable? The size. The size.

[00:23:34]So, let's not call it size. Let's call it count. Remember in the data members we have a counter variable. So, if we are giving length length or size of the list, what will be the time complexity of that?

[00:23:49]One. We go of one.

[00:23:55]How it is of one? Because we are just giving this count. Lot of students think that we'll be doing this. That's not the way that you should be implementing your data structure. I can maintain a counter. Whenever we are pushing an element inside the data structure, I can increase that count by one. Whenever we are removing, I can decrease that count by one. So if tomorrow the length or the size comes in, kunar is absolutely right. I just need to give out this variable return count. Now this is a concept which is not there only in array lists in most of the data structures that you will be implementing. This is one of the key things. Don't do this. That is naive way of doing the things. That's how not how you take the size. You just maintain a variable.

[00:24:48]Whenever you are adding any element in the data structure, you increase that counter by one. Whenever you are removing an element from the data structure, you decrease that counter by one.

[00:24:59]Whether it is doubly link list, whether it is single link list, whether you are implementing stack, whether you are implementing any kind of data structure, whether you are implementing LRUS. All right. So this is a good this is a great concept that maintain a data member a variable int count whenever you have to get the length or the size you just do it do it in a way let's talk about push or insert or add so if I am pushing push five let's say the data structure has one two already. If I have to push five, what would what will be the time complexity? Where will it be pushed in your language? Where it is pushed? If I push five, where is where does it go? It will pushed at the end after 20. Second index. After two. After not second index, at second index. Huh? At second.

[00:26:04]At second index. All right. After two, it will be there. It will be pushed.

[00:26:08]right here. How does the system comes to know that? Oh, I have to push at this memory location.

[00:26:15]We are maintaining count. We are maintaining a count, right? We are maintaining a count. When this was there, the count was two. So, if the count is two, I already have the base address 420.

[00:26:32]What? I already have the offset.

[00:26:38]I already know the data type. It will give me the memory address. Hey, go to 428 memory address and put five over there. Whenever we are doing push add, it pushes to the end. But if I want to push at the any other index at any other index we'll talk about that if we have to push at any other index we'll talk about that but let's come to further things if I want to push six now remember as soon as we add five the count goes to three if I want to push six insert six at the end what happens now same thing counters increased and 420 plus count is already three 3 into 4 that gives me maintain a size variable also why because you'll eventually read the end of the array that's why that's why I'm doing we'll see all right and we don't need to maintain the cycle we'll see what all right so 420 + 3 into 4 what is that 432 2 at 432 location I will be putting six it becomes four. All right. Now if I want to push seven what happens? I have 420 + offset 4 into 4 16 which is 436. At 436 location I will be put able to put seven.

[00:28:27]If I try to push eight, I don't have any space left. All the static array that we have defined as a parent data structure is occupied. But this is a dynamic array.

[00:28:40]Remember that the whole thing about the dynamic array is that it should be dynamic. So how do I make it dynamicity?

[00:28:50]How do I bring that dynamicity into the picture?

[00:28:54]Keep on adding memory. Keep on any memory. How? Create a new array with double the size of the No, not double.

[00:29:03]It is 3x2 + one.

[00:29:06]We check the size if it is full or not before uh inserting an element. Okay, we check the size before inserting it. And how does how would you implement it in this without in by allocating the by allocating memory of the incoming data.

[00:29:24]Maybe we can check if 80% of 90% of the spaces have been filled. We can increase that. So if I need to define another data member, I can define another data member. Size capacity. We need something to track the size of size capacity. All right.

[00:29:43]Capacity. What's the capacity? All right. Or fill. How much is the fill in the array? All right. So let's say what do you want to take the capacity at what index? So if I have already put seven and suddenly immediately it comes in you'll get an error. So you have to do it before fill the last index.

[00:30:13]How do you define the capacity? What will be your decision?

[00:30:18]What what will be the action that you will be taking? what should be the capacity that I should be while inserting an element if your capacity or threshold is less than is filled up more than 80% uh you would be uh you can increase the size or declare another array list we'll go to the other array list later 80% uh anybody wants to take any other other number or is it always 80% Not necessary% I just give an idea of 80%.

[00:30:55]You can go to 60 or idea but how do you validate that idea that is it 80% or I should be going for you can have a value and ask the user if he wants to set a specific value. No no since we can only add one element at a time. Yeah. Since we can only add one element at a time. So we can have this check at n minus one. So at n minus one that again circle backs to this thing that what kind what is the use case is it the is it the size of the data type which we are adding it's a use case that you know if it is 80% in and at that time you are trying to increase the size of the array to twice make sense at that time it may be possible that you are having the data which is becoming very very fast very fast within the milliseconds all Right? So you decide about the threshold based upon the use case in with what frequency and that's what you have to discuss with the interviewer or the in the real world you have to discuss look at the how the user data is coming based upon that you make the decisions all right but this is an idea which is given by which is perfectly correct that we look at the user data and we decide that oh 80% is going to be fine if it doesn't work out we'll reduce it if it breaks with iteratively we can improve our data structure. All right, for now we are taking a decision that the threshold is 80%. So at six when it is 80% full I know that the size of the array is not going to be enough. the mother data structure is not going to be enough and I need to have more size for storing my data.

[00:32:54]All right, let me take the question first. Yes, Kavita go ahead. Uh sir, can you give some practical scenarios of setting threshold like we said like uh depending on the circumstances we set the threshold right now it's like a uh standard format that is 80%. So could you give some examples that I get the concept here?

[00:33:18]like where it has to be lesser than 80%.

[00:33:20]Yeah. Like suppose it's a question asked in the interview and you kind of discuss with the interviewer uh and then you kind of come up to a threshold like so can I have some examples uh on this is the kind of conversation that you'll be having. All right. Okay. If he says that the push is coming every 5 milliseconds.

[00:33:41]Mhm. All right. push is coming every 5 millconds then 80% is you are you saying that oh probably 80% threshold will be fine but he says the push within five millisecond there are thousand pushes which is coming in and the frequency of push is lot more within one millisecond we have lot of push all right then you say that okay let me try it with 80% if it fails then probably I should be going with lesser 75% I'll try to figure it out whether it holds at 75% % if it doesn't then I'll go with 70%.

[00:34:15]Okay. So the these are all estimates basically there's no formula for it.

[00:34:19]It's all estimate and based on the use case that's what is the use case.

[00:34:26]What should I do? Threshold is 80%.

[00:34:31]Copy your array into increase size array and then use that. Okay. So increase the size of the array. Increase the size of the array.

[00:34:43]Remember the array lists contiguous all right they have to continuous memory allocation and we should be able to get if in this array list you are getting list dot get one that you are getting two in all one time okay so we have to increase the size of the array first decision how much Please by twice why again use case again use case if it is coming every 10 milliseconds then probably 2x is is an overkill all right again you go back and discuss it with your interviewer or you look at the use case if it is the push is coming every 100 millisecond then probably I don't need I can go with 1.5x all Right. But generally what happens is under the out it is implemented with an extension factor that we are calling it extension vector that is two. All right. You can change it to 1.5x based on your use case also. Now I don't want a fixed array of size five. I want an array of size 10. If the extension vector is two, what happens? What should I do for making it dynamic?

[00:36:15]Acquire new memory and copy over the existing elements. Acquire new memory and copy the existing elements over there. Yes. So if I pushing seven right now, it is 80% full. I will go to another memory location 840 where I will be making an array of size 10 step 10. Remember we are thinking from the first principle there little bit of real estate issues over here and we will be copying one over here, two over here, five over here, six over here and then pushing seven to that right here. This is what Dan is telling us. Or uh we already have one array. We we have a reference of that array with us. we can create a new uh new array of whatever two X size you want to create and connect the reference of the first array with another array so that we don't have to do this exercise again and again and whenever there is a call we can that calculation can be done behind the back yeah we'll talk about that Dan is doing this all right the what's the side effect Dan good what's the side effect if you are creating a new array and you are copying the elements from here to here I'm complex we will not get constant will not get constant of one everywhere till now we were getting of one but if I'm creating an array at a new place then we will be copying the elements from the old array to the new array and then we'll be pushing to the end it becomes offend the worst case for pushing an element to the end becomes offend But at most of the places it is written of one push is pushed towards the end is of one. Why do they say of one?

[00:38:25]New word amortized. What is immortized time complexity? Good. On average on average we first principle whenever we'll be talking about the algorithms we will be talking about the worst case time complexities bigger notation but whenever we are talking about designing data structures we should be bothered about the average case scenarios am what kunal is going to say is trying to say over here at one it was perfect of of one of one of one at seven it is of at 8 again of one perfect 9 also of one 10 also of one so once in a blue moon I have to increase the size of the array to twice so we will take the average case scenario not the worst case scenario and he's absolutely correct but Ariana has a great suggestion he says rather than copying the elements from here to here maybe I can create an array of size two and I can connect the last address make a pointer over here and I can point to this thing this is what his suggestion is we'll come to that suggestion anything else we can do that I don't have to create a new end for every element if there is reference of the next element He is not he's not dead. He is sleeping infinitely from the size if we can get the last element and it memory address and append. Okay. Can I increase the size of this memory to 20 or 10 at the same location? Can I extend this?

[00:40:24]That depends. If you don't have the location, if you don't have the location or memory after that, there is some other memory who has consumed that. We don't have that. Yeah. Good. Akash and Tanme are two friends. Akash is having a array over here of size five. Tanme is sitting with a link list at 437.

[00:40:52]Then next to 450 something like Tanbe is having a link list over there. Akash has an array over there.

[00:41:02]Now Akash has a use case that he has to extend the memory. Akash says T already has a link over there. He will start there will be conflicts.

[00:41:20]I might not be having the availability of extension at the same location as I cannot do it. Now Arant is saying that why don't we do this at the last location I store the memory location of 840. First question is how do you store the pointer? Remember the data type is homogeneous is int. How do we store a pointer over there and at which location I will be having pointer? Let's see. Let's say that Arian pulls it off. He says that I will be doing it with the pair. This is what Monica was thinking. All right. If I have a location from here to here, then when this is full, probably I can put seven over here in the pair integer and the pointer to the next. I have 8 over here, 9 over here, 10 over here, 11 over here.

[00:42:29]Cool. This can happen. We can implement it like this, isn't it? Will it breach anything?

[00:42:40]Will it be the formula to count the uh address would break, right? The formula for counting the address will break.

[00:42:49]Good. Be more specific. You're absolutely right, Neil. Like we can use the base address plus the uh data type into the uh index that will break. So array of let's say array.get six.

[00:43:09]What happens if I have an offset of six? What happens?

[00:43:15]Like the base address now we have two base address uh so to say right for the both the arrays like uh it's starting from two different points. So we have like two base address. Don't worry I'm storing I'll be having base address 420 only. I am taking that as the reference only. So 420 + 6 into what? Four.

[00:43:35]Yeah. Is going to be what?

[00:43:39]uh 4:30 4:30 right now at 4:44 who is sitting with his link list was it Akash or was it who was it San D was sitting with his link list and you'll get some garbage because 444 is not belonging to this. Remember I want to get it in one and I use a consistent formula or a consistent thing for referencing an index. The whole purpose of the array was that I have indexing. Now I don't have an index.

[00:44:35]Now I have a garbage value at six. So in order to build a better push you have breached the basic feature of the array. What is the basic feature of the array?

[00:44:53]contiguous make.

[00:44:58]No, it is not contiguous and that's why your basic method will be breaching without exception. All right? And this will happen when you are designing the data structure and when you are doing the algorithm, you'll take the stairs and you will be thinking locally at this stair that how do we make this stair better? How do I make this push better? And this will take care that this these stairs are not broken into if you're looking at this part locally on it. Don't do something against the basic features of the data structure that you have. So this is not the way that we should be defining it. Is it clear who had this doubt? Who had this suggestion?

[00:45:49]That was a good suggestion.

[00:45:51]Arant did you get it? Awesome. Yes, Akash go ahead. What's your question?

[00:45:59]So, uh the basic way we define a dynamic data type like we use heap, right? So, we don't have to worry because the heap is increasing memory location according to the basic principles. Okay, let let me stop over here. There are lot of assumption. How is the heap implemented?

[00:46:17]like no no just from the what I have read or what I have uh that whenever that that is okay it is exactly like this all right this is we are talking at the memory level it's a contiguous memory allocation make sense you do anything that I am going to you do it using tries you I'm not saying that it will be implemented using tracks all right that I am going to do implement it like this I'll bring the sky down you bring the sky down but under the hood you will have to go for the continuous memory allocation only does it make sense Akash because that's a basic feature of the data structure that we have all right and heaps are not any heap any st any stack that you have implemented any heap that you have implemented it's going to use under the hood the three basic data structures that we'll be discussing. All right. So for storing the data the basic first basic data structure is an array a continuous memory allocation make sense? All right. So if somebody is writing heap just go under the hood and see how is the heap implemented. What is heap? What is the memory allocation in that? What is the memory structure into that? All right. So we'll not stay at first level or shallow that oh we believe oh it is implemented. Tell me under the hood how it is that implemented. Okay. Got it.

[00:47:57]First principles. Yes. Omar. Go ahead.

[00:48:02]So what if we uh change our base reference address to a new address which is free and we kept a new variable which holds the old address. Okay.

[00:48:19]I'll be having another base address, right? Yeah. So, how many variables? If I have 1 million array, one million data structure is coming.

[00:48:28]How many variables you'll be having?

[00:48:32]Around half a million because we here yeah half a million because if we are doing twice twice twice 96.

[00:48:41]Okay.

[00:48:42]So but my question is that if array.get comes in how would you decide which face address to use? Now we are start make sense. Yeah.

[00:49:00]All right. Don't say that okay I will be exploring everything. If you explore everything all right then you'll be basically going over you know so many and you'll keep getting array out of bound index error array out of bound index and array out of bound index. So it has to be consistent. Your data structure should not fail is should be should be the uh should be your prerogative.

[00:49:25]Don't try to optimize something which is going to break tomorrow. All right. And if I have lot of addresses, lot of addresses, it's still breaches the basic requirement of the data structure that it has to be continuous memory array. Make sense? All right. This was push push towards the end. If I want to push at a particular index, insert, add, lot of students in Python, they do it. They are implementing a queue using a list and we push at zero syntax. All right. First in first out kind of. All right. So if I have a data structure like this, 420 is the base address. 1 2 3 4 5 it's actually six now five huh so I have one I have two I have three over here I have four so in a list I have this is the situation it's a dynamic array I want to put five push five at index one how would this list list look like in your languages how does this list look like If I insert five at index one 152 1523 1523 good this is what we want to achieve focus on this how does it happen in the under the hood in the memory location at the memory level remember we have the base address 420 and then we need to traverse you need to traverse and need to traverse to what? Yeah. The position to that particular Yeah. index 420 plus 1 into four.

[00:51:23]Huh. Okay. What do we do over here?

[00:51:28]Now we make Yeah. If an element is pres present then we would just shift the remaining to the next location. We have to shift the remaining. And how do I shift the remaining?

[00:51:43]By adding uh bytes to the base address.

[00:51:48]Those byes might not be available to us.

[00:51:51]So once we get hold of the this link list over there you have to move all the elements already have the space over here for now. Makes sense. Aish why do I need to add the index available? We will if we have If we have if we have breached the threshold then we'll talk about how do we increase the size and that's what we did with the exponential vector I don't need to have we are not in that situation 80% is not full 80% right so I we can use at this location how do we do it yes go ahead yeah we can use count uh as three uh we can copy to four and then two to uh three and one to two so this is what we can do. All right. So there are two ways if you want to implement it. Your languages generally implement it one way. There are two ways of doing it. All right. You do it normal push.

[00:52:49]You do a normal push over here. Five. And you already know the count. You know at which index it will be going. 420 + 3 into 4. You push it towards the end in one. And then you do this swap up to index one.

[00:53:17]Swap. Either you do this or you can do this. Five over here. We had two and three over here. Don't put five directly over there. Two will miss. Two will go.

[00:53:32]it will be dis it'll disappear. Don't do that. Remember I want this. If I put five don't I don't want 153. I want 1523. Insert at a particular index. You go to index one. You put five. Store two in a temporary variable. Put that temporary variable over here. Put three into that temporary variable. Then move your three right here.

[00:53:59]Basically doing this.

[00:54:02]So either you push to the end and do this bubble up or you put over here and bubble down. No matter whatever you are doing whether you are bubbling up or bubbling up what will be a time complexity pushing at a particular index of average everything off immortized also often. So is it a good idea if I have to insert at a particular index? If you're using if in Python I'm using a list and I'm adding it to the zero index under the hood it takes how much time is it a good idea to use a list as a Q in Python?

[00:55:03]No. What's the better data struct all right? So don't use an array list or a list as a key. You can use it but you should know like Simoli he says that I'm going to use a but in production I'll not use I'll use a DQ just for coding purposes I'm doing it. I know that it is of n. All right. So pushing at a particular index of n pushing towards the end amortized of n. Now if I want to remove a particular element.

[00:55:52]Let's say we have 10 elements. 1 2 3 4 5 6 7 10 elements. These are full. Count will be equal to 1 2 3 4 8. Huh?

[00:56:16]If I want to remove or pop. Pop does what?

[00:56:25]Removes it from the end.

[00:56:28]What happens? How do I do it in Mr. 420? I know what count right now. 8 into 4 that is going to give me 450 852 it will give me this address this address so what should I do count minus [Music] countus that will give me 448 420 24 28 32 36 40 44 48 What can we do?

[00:57:18]Remove the count. Remove it. I can make it any garbage.

[00:57:23]Reduce the count or we can just reduce the count on that. It's a garbage value.

[00:57:31]All right.

[00:57:37]All right. So let's say that I'm making it minus one for now. If I want to remove one more element, pop I know this count is 7. 7 minus one. I'll go this and I'll remove this. I'll remove this.

[00:57:51]I'll remove this. Pop pop pop. Exactly.

[00:57:54]I'll remove this. Again based upon the use case that what is the frequency of the pops?

[00:58:00]Generally what happens? The pushes are more the pops are less.

[00:58:04]But for now we are just that they are consistent for our discussion. You discussed it with the interviewer and he says that you can assume equal quantity of pushes and pops. Now when once you are pushing pushing pushing it went up to 1 million.

[00:58:25]Now pop has happened and you are left with very less elements. What should happen now?

[00:58:37]You want to trim the array list to avoid.

[00:58:43]Yeah. And how do we trim the array?

[00:58:46]Reducing the size. And how do I check where to reduce? Extend whatever is there after count just free the memory.

[00:58:58]Not just so the capacity should be less than half that's check just like upper threshold we have a lower threshold and based on your use case you will be deciding the lower threshold for the upper one it was 80% let's say for the lower it is 30%.

[00:59:20]When the array is 30% full then you have a squeeze factor consistent dynamic array when you are going ahead ahead ahead push same thing pop pop pop same thing all right I don't want a 1 million memory allocation if I just want to store three elements all right so when the pops are happening you look at the lower threshold if the lower threshold is 30% you can reduce the size by squeeze factor again based upon the use case.

[00:59:53]Let's say the use the squeeze factor is 1 by two. You reduce it by you were increasing by twice you are reducing by half.

[01:00:01]Now what will you do in that scenario? You do the same thing. You create a new array at 840 location.

[01:00:20]of size five.

[01:00:22]Now you copy the earlier elements and now your mother address. Earlier it was 420. Now you are resetting the same mother address to 840. And this memory is free for sun to play around with his linkies. So we extend in the same manner. We squeeze in the same manner. If we are copying the elements from here to here, what happens? often at certain specific places. Kunal is going to come and he is going to say what what's the time complexity of pop singortized over immortized. All right. Yes. Go ahead.

[01:01:29]So uh when we uh reduce the size of the array uh for example I saved an element like let's say a value,000 at index 500 but when you reduce it the indexes get messed up isn't it? So is that if we have thousand elements his question is we are at 500 index is that we say yeah is that lower threshold no uh the other elements like the uh other elements are empty le let's say so the do you know what I mean like the it has garbage values in so your static array is of length thousand correct And your 500 elements are fulls correct one two up to 499 right make sense right so lower thresh 499 not achieved yet. Yeah I think I got it. Uh u I thought like uh we were also considering the garbage values uh as like uh not included in the size but the uh if we delete something and it has a garbage value we would include it in the size right? Yeah. The count is giving me the actual length of the list. All right. Right. Okay. Yeah. Makes sense.

[01:02:49]That is in the static array thousand.

[01:02:52]Right.

[01:02:53]Right. No. Makes sense. Makes sense.

[01:02:55]Yeah. So even if I have 500 over here at 500 one location I have to count as 500 at 500 location it doesn't matter. Even if you have other value some other value garbage value. Let's say that garbage value is G Molly had left 500 one over.

[01:03:11]Let it be there. If I want to find push at 500th index or 5001 index, if I want to push, let's say, 10001, you can push it.

[01:03:24]You can overwrite 5001 whatever was there, you can overrite it to,000 does it matter? Make sense, Neil?

[01:03:34]Awesome. Yes. Yeah. All clear. Yes.

[01:03:36]Kavita, go ahead.

[01:03:38]Uh I think you'd already mentioned but where do we store the new base address like from 420 right here all right all right if I had the earlier one was 420 now it will be overwritten to 840 okay so push pop we have done pop was we have done it at a particular end at towards the end only if we have to pop from a particular index for example if I have 1 2 3 Do I need to go get into the details? If I want to pop index one, what happens?

[01:04:13]The list becomes 1 34. What's the time complexity? A what's the time? Good.

[01:04:23]Off. All right. Open.

[01:04:25]What happens? This is the memory. Mr. 420. 1 2 3 4. All right.

[01:04:36]There are two ways again I can do this 3 to2 and I can pop from the end use a normal pop this happen 1 3 4 is it so if we are swapping uh of n shouldn't it be of n minus one in that case yeah that is of n - 990 1 million - 1 1 million make sense sha okay this is a good time there are two thumb rules of time complexity analysis what are the two thumb rules of time complexity analysis constants are constants doesn't count both matter only consider the higher order values matter and the other thumb rule only considering the higher order ones higher order values matter higher order terms matter constants don't matter two thumb n minus one okay I didn't know thanks oh cool all right so pop from particular index of n that's it that's it for array lists I had the continuous memory allocate I could store the data over the people the good people at Slabs when they were doing it in I don't know 2030s they were having arrays only if I have the array list I have a static array I have a dynamic array from there I've already developed it why do I need link lists what are the properties of what are the features of link lists for the random popping and random inserting you don't have to go off and So you don't need the continuous uh memory location for that. The basic feature of the arrays is continuous memory. The basic use case of link list is non-ontiguous one. Shilpa comes and she says why do I need not contiguous memory? I can use the continuous memory everywhere.

[01:07:01]Why do I need non depend upon use case? We can freely store you can utilize the memory for the use case. But if if my use case is there, if I have the availability of continuous memory, then why would I be going for the thing is if we use continuous memory, we have this restriction of we have this restriction of uh pushing and popping in O of and an amotized thing comes into picture. But if we have a link list which does not restrain us from using continuous memory that gives us the ability to push and pop in of one time. So there is basically a trade-off. So if you do a push and pop in one time check in the link list push is how much time of one constant are you sure about that it's not of it's off single link double link. So if it's if it's a single link English then still off I think it's not the push but it's still we need to append the or correct correct correct correct that's that again we have to traverse to the end we'll see the whatever is the strength of the data structure is also the limitation of the data structure the strength of the data structure array is uh continuous memory and we can put indexing over But that is also the disadvantage. The whole thing is that somebody mentioned it that we might not be having continuous memory allocation. Imagine Neil K also comes with the memory allocation that I have to have a 1 million array. Kunal also I need to have a 1 million array also stream 1 million array. Argu says that I have a smart refrigerator on which I have just 5 MB of space.

[01:08:57]Whenever we are talking about the data section, first thing that we start thinking about is command quantum computers that I have all the 200 TB memory. Barabi has just bought a smart refrigerator. I don't have that much of memory allocation over there.

[01:09:22]Omar says we will add some memory over there. We will add a big new refrigerator of 2 million terabytes.

[01:09:31]Marggo say I don't have that much space in my house. Make sense? So I can have devices on which or cell phones. All right. Even if I have lot of GBS memories over there, it may be possible that there are so many cat videos which are there that you have to watch. It is very important to watch cat videos these days. Instagram you call it Instagram. Omar is already make sense. So memory becomes a critical factor at that that time. So wherever we don't have the continuous memory allocation requirement or we don't have the availability of continuous memory, we can use the non-ontiguous memory. Nilkata is substituting with his thousand from with an array of five elements from 420 to whatever 440 and then Shrimal is sitting from 450. Omcar just squeezes in 445 I'll take then 8:45 I'll take I'll bring build my link list at these memory locations in between. So a link list has what?

[01:10:44]A data and an extra value. That's a node. All right. If I have to define node of a link list, it has a data value and it is not 445 after 845. So why do I go from 445 to 845 says that we can reference to the next location. All right. Node next. If we are talking about this, we are talking about singly linkage. Next, next. Next, next. If I have to store a reference to the previous also, that is called what?

[01:11:29]All right. Now, let's talk about singly link list. I can have a node. I can have a value. I can have a key also. Who stops me? I can have more data members. I'm building my own link list now. I can have key value. I can have any other data in that. Is it apple boolean? Make sense? I can have a list as a data member in that node. You can have anything.

[01:12:03]I'll have the initial base address node node is equal to new node of blah maybe I can have a string al all right I have the reference to it is Mr. 420 I'll have the reference to the next for now let's talk about integer on one and at 485 location I have two I have reference to next one three it's at let's say 505 non-ontiguous and reference to next Four. All right. This is pointing to none. This is the form of the singly link list. Somebody's not mute. Can you mute yourself? All right. And what are the functions or methods that we have to implement on a link list? Singly link list. Remember you are developing your own link list. Insertion, deletion, search. Insertion, deletion, search.

[01:13:16]We'll talk about search later. Huh?

[01:13:18]Insertion, deletion.

[01:13:23]Size. Length. Size.

[01:13:28]Okay. Length. Size. Same thing. How do I get the length?

[01:13:34]Maintain the count. Maintain a counter.

[01:13:36]Maintain a counter. Now you guys are fine. Maintain a counter in the data members. When you are inserting, increase the counter by one. When you are deleting, decrease the counter by.

[01:13:46]Cool. I can get the size of the length with this method. I can get the length of the size of one literally in any data set. If I have to insert insert where shiny add uh insertion at head at maybe add to head there is one function add to head or add to take let's talk about add to head. If I want to add a zero towards a head what do I do?

[01:14:16]Check if head is present. And it's always present. Okay, then just uh add it to the next uh add a new node head next of the new head.

[01:14:36]So we have inserted zero over here. It has a next pointer. Right now it is pointing to null. What do I do?

[01:14:46]Point next of zero to new node. New node next. This new nodes do next is equal to what? Head.

[01:14:59]No.

[01:15:01]Yes. Just head. Just add.

[01:15:04]This is what has happened. And what should I do now?

[01:15:11]Reset the head to new node.

[01:15:14]This is the new head. How many time to constant of one? Perfect of one. That's it. Playing around with the pointers only. Cool. Yeah. If I want to add to the 10 of I don't have reference.

[01:15:42]I have it till we get uh the reference till the time next is not equal to null.

[01:15:50]I trade till there and then we can insert a somebody's watching TV on the back. I can listen to mitakarati either let's watch it together. All right. Yeah. So we can traverse towards the end when we hit null at that time we can insert it. All right. That's awesome. But if you have the creative independence, can you do it better?

[01:16:19]Maintain a tail pointer. Maintain a tail pointer in your object. Exactly. Yeah.

[01:16:24]Maintain a tail pointer in your object.

[01:16:26]In the single link list, you maintain the node head, node tail object. All right. So you have a class link list. A little birdie told me that I can have a counter so that I can get the size. I can have the node head and a node tail in my link list. All right. In that scenario adding to the tail also becomes one. You add five towards the end. You do do next is equal to this new node. The next of this new new node is pointing to null and move your tail from here to here. Reset this. So add to the tail also can be done in one. But insertion at a particular they say that insert it after two then you have to traverse start at after two elements count of three elements then we'll have to we'll have to go in an offend manner 1 2 3 then we add it create a new node next of it is E and this previous is equal to this new node but we have to traverse. So insertion at a particular index although there is no indexing as such in link list indexing is a concept of continuous memory allocations.

[01:18:15]Deletion again. If you have to delete from the head, just move your head pointer to this. Store it in a temp. Temp. Next is equal to null. This is an orphan node.

[01:18:33]Now in C, you will be physically deleting this memory. in Java or any other dynamic languages like Python the orphan nodes will be garbage collected you don't need to be worried about that uh so in link list it's not continuous memory right the memory is not no not sure that's a basic property of the link list all right so you are thinking that where how do I go from here to here is that your question uh no no okay okay [Music] uh add to how do I remove the tail traverse from head way of doing it. Can we do it in one?

[01:19:29]We have a tail pointer then want to know the previous Yeah, exactly.

[01:19:35]No, you guys discuss among yourself.

[01:19:39]Exactly. No. So my question Yeah. I had like a question before. Yeah. Go ahead.

[01:19:44]So the thing is if we are maintaining a tail pointer here and we have to remove and tail pointer is pointing to to the tail of the link list and we have to remove that particular node. We we have to keep a reference that will take us back a node. So we can or we just make it uh free. I mean we just make it null or undefined. Yeah. So for that for that we have the count right. So we can just decrease the count and we'll just go back like the previous node. His question is valid. All right. Yes. And Shrimoli fight. His question is from here to here. How do I go from five to four?

[01:20:20]Because five will be storing the next reference that is pointing to null. I have a single link list. How do you go from five to four? You need to have a doubly link list. We'll see. So either double link list. Can I do it in single English class? Yeah, we can actually.

[01:20:36]Yeah, we just do it. Yes, we let Yash and Shrimoli fight first then we'll bring the other wrestlers into the picture. Yes. Yes. So, what I think is like uh that Shrimoli say saying that if we dreference the last like tail node, how we know that the tail should the four should be the tail, right? Yes. So what I think is what I'm thinking in that direction is that we have the count right. So if we are dreferencing the last node tail we can decrease the count that count will take us to the tail should be a pointer. Tail is a pointer.

[01:21:11]No. Yeah that's right. Node tail is a pointer. Right now it is at Mr. 420. All right. And the next node over here is 420.

[01:21:22]Yeah. All right. Because if I have to d Okay. D reference it. I don't know what is dreferencing in this scenario. All right. How does the referencing work?

[01:21:32]But I have the count. Let's say count is 1 2 3 4 5. Okay. If I have to remove tail, I will make this count as four.

[01:21:39]Okay. Now, what what is the new tail pointer pointing to?

[01:21:44]Second last one. Four. Now, before give me the red. How do you get there? But like how do you go there?

[01:21:51]Yeah.

[01:21:54]Yeah. We don't have the previous address. Yes. From the head only for singly we don't have the previous address. Yes, we don't have them. I'll have to traverse. Yeah. Asha comes and she says yeah. Yeah. Aa go ahead. Say when we iterate to remove the tail, can we maintain the temporary node which says like uh no when node next is null store this address and this tail. Okay.

[01:22:19]Why do I need when the okay temporary pointer? So your temporary will be right here only. What do you do with this temporary? Tell me how do I go to four back to four because that should be my new tail.

[01:22:35]Okay. No. Next do next can be stored as like in one iteration itself. Okay. So we can so basically maintain a current and previous pointer. Yes. Maintain a current and a previous pointer. Okay.

[01:22:48]You can do that and then you can remove but how much is the time that you took?

[01:22:52]of N of N. So let's get back to the again discussion. I want to do it in off one. Can I do it in one?

[01:23:05]In a single link list in a singly link list. No in a singly link list. All right. Now somebody comes and somebody says Dan you are wrong.

[01:23:16]I'll maintain in my object class uh in my link list object I'll maintain a node head node tail and a previous previous node previous day no no not in the node in the node I have next only just previous so previous pointer right here a tail pointer over here this is a single link list node still I maintain a previous over and comes And he says that I will be doing previous dot previous is the new tail. Now I'll declare it as a tail and tail do next is equal to null. I'll dreference it. But then how will we find the previous to previous? Now previous is this is just yeah exactly this this is this is not generic. This is just one level. This is just hello thinking. This is me thinking only once. Darian comes and he punctures the whole logic. He says go to the previous tail.

[01:24:24]Now somebody comes and he says no no no you can make the previous number as the previous. You have declared this as the tail. Move your previous number to the previous node. You can reference from previous. Daran comes and he says how do I go to the previous from four to three.

[01:24:44]The whole logic gets make sense. So don't think just first level think multiple levels. The tail is removed. What if new tail is removed? What if tail after that is removed? Then dash then shrimal comes previous. Then somebody say previous previous. Then dash says one more. He says previous previous. All right. That should not be happening that you cannot have 1 million data members in the link list. Make sense? So removal from the tail is of course of n still add I have a question sir.

[01:25:23]Addition to the tail is of one but removal from the tail is of n in case of singular list. Yes.

[01:25:32]Uh yes. So when you say that we are having a next uh pointer and a previous pointer, aren't we having both those pointers for every node?

[01:25:42]No. So here's what I was referring to.

[01:25:45]Here's what's the difference.

[01:25:48]Linked is an object. We are designing an object, right? So in that we have node head. There is a class node which has int value and node next.

[01:26:10]So in the link list I'm maintaining the node pointer to the head node tail. This node data data this object node still has just value and node next.

[01:26:28]I I get it. Yeah, I get it. All right.

[01:26:30]So two different this is a node. This is a different object. But this collective is a link list. All right. So if I'm maintaining three things over here, it's not that in the every node that I am maintaining. If I change the the object node like this that I will be maintaining node next and node previous then in every node I have a next and every all right. Yes. Okay. So that's why I didn't didn't I should have written for tail previous tail pre rather than previous. Okay, if you're getting good similarly if I want to part remove a particular node go and remove 505 then again I'll maintain a current pointer maintain a previous pointer. We should be one step ahead.

[01:27:31]about all right I'll maintain a previous I'll maintain a current I'll do this previous null current right here are you equal to 505 no move your previous to this position current to this position are you 505 no move your previous right here current right are you 505 no move your previous right here current right here are you 505 yes my previous is right here all I need to do is previous next is equal to previous text and I can do current.exe equal to null make it or it will be garbage collected. So deletion in case of a particular node in case of link list whose reference we are given 505 is of n. If I have a double link list and the reference to a node is given 505. What's the deletion? Insertion is same of one at the head of one at the tail of an in between.

[01:28:44]deletion towards the head list of one one one the disconnect in between yeah okay I'll come to your question just a moment all right if I want if I'm given the reference to a particular node and I want to delete it in w link list what will I do node previous next is equal to node next whenever you are dealing with the link list please jump onto the whiteboard node dot previous is to do next is this arrow is node do next remember we are given the reference to node okay don't worry if you want to leave you can leave we'll spill over a little bit and so So this is there there remember three is still connected to four as well as two all I need to do is node dot next dot previous is equal to node previous node next previous is equal to node previous once these are done I can do node previous is equal to null node do next is equal to n it becomes orphan it is removed from the dlink list in one when we are given the So if we are given the ref in a singly link list removal is often in a double link list removal is perfectly open and that is a one of the crazy or the awesome things that we will be using for double link list in the data structures when we are designing LR cache LF caches there we will see oh slowly single link list oh singly link list will have removal of all them hence we will be using double link step by step by step. Let me take question from Hasha. Go ahead.

[01:30:48]So, uh yeah, regularly we use link list but uh when we consider double link list, we have many advantages over uh single link list, right? So in which cases do we really use single link list?

[01:31:03]So for every use case for singly link list, we can always uh like replace it by double link list.

[01:31:11]What are the real world scenarios? Can you uh let me know some? Yeah. So we have seen that okay doubly link list is better than singly link list if I have to remove it everything we can and literally every function that we can every method that we can implement to singly link list can be done in d link list and in some scenario for example this even with better time complex uh what's the disadvantage of double link list over single link list extra space space off extra space in every node I have internet is breaking right in every node I have one extra pointer make sense hasha uh yeah so but uh we have uh like uh accessing uh front and back is pretty much uh easier right what do you mean by easier if I have don't have the consideration of extra space now or if I don't have the disadvantage of continuous memory allocation then I'll be going always continuous memory allocation it's always is that there will be use cases when you don't have extra space in that scenario you cannot do double link you will go for the single link yeah but uh in uh real time uh can you give me an example like so where we use the smart TV the smart refrigerator that who had bought Jo I'm going to make you buy a smart refrigerator all right Joyce has bought a smart refrigerator she doesn't have extra space all right in the real world for the those smart small devices probably I cannot use I I don't have the what do you call the privilege of using extra space make sense hasha did you did you get it like uh I didn't uh exactly get so yeah it's okay not okay you are thinking computers you are thinking cell phones of 816 GBs.

[01:33:17]Think about the devices which you don't have the privilege of extra space where you are you are right now the there are like you know planes or the tips of the radar all right in which you don't have the extra space every space is very very crucial. So don't think quantum computers think very smaller ones. All right.

[01:33:43]Yeah. Okay. And also uh one question that I missed is you know ars we have talked about and we have been talking about the homogeneous data structures. People in Python hate me. They say that okay you are saying same data type but we in the list I can do this also one two and blah blah also I can store blah blah also. How do you do it? How do I do it in Python? I have integers also string also directly by maintaining a list right?

[01:34:21]No, forget about the string over here.

[01:34:24]What if I have a long two long three long in Python or in Java also we can do it. So we have two data types now. I have two data types now. One is integer, another one is log.

[01:34:41]How would larger data type just go with larger data in that case go with the larger data type long eight bytes int four bytes. So I will not allocate the memory with the integers. I will just allocate the longs only and at that memory I can store integer also because it's the lower data type. The bigger data type matters. So I don't need to do 48 4848. No, no. I'll just declare everything 8888. That's what Python does.

[01:35:22]8888. So always go with the higher data type. You allocate the memory according to that. The smaller data type can be adjusted. That's how the generalized lists are implemented in Python. You sacrifice the space. Yes, Omar. Go ahead.

[01:35:43]So you just said that uh take the larger data type uh when you are implementing list. But what will happen for uh the ones which are previously having lower data types? For example, if I'm uh in my list I have here's how the conversation.

[01:36:02]All right. If you have the the previous ones which are with the smaller data types then probably you have not asked the the clarifying questions correctly remember clarifying question is what kind of data is coming to you he says I can have integers and longs would you be starting with just integers probably that will be a wrong thing to do all right that's what that's what happens when you are asking the clarifying question you have to ask the clarifying question what kind of data that we getting all right that's the sole purpose of knowing this that you should you be going for just integers or should you be you be going for generic data any sense omar yes thank you all right oh sorry uh I have a question what happens if we uh allow string also in the list strings can be of any size yes we are now we are into uncharted territories now we I don't discuss it on day one we'll discuss all right how much time is left are we done with the time okay I'll just take five more minutes okay um before going there uh that if I am having data structures I'll go with firstly think about concept of hash I have continuous memory allocation I have non-ontiguous memory allocation I can insert I can delete in fact push and pop is amazingly amortize of one in case of arrays and array lists in case of arrays perfectly of one in case of arrays amortize all Right? What's the need of hashing based data structure? Hashmaps, hashets. Why do we need them in the first place? And remember, you know, continuous memory allocation, non-ontiguous memory allocation will be the basis of me choosing a link list over an array list always. All right? These are not just generic that we are doing warm up. Let's do the brain analysis. No, no. That's how we will be choosing the data structure.

[01:38:00]When do I choose a hashmap or a het or what'sing? As far as I know, it makes the searches easy for us. It makes searches easy for us. Oh, retrievables.

[01:38:13]What do you mean by easy? No duplicates.

[01:38:16]By easy, I mean we don't need to iterate in the collection of objects rather what you're trying to find is translated into some address that you can directly go and access it. Search of one is what a is trying to say that I can make search or one with hashing based data structures can have question please yes search O one now let's benchmark it to arrays and list link list if I am searching in a link list 1 2 3 4 5 6 if I have a list they say go and find if four is there not the index four if number four is there then a is going to do four is there he's going to take of offend type for that such is often in case of lists if I have linked list then apparently it will be often he'll be doing go to this note are you1 are you1 are you1 are you one of now the basic use case of hashing based data structures is making the search of one amortized. Cool. That is a basic use case of hashing based data and we will be implementing hashing based data structures with certain things. We'll discuss them tomorrow. How do we implement the hashing based data structures? But the basic use Wherever we want to make the search of is hashing. Yes. Go ahead. So uh when you say amortized uh like I think correct me if I'm wrong when you say amortized because there might be a possibility that two or three of objects might translate to same address like hash collision or something. Yep. That's why is it amotized? Yes. because of collisions and there are collision handling techniques which is called we'll discuss about them linear chaining double hashing then we have uh binary chaining all right we we'll be testing uh linear probing but um we'll the idea will be trying to make immortise all right good because of the collisions only we'll discuss about the collisions if somebody had another question uh kunar kunar had another question go ahead Nobody okay and we will discuss about the hashing strategies basically the parent data structure that I will be having in a hash hashing based data is no duplicates let's break some mths no duplicates is it the reason that I need to I need to absolutely forget about search if I don't want to maintain duplicates Is het the only data structure or hashing based data structure are the only data structure? We can also use a set. Set is same thing asset. Any other data set that if my use case is I don't want to have a duplicates in the data structure binary tree. Oh need link list and arrays. We can remove duplicates.

[01:41:50]Now the time complexity might be the issue.

[01:41:55]time complexity might be the issue because in search if I am able to remove that element in one I can search it in one and I can remove it in one probably using a hasset that's advantage but having no duplicates is not the reason that we are using a het searching in one and removing it in one is the reason but if I want to have no duplicates that is not the basic Use case of the hashing based data structure. I can have the node duplicates in a link list. I can have the node duplicates in another. I can very well implement it. Another myth is I want to have key value pairs. Is hashing based data structure is the only use case for maintaining the key value pairs.

[01:42:45]Oh, we can use tries. Forget about tries. We can maintain two array list all together and match the indexes. that can suffice the uh I can maintain one array list only in which I can have a node or a pair or a tupal.

[01:43:01]Yeah, Python people are going to love me now. All right. I can have a pair. I can have in which I can key value. I can have a node key and value. I can literally maintain key value pairs in any data set.

[01:43:19]The question is if I have 111 over here, 212 over here, 31 13 over here, 44, give me the value corresponding to 313 in array get 13 in link in hashing based data structure.

[01:43:48]O1 it will be search of one which will be this will be the side effect of search of one it's not that okay because key value that's why we have to use hash the search of that key is an or one again search optimization of the search is not there in the arrays and array list or a link list that is a basic use case of hashing datas Now we'll see how do we implement it using hashing. Uh somebody said okay we'll close at this concept and this is one of the important concepts. What is a string? Bargavi was saying was it bargabi or bhavan? What's the name? Yeah, Barabi. Barabi. Barabi was saying that if I have 1 2 3 blah and Andy or let me ask you. Okay. What is how is string? What is a string under the hood? How is it memory allocated?

[01:44:57]Contact. Array of characters. Array of characters. Array of characters.

[01:45:02]basically continuous memory allocation of the characters. So basically it looks like B L A H. How would you store it in a in a list or an array list or basically under the hood it is an array?

[01:45:21]How would you store it? How would it look like?

[01:45:24]Base address. Base address. Make sense?

[01:45:28]So if I have reference I'll have a reference to this is 420 and this is what 320 some other base address to 320 where I will be having blah and that is a basic way that the nested arrays or nested data structures work. If you are given tomorrow now that you are given this array over here 1 2 3 4. This is a list dynamic array. I can insert any elements over here. 4 5 6 5 6. How would it look like under the hood? It would look like this. the primary array its reference to another list where I have 1 2 3 4 and another list where I have 5 6. Why is it like that? Think from the first principle. Why is it like this?

[01:46:41]What I am claiming over here is that the primary data structure has just just two references. Two elements, two references only.

[01:46:51]What's the size of this primary array?

[01:46:55]Primary data.

[01:46:58]Size of the both two into what? What's the size? What's the size of a pointer? Search it. What's the size of a pointer?

[01:47:09]Four bytes. Four bytes. Sure.

[01:47:13]Yeah. Four bytes. Four into two that is eight. The primary data structure is of eight bytes. Sorry.

[01:47:24]Somebody comes and he says that oh no no no it should not be eight bytes it should be 1 2 3 4 4 into 4 16 and last 8 it should be 24 but it is 8 bytes why should I be why should I be structuring my data structure like this a reference to a list reference to another list why can't I do 24 over here not adhering to the biggest block of memory Again it should be continuous, right? It is continuous. 24 also continuous.

[01:47:59]Indexing uh might be a problem.

[01:48:01]Everything breaks. Not only indexing everything breaks. I'll tell you if you go if you want to get two it will be array of zero primary array zero index one further into that nesting that indexing goes for a six another thing that you this is a dynamic list prashant adds 5 6 7 your primary data structure stops behaving it says I have 24 only what are you talking 4 1 2 3 4 You added 7 8 over here it will be over 8 into five and six everything starts breaking. Hence a data structure in a data structure is always a pointer. Listen to this statement carefully. Data structure in a data structure is always a pointer so that I have the flexibility.

[01:48:58]I have another data section. I can add 7 to 8 to 8. it doesn't interfere with this. Hence, nested data structures always in the primary data structure I have a pointer to the nested data structure. Hence, this will be having a pointer. Hence, this will be a pointer to Andy. That's how the nested data structures are structured under that. All right, make sense?

[01:49:32]Bar does that answer your question?

[01:49:34]Yeah, thank you. Done with the class.

[01:49:36]Bye guys. Have fun. Anybody who has questions can say yeah I have a question on this. So uh let's say we have this 1 2 3 and then blah. Right. So in in this scenario is it still not uh uh static array in in Python?

[01:49:58]under the hood it is going to be a static array but implementation will be the with the dynamic array the parent data still has to stay as static array where are you going with this I can have it dynamic also I can add five five also six also over here no my my main reason behind this question was let's say instead of ply it's it's a bigger string over here right so can uh it can have it's this is the primary array doesn't need to the it's Not the change that you will be rather than blah you will have blah dion right where will that dion will be added you'll get this index and you will be get this getting this pointer in that you'll be having dian writer does it affect the primary array primary array still has five elements only it's not the dynamicity of the primary array that you are doing it's the dynamicity of the nested data set that you're doing. Cool.

[01:51:02]So the Python list is not really an array list in this scenarios.

[01:51:06]It is an array list because why are you assuming that okay I have to add dash only because Rohit comes and he says no no I want to add after ND I want to add seven also. he can add in that scenario the primary data structure will be increased to 10 not here at some other place of course right so I need the dynamicity over here also I need the dynamicity over here also this string is basically a a list or an array of characters all right that array is basically a dynamic cool okay okay one thing that okay that I made a mistake is basically strings are immutable data structures. All right. If you are concatenating anything over here it will not remain 320 only.

[01:51:54]It will change because strings are immutable. A new string will be created. That reference will be right here probably 420 whatever 820. All right. Then something will be coming because strings are immutable. If it is string builder then it is mutable. It'll remain same.

[01:52:14]few discussions that you should not be understanding right now. If you understood my last three sentences then you are then you are ruined. All right. All right. Don't worry. We'll start understanding those things. Bye guys. Have fun.

[01:52:31]Thank you.

[01:52:33]Thank you. Thank you. Go ahead. Thank you. Thank you. No, no, no. Thank you.

[01:52:38]Questions?

[01:52:41]Anybody has question? Yes. Sat you raise your hand. You're not speaking. I'm not You're not audible.

[01:52:57]Yeah. By the time can I go?

[01:53:00]Where? Yeah. Yeah. Go ahead. Yeah. So the thing is I was under the impression that uh not knowing uh those bite things and the calculation I think that is very language specific. So is it fine for me to not know or at least not tell my interviewer as an interviewee the entire math behind it? Is it is it fine or do I like stress on the math as well? You don't need to tell them. You need to know that. Okay. Okay. Yeah. Awesome.

[01:53:27]Got it. Yeah. So you're not you can if you can write in the chat then I'll be able to take I I think my audio should be working now. Is it fine? Yes.

[01:53:36]Awesome. Uh so my question was related to like what you alluded to before you mentioned first principles. So um I wasn't sure exactly what you mean by that. Do you mean like breaking the problem down to the most basic part principle is that okay don't take any reference from your languages. Think from your head that you are solving the problem for the first time you start I have to develop an array from scratch. How would you develop not how has the languages developed it? All right. You start thinking from the first principle means that it is a very fresh problem to you.

[01:54:13]You are inventing the wheel by yourself.

[01:54:18]All right. Okay. Got you. Think that and the reason for that is that okay we will be able to take the reference from the languages. We will be able to see how it happens. But the idea behind it is making you start thinking from scratch about a particular problem is a unknown training that you are having because tomorrow you will be having a problem which you might not have seen and you will be coming and you will be saying that okay I have done 100 problems but whenever I get a new problem I'm not able to do it. This is doing that from the first day you don't need to come to know.

[01:54:53]Got it. Got it. Okay. Thank you.

[01:54:57]Bye, guys. Have fun.