Live Mock DSA | GeeksforGeeks

Key Takeaways

[Music] [Applause] [Music] thank you [Music] [Music] foreign are you sure this course is just for 2499 yes and you know this is the only course with this expertise across the world no way yes way [Music] don't delay enroll now Geeks learning together hello and welcome back to this amazing Channel Geeks for geeks this is abhinav I am currently working as a DSA Mentor at Geeks for geeks and today we are back with another session of live mock the essay so please write a Plus on the chat if I am clearly audible to you all that's the plus one and then we will start so yeah great guys so let's start and so today we have Amit with this let me join how are you yeah hi I am great how are you great yeah I am fine too so Amit please tell tell us something about you your audience yeah hi I am Amit currently working B Tech in computer science and engineering and uh I am currently in in my tech expertise in like Android deaf I am currently doing in Android Days by using Java and in I made various projects and I saw film as open source contributor and I contribute in various open source program and participated as a project mentor and a project contributor like various open resource program and one thing is about in open source I qualified amethyst Fellowship round two not around three qualified but around two qualified English industry so that's it about me great great damage so it's it's amazing you have you have a great experience and I think development in Android and so can you please tell us something about your projects means I just told you have something hackathons yeah maybe um inside participated in two or three hackathons and I have means personal level project in like a track application using Firebase as a backend I used wheels I used the Firebase as a backend and there are various API faced like GitHub provide fbis or code posters Etc type provide apis and Rapid API by using rapid API I use there are lots of apps and there are Indian government provide covid API so by using that also I make a application means by just entering the PIN code you can search the Google direction available or not in this way you can get the projects great so the projects are amazing so are you still working on the projects any possibilities some of the apps are in life in Google Play Store but uh now I am still practicing a DSA just now my main focus is on DSA okay great so let's let's come to the accident so wait guys uh I hope that uh that's so are you good to go I just started person is that if you're good to go and we're going to start the session so uh Amit I have shared our seat with you please share that seat yeah yeah okay great guys so fine let's start with the first problem okay so let me write the problem here so is it visible whatever I'm writing yeah okay great so the problem number one is this one which is you are given an array of sizing which contains zeros ones and twos and you have to solve the array in ascending order so this is going to be your first problem let's say let's take some example that you have n is equal to 5 means you have an array of size 5 and the numbers are 0 2 1 2 0. so you have to basically sort this array in ascending order like zero zero one two two and that's all this is what you have to do so is the problem clear to you yeah I've got it good good yeah how we can do it okay so this is a problem like containing 0 1 and 2 we need to sort it so if we think about the first approach so what we can do we can just using use any sort like bubble sort but the if you use the open source then the time publicity of the algorithm will be big of n Square okay okay L Square but by using this sort we can do it now we'll sort just sort it and we can do 0 0 1 2 2 we can get it but uh so for first optimize just we shift one and we can think about the Mars sort we can use the math shot if we use the math sort then the time compression will be n loaded okay okay so but uh we need to more optimize if if then more optimized then we need to means that the questions specify that this just containing 0 1 and 2 so we can just count suppose so you can just count the zeros and we can just count the ones and we can just count the screws so after counting means we use the same type of counting sort means we just count the elements means after using this we can use the three four means first for for zero then for one and then two so we can get the answer isn't it that uh zero run for two times and then one then two so we can get the answer but there is another approach you can do it by using there is a famous algorithm like what what was the what was the space and time complexity for this one which we have just told yeah in counting sort we can do it by using means we are just counting means what is the number of zeros and number of ones that's the the but we are using some space like uh we are using sort you store the elements in the anything so and after that we use the three four but for that three for the time complexity will go of n okay okay okay fine so you you were talking about some another approach you know yeah so after that we can think about like uh there is a means famous approach we can do it right that's nothing like means that approach say that we can use the three variables one is low another is neat and another is high what they said t 0 to 0 foreign foreign so that's the means my Approach we can do it by using that so how we can proceed further means the error is 0 to 1 to 0 0 2 1 2 0 so at first we need to understand that is the uh three variable like low mid and high so we can initialize the row by using 0 and just inside the meat by using 0 and just I understand that is the high Edge the size of the array minus 1 means just pointing to the end anywhere that's it n minus 1. so after initial digestion we can proceed further that we can create a loop that uh while it means we just given a condition from a operation at first no pointing here and mid pointing here and high pointing here so we are just Traverse here means foreign okay so for that we need to write the condition that if means meet greater than High make this less than high then we have just comparing the elements that uh if the elements means if the array is ARR that's representing that if the array of low mean supports my row is here and my mid is here if the error law okay if the error error made if the array means suppose my mean is pointing here and my low is pointing here what we say 0 to low everything will be zero so my no is pointing here and my mid is pointing right here so my if my mid is 0 if my mate is zero so um so here we can use the in temp variable detail array of mid just write it and in array mean we can assign the array hello and after error we can assign the error into 10. so after that we can just write after that we can just write the we increase the low point of just here so that's the zero zero check means uh however the low point and midpoint the zero check is done and after the zero point we just need to check about the high means whereas the highest pointing right now so now we are picking if mid means if needed meat is now pointing to the two so we need to exchange the two and the high where is higher quality High variable is pointing so if array means ship with the same thing with the temp array made and in the aromat we can assign the high and in the high we can assign the 10 so after that just decrease the high sorry that slot but after that we just decrease the it is fine I am getting it okay okay after that we can decrease the eye if there is another condition means if the middle element just pointing 0 means here ever suppose the mid is here and pointing zero so we need to convert the we need to transfer the 0 to here and just increase the low and if the points made an event just hit the two then shift to the end and if the elements just pointing to the one if one then just increase the mid [Laughter] so I think uh that's the approach okay yeah fine fine fine uh I think here you have to uh here you are taking a low and you are checking with the mid so mid is in initial limit is zero now yeah made it zero okay so you are just going on with the mid and low will be as it is and zero and uh when mean is at uh zero fine so let's say key when we got 0 at the mid so you have a swap that will be the loop got it yeah yeah and when you have got two at the mid you have to swap that with the height hi and after that you are a decrease in the mid okay okay great fine same same is good it seems good so what is the time complex of this particular proof time and space complexity so if the if talk about the space complexity it is constant constant space that gives you the constant phase and if I talk about the time complexity and complexity then the time probability of this algorithm means we are just traversing from need 0 to and just so I think that time complexity should be login just give me one minute it means if I am traversing from the meat that's I think n means linear time complexity okay yeah seems good okay yeah same good can you just make a diagram on it just for the sample case a simple dragon yeah means okay let me give you let me give you a sample this case let's say your case is very simple it's just two one one zero okay let's make a dragon on it okay okay let's do it like this fine okay so if I write about the index means that 0 1 2 and please please Zoom the sheet for our viewers now okay so that's the element two one one zero one and I am writing the here the index 0 1 2 3 4 so at first we talk about the lowest pointing to the zero and uh high is pointing to the the N minus 1 means here is the n represent the one two three four five so the high is pointing to the 4 and the mid is pointing to the zero so at first what we compare that if array meet zero but uh here aromat not zero so then after that we compare that array to yeah array two so what we can do right now just compare if array me to then just swap array high and array meet so now mid is pointing to the zero index and height pointed to the fourth index so what now we can swap the array high and array meet so just swap it one one one zero two okay so now just right now the condition is but now is zero and if I talking about high high after the setting we decrease the high so now high is pointing to the 3 and now mid is pointing to the one no sorry me responding to the zero right now we don't ship the meat so okay after that mid is pointing to the zero yeah so now mid is here now we just compare that if need okay made uh zero okay I think uh there's a mistake means here after the increasing if High means after decreasing High we need to increase the mid right yeah that that was that is what I was just checking that is I have told you to yeah means after decreasing the high we need to increase the meat also so now maybe to one so now we are comparing meat and tando so now meat is the now yeah now we are considering meat is here means index G index one and the glue is here so if mid means that that's the compare that if array meet zero aramid means that's the comparing here aramid 0 not array mean two lot means that the mid again increase the meat so just increase the meat here and array as it is so the need to and after that meat is pointing right now here but again the array not changed as it is 0 to now made it three so okay now mid is pointing to the hair zero position but high is pointing to the hair so where we write the condition meet greater means mid less than high so we just need to meet less than equal to high so after that right now high is pointing to 3 and meat is pointing to 3 and then we need to compare this that uh if need and low if mid is zero then we just need to save the low and hit so if we save the index 3 and index 0 then we can write about the zero one one one and two now meet equals to 4 no there is no increase in the meat so that's the increase of low so that's the mid 3 but um so after that right now we are checking about mid 3 yeah mid 3 but uh made three one hour one so we just need to increase the meat so just increase the meat and whenever we increase the meat Mix 4 but the height is now right now pointing to the three so the condition not satisfied so just break the for while loop and we get the sorted form okay yeah I think we have got here okay great fine change good sounds good let's let's now move towards the next problem so yeah this was this was fine uh let me just add the next problem on the seat okay the the problem is really simple the problem is that you have to detect a loop in a linked list the problem statement is simple actually and you have to detect a loop in a link place are you getting the point where I'm writing yeah you got it yeah this is what we have to do let's let's take example let's take an example let me say the problem statement to you that will be more okay here's the produce segment I have given just just scroll down to the next page the task is to use it foreign let me add a image for your better understanding okay yeah as you can see I have added my image too yeah you can you can see that there's a loop in the link which means there's a bracket after one two three four five are the five is again three four five again two is yeah we have to just just detect that whether there is a loop or not okay so um in the first okay yeah so at first means there we are given to the Head means head is pointing to the hair just we need to detect means let me also share the problem statement to you that's completely fine if you will write the pseudo code there because yeah so first approach I'm thinking right now yeah that is okay at first at first write suitable here or just go to the code yeah what do you want so you want me to personal explain the logic you can yeah we can move both into logo so at first if I talk about the approach means first approach in our in my mind that's we can use here the hash map means what the hasbab property says means we can use here it means I am coding right now in CPP so we can use the map or on order map so what is the map or unordered map means concept says that there is a key or value pair or we can use the set also that's not better but we can use the hash map here and we can store the node means whatever the link is node we can store in the key portion so in the whatever what is the property of has to have saved that has web said that the key can be one only at once time means foreign so we can just uh break the loop and just give us so if I talk about the pseudocode about this so we are given just uh suppose we are writing this to know the head we are given the head so what we can do while hit not equal to none means we are writing that we are iterating the new list throw over this means we just iterate and uh up to now the head pointing to the none so we just iterate and here we can use one math on order map we can use the another map for thunderstorm publicity and in the store that and uh after entering after entering the for one Loop we just store the map of it means we just store the node in the map and after storing this after store the map just increase the Heat and point to the next pointer so how can point we can point to the means head to head to next and after that okay at first we need to check okay how we can do this but at first the oil enter in the loop first time we need to check means in the same node the if there is any node pre-exist or not if three exist then we can say if there is a loop and just return true and if there is no no existence of that the node then just go ahead so at first when you enter the one Loop just check if the node is exist or not so for checking the node exist in the unorder map we can just use the if map.com ismap.com head greater than 0 means what we can say the head means this node exist already exist so what you can say that the this is the true case means there is a cycle and if it exists to return true just return to if not exist then just go ahead just store this load into the map and after storing the head means this node into the map just increase the head to the next pointer so that's the and after when the loop end just here return the first so that's the basic means approach we can now code it in the gx4 GX so there is a there is a question that uh we need to iterate through the loop so here we can detect the unorder map I've got it on for the map and in the map we can store the as a key as a node means we can total node as a key and thus integer and just write the map variable right now and uh after that what we can do we can just iterate through the wild uh head north people to learn and after that we can do right now just if check map.com head greater than zero then we just return true or just simply go ahead and store the head in the map snap.com head greater than zero then just return true and just store the head into the map and just increase the head to the left pointer just this and after that we can just return first hope you got it so if we compile and run then yeah output true then we have to just submit foreign yeah okay great so is there any other approach for solving this problem without using any hazmap means if we have to do it you know by the way first of all tell me that the complexity analysis is called the time complexity of that the big open the time and if we talk about the space complexity we are using a map and just iterative trade if there is nothing Loop then we just store the everything means all load so we can tell the space complexity also we go and store the all node if they're in the rust case scenario if there is no node no cycle present in this is there any other other approach how we can solve this particular problem means if we talk about the another approach then there is we can use the tortoise method like store first pointer approach we can do okay can you please give me some some Basics you record all the expression for it how we can use the totals method yeah means for daughter's method just go here foreign the two pointer like slow pointer and first pointer that pointing to the first node here suppose the means two pointers just pointing to the hair and what we can do that the first pointer moves two step in one iteration and the slope pointer moves one step in one iteration so if right now the slow and first pointer is here then in the next iteration first pointer move here and in the snow pointer move here and in the so this process we can do uh slow and fast forward there is nothing cycle then we can do this just to increase yeah if I write about the pseudo code of this means uh just take the okay then just check means uh why we write the condition means first to next we why we not take the first one first not equal to none we just write first to next not equational because the first is Moving Two Step Ahead so if I want to access the first to next to next so if there is a null means uh if first is pointing to the end node then we just uh write two links we just access want to access the first two next to next that is impossible so at first we need to check the condition if there is first to next to next first to next none and also you can check the foreign the first variable for two times because if we not write the this condition first to next month then this is not possible then we can show a error so just we assign the first move ahead first to next to next and just look the slow pointed like one step foreign exist in somehow if it's slow then return true or is Africa return is the right pseudocode means in this or you can approach yeah yeah I think it seems it seems fine to me let's just quickly write the code in that problem according to and okay yeah I I can again please just give me some I'm not wanting a quote from you just just some hint from you that how we can also remove it this is what we have done for detector uh a loop in a linked list how we can remove it too I mean just uh just a basic uh we can say I just want a explanation from you or nothing so when we check about the means just remove the loop right yeah I mean so we were checking just like if you will open diagram you can see that there's a loop like one to two then three and four and five then five is again two so the the yes that link between five and two is creating the loop if you will see so how is it possible so if I think means just need to remove this so first yeah so first display if we remove this scene two step then over here first details yeah means uh just remove the first pointer in two step and slope wanted in one step if we talk about this then my pointer is pointing to at first here in one then we move the slow pointer by one step means right now my slow quarter is here and my first pointer is three so in the next step my slope order is in three and my first wonder is in five in The Next Step my slope counter is in four and the my first pointer is in three and in The Next Step what is my slow pointer is pointing 5 and the my first pointer is pointing to the five means here we can say we just hit a cycle so if we set the 5 to next none void then we can just remove the loop so if we hit here just go to the code if we hit the Queens first slow then we can simply put it down through and just set to first to next right okay uh yeah actually let me first get out of the viewers also the time complex of this set or twice is order of n because we are iterating and the space complex is a lot of fun because we are not taking any extra space so that's not here okay don't be confused yeah uh okay actually uh Amit that the the first approach which you have told of housing was actually was seems good and that tall dress it was also seems good but yeah that this uh the the next approach called removing a link looping link is is something which is uh not correct because this is not always possible that your fast and slow pointer will be on the last note only in this case it is fine that the fast and slow are meeting at the last node and you can say five but maybe if there is one more there are six nodes then they will not meet at the same point so for that we have to write down another approach to basically move that point into the last one so that that's that's another thing but yeah that that seems good whatever you have written is that that was approach that's completely fine what I was expecting and uh but the means the problem which was detect Loop and linked list is completely fine so now you can you can you can you can move to that is female don't understand yeah okay yeah great so now it's the time for the feedback so how was your experience first of all yeah it's great means it's the first time experience so it was a great session okay okay great great great so just a minute let me add a feedback for you can you again can you again but in the approach we might transfer the remote in one time okay maybe you are a traversing more than one time but that will be constant only at the order of and on uh it will be at Max two times not more than that okay uh Amit can you please again open that that seat yeah can you sort of scroll down yeah here is it so that's it that from my site first of all your coding the coding the first program you just got in in a quick way so I can give you eight or eight point five between that uh for the coding uh in the second problem also you got the both approaches all the thought twice approach and the hatching post but therefore removing the link list it was quite uh it was actually wrong it is not always possible that the fast sensor will be at the last but yeah fossil the problem was the technical link is and you got it really well uh so basically for the problems the first was the solid raise of zero one you have got the most efficient solution for it which is the three point solution so that was amazing and for the second also the most efficient solution was to two pointers which was fast and slow pointer and that was also what with that you have got okay after that for the implementation skills 9 out of them means the implementations were really good for all the two probes for the both the problem you have really implemented this nicely means uh taking the you have not taken any extra unwanted variables you have not taken any extra space you have just taken what we want you are not not taking an extra uh Loop or anything so the implementation was overall really good and if you talk about the communication skills I can say that your communication skills are really good means for each and every line you were writing you were explaining that to me and there was a continuous conversion between us means basically you are you are telling something to me and then I was getting it that was really nice means how you always interacting with me it's fine that way in between you were just some Sunday Hindi in English so just try to be in a in a same language too okay that was amazing how you are just that you are explaining each and every line that you are writing that was something which was good and that you have to you can continue I think the your real interviews too uh when you whenever you even your interview because that communication plays a very important role sometimes when even you are not getting the approach sometimes when you're not getting the solution of the problem but if you are communicating with the interviewer correctly if you are in a conversation maybe interview will give you a hint maybe uh he or she will understand you in a good way but if you are not even uh basically talking with interacting with him so it may be a bad impact okay so that would be the thing and overall it was good it was 8.500 it was a nice experience for me also for the first problem by the way it was really immunity I've got all the three approaches in a good way like the Sorting with order of N squared and sorting it and log n after that accounting sword and after that three-pointers recruits they all were very nice family so that's that's all from my side for me yeah your means just great for means just where we can stuck here you can just approach we mean she just help me so it's a it's really great experience for that yeah you've got to create great image so uh hope guys this particular session was also helpful for you guys so if you also want to be a part of these live mock interviews you can fill the form in the description also you can share your interview experience with us and for that you can fill the form in the description thank you guys thank you very much for joining this particular live thank you much thank you for joining us thank you thank you guys bye-bye and uh Happy coding have a nice day