Live Mock DSA | GeeksforGeeks

Key Takeaways

just check whether you can edit it or not all right so let me paste the first question yeah just read the question properly and then ask me if you have any doubts regarding the same okay okay it should be exactly k right yeah exactly if it's more than k then you have to remove the first k characters and then okay like if we have like four times so uh so can we remove like two then consecutively like recursively we can remove them frequency in an array or can be stored in math then we check whether it is greater than or equal to k then we remove that character all right so [Music] just just write the uh pseudocode for that approach or just take an example and explain your approach once like what type of characters it can contain it may contain only characters from a to z nothing else like only lowercase like to do this okay so uh you were going on with the uh current approach right so can you please explain the current approach completely including the time complexity in the space complexity you're talking about and after that we can move on to the optimize of course right okay okay let's give me a minute so that i can analyze all the things yeah like what we can do we traverse from left to right and for every character we push it into step all right so what was the time complexity of the space complexity of the knife approach that you discussed so you were going with the vector method as you discussed right initially was you are going with the uh vector method so can you discuss about that we can move on to the optimized method later on so string all right can you take an example okay let me give you an example let's see another example is the string given to you is uh so what would be the output for that and let's let's just do a driver for the same i'm not talking about the code let's just do a lagging uh is that audible now clearly yeah it's clear okay so i've given you an example geeks for geeks and just tell me what would be the output for that and also do a dry limb for the same i'm not asking you the code just do a dry run but the approach you're talking about like uh first i push like g in the stack okay then okay in the stack and then uh then third time if i traverse e is e then i check whether uh top of the stack is the same character like e is or not if i got the e then i pop it right from the stack then i traverse again i will check whether top of the stack is the same then i will pop it again for this because it is consecutive after deletion of e right okay okay just do one thing just do one thing uh let's say this is the stack you're talking about uh this is the stack and explain me the approach after each iteration so at each iteration what will be the stack contents okay first i push this first i push the g inverse tag right you may modify the given stack only don't need to write the entire stack again again okay then i put e in the stack right then again if i go to the e then i poke from this time right then again i i am on the g side right so again i check the stack but it is it is still containing key so i copied from the step now i unchecked s so how are you going to check exactly how many elements are there on the top for example in this case we had the exam k as two right so if i give you the ks4 and let's say let me add two more e's over there so how do you do that just think of some approach of keeping a track of the number of occurrences right it should be adjacent yeah consecutive so i can do like uh if first character i put in the stack right then i check the second character but i don't pop from this time uh until i got the different character next different character like this is a only so i will not pop it i will check from the e until i go to the g which is different corrected from me so i pop the e from this time so how will i exactly check the number of occurrences the frequency of the characters like it should be four right yeah it should be so but how will you check that one one character i will maintain like this only so [Music] yeah so one thing i can do like i count the frequency of each character then again i traverse each string and check whether it is adjacent or not like first i count the frequency of each character if it is like greater than or equal to k then check for each character for whose frequency is like for greater than in this example still not make sense to me just take the example just take the example and do a complete iteration of the given example let me modify the example a little bit for your benefit let's say yeah this is the string argument as so what kind of a data structure will you use for that simple character array like this one but if there is a like how many times he occurred so i increase the count and what would be your thought process of checking whether continuous or not i have to again traverse the like string that for two pointers approach i can do like first i keep the track of i here and j will i move on the j from that string if it is equal then i will take care of that like increase the counter and what's the use of stack over here then i stack stack will not work then like if it is like stack will not work here right actually because it is a stack will only remove the two duplicate characters so what will be the time complexity length of the string like first i count the correct frequency of each character then i simply sliding each character until i get the count and i have to check whether i have to delete or note these adjacent characters let me make the question a little bit clear for you i guess let's say this is a new string given here and gg is there then you have e or let's say i'm taking this subpart itself so when you are actually taking care of this part four consecutive ease you'll be removing this part right yeah according to your approach you'll be removing all these four e's at a time after this operation the string will boil down to four conjugated g's and then again you will have to remove these to make it resultant as an empty string how will you take care of this particular case so like i have the frequency area map frequency array so until all the like i have the in this case like you take the example like g and e so i have the g as frequency 4 and e has frequency 4. so uh i check for the like for one of the character is already removed like in this case he is removed from the string all right all right if you are having a k in between so initially you will remove after this your count will be g is 4 over here e is 4 over here and k is 1 right and after the initial removal you will have the string as this you'll still have four g's with you which is equal to equals to the given k i will minus that also in this case we don't have to remove yeah i know that but how will you actually take care of that particular piece right like like complexity may be a bit higher sorry like what happened is like first i check for e right then after removal of e i will again check off the map right what is uh if there is any character whose frequency is 4 or greater than 4 then i will again traverse the string if it is i am not able to remove then okay we end up the link all right i checked the map until i don't like i don't have any character which is greater than k all right so can you please uh write the code for this or let us first discuss the complexities let's discuss the complexities okay right okay it's obviously more than a length of this train but okay like yes okay so let's break the problem on the smaller part to discuss the time complexity uh are you using any extra data structure in your approach are you i am using but it's only constant because 26 grams not not space complexity is constant you wanted to use a map or you wanted to use a vector vector actually it's a constant only 26 characters because it's lower case only all right and what if you have to remove all the characters in any case in any case let's you have to remove all the characters then what will be the complexity like in this case also like all the characters i have to remove right all the characters at once then don't need to figure out like its constant time so now you are deleting length of the string from the entire string and you have an outer loop so what will be the time capacity sorry you said you are removing the entire string and the time complexity for that particular operation is o of n right and you have an a for loop above it and inside which you are going to delete that particular string am i right yeah yeah so what will be the time to see that like length of the string into you are given the string as eight consecutive pose and is also eight over here in that case will have to remove the entire string to return an empty string right you said you will be using a for loop with some conditions inside that you will be deleting this tree right and you're deleting the entire string over here okay but will be the time constant i just wrote a kind of a pseudo code over here to make things clear here now what will be the time complexity uh like in my approach like it is only order of length of the string only but i am like first i have to traverse to count the frequency of each character so there is only one connector so it has eight frequency right then then you will again be traversing through the entire exist yeah you will be checking for the frequencies and if the frequency let's let's consider the worst case right just consider the worst case in my example i gave you eight consecutive o's and the k is also eight over right in your second iteration you will be traversing through the given string you'll be checking for the frequencies and then you'll be deleting all the eight consecutive uh let's say the characters in that case don't you think there will be a nested kind of a thing going on over there because you're running a loop you're deleting characters creating characters how i am checking how to remove the adjacent like yeah sure if this thing is clear only right how can we count the frequency yeah that's clear but i'm not satisfied with the time complexity so and like it is in place only and this is string i have to modify you may use an extra string if you want to but that will only add up to the complexity completely depends upon you i don't know whether it's functional yeah like first time checking whether it is equal to that character no more which is in the map right we'll count that if it is equal to like k whatever we have assumed then simply erase that sub string okay so here it is you see you're raising that particular part in that same loop right yeah will that work okay in one loop like it's only for the one character like i have to again go through the whole character so two loops definitely it's like quarter of any square okay can you think of an approach better than this oh hello like we can do let me just give you a hint you are actually going on the right part when you actually discuss the stack solution but you failed to explain your approach you could have solved this question using stack in of n solution or off n approach so can you think of a solution using stack so i explain you like the approach using step so it was missing out the edge cases you were actually you're not actually considering the frequencies part is let's take the example as i gave to that time yeah let's consider this example i have selected this part consider this example and discuss your stack approach okay like first items so again i traverse e scan the e character then i i get the different characters so i put it from the stack g if stack is empty like and nothing in this stack so i simply push it into the string again i check the e again i check the e then it is in the stack so i don't do anything go ahead then i check the e like i have to again check this k part is i am not missing out right one second one second uh can i do like uh along with character i maintain it's frequency in this stack only but how will you do that you're going to the right direction but how you exactly maintain that frequency all right so you are going on to the right path now can you please do a dry run one again i see so uh initially i pushed all the characters with their light frequency right after popping from the stack then we consider whether it is that will again add up their complexity then oh yeah like first i push g and it's there count like one then after putting before putting the g at next c i check whether like it is a pair so i check its frequency so its frequency plus one if it is equal to k then i simply remove it from the stack otherwise i push push the frequency more than one right like g like in this case if i have k equal to 2 then if g is like 1 initially i don't put the g 2 right i have the g 1 so i pop it from the stack to like take the top of the stack and check whether its frequency is one plus one like two equal to two so i pop it from the stack and go ahead with max current i can do that okay like okay so so just let's move on to the code now i i understood your approach makes sense to me let's just move on to the board now oh uh so uh so you just go through your code i can see some of the mistakes here some tactical or logical still i can see some of the mistakes just tell me one thing the first uh condition that you gave in the if statement what is the meaning of this part or why are you even doing this i'm just considered about the stack is empty right you're saying i am always checking the top of the stack rather like not figure out whether it is empty or not in this case okay but in this case for example in the string you are extracting each and every characters using this for each book right yeah yeah after that you are checking whether the top element of the stack and in that top the first element is equals equals to c or not there can be a situation whether the c is not equals to uh the top element but the k is equal to equals to uh the given occurrences right so in that case you will have to pop it but if you are putting this condition in your if statement the entire condition is becoming false and you're not you're not popping the element in that case but i am checking something like plus one frequency now so in that character only if i quote that match then only i can remove them otherwise it is frequencies less than k still not make sense to me because you are still missing out some of the edge let's do cases or can you once again explain what you are saying like for example in the if statement we are checking whether the top of the first element top of the stack and its first element of the equals equals to c or not what is c c is the extracted character from the string at that particular instance right you're checking whether it's equals to the top or not there can be some cases when the c is not equal to the top element but the frequency is equal to k and in that case you are putting an and over here so the entire statement is becoming false right when they're trying is becoming false you're not popping out the top element over there so you're missing out on some of these cases like i am thinking whether you are saying that like is it possible like you have an example for instead of this part you could have directly check whether the stack is empty or not if it's not empty you can simply sorry push it to the stack what's the use of this statement and then you're checking this you're actually missing out on many edge cases over here okay so what i believe we can move on to the next question let's leave this question over here shall we yeah all right so a simple question you will be given a linked list right and you have to find the starting point of a loop in a linked list okay so okay let's take an example yeah just take an example yourself and find or derive an algorithm how you find that starting point of the thickness now starting point of loop of the loops like uh and this i can do like suppose there is a loop so i can do using the like i can use a map data structure here can i do like i am putting every like link list address and their corresponding index i can say like initialize the index with zero i can like first i uh initialize the index with zero like for for the first node i have all right so uh well i traverse the link please list until i get the repeated index like everyone has a unique index right so i first first i traverse the first notes i put that note address and their index like for node address is something and index is zero right then again i traverse the second node and put that address and its index increment that index and put it in the map then in that way i go and go and reverse the linked list until i find the same address again right so that like in that address that index is repeated like that node number is repeated is it fine okay so let me give you an example just wait for a minute one second let's see you have this linkless with you is that visible clearly yeah yeah okay let's say you have this given linked list with you and now explain your approach again okay like first time right first consider this am traversing from this so let's say its address is thousand right so i put it into the map and its index may be considered as one okay then i traverse the second node and its address is two thousand so index uh and implement that index and put it as two second node means index uh denotes the node number 5000 and this is a starting point so i found in the map that there is a address 3000 so third node number we can return so you are using an extra data structure over here so can you think of a solution where you are not using a data structure i just want the space to be a constant space okay space i like there is one of those like we can use two pointers here one is also in 1000 then we move until we get equal to and what we can that like one pointer we can move one two steps at a time and other pointer at the same time will move one step at the end and are you understanding so yeah but just write the code once decide the code once and then i'll ask any questions and we will move right step side will move like what we can do like first we detect that so to return the starting point of the loop first we have to check whether there is a cycle or not then only we can return so for cycle checking we can also do using two pointers like that so so hello yeah so what i'm thinking is like i first check whether there is a cycle or not right in the linked list so so i am using the two pointer uploads like one pointer and two pointers both are initially here so i will move uh one pointer two steps ahead at a time and one pointer at a uh one time so uh so first i will check whether it is not null so it is simply written but it is not having any cycle if it is not so if it is normal so we increment one pointer by one first one step and then again check whether there is a loop or not otherwise again we increment one loop one pointer and check whether it is a loop or not in that way i continue to track whether there is a cycle or not all right then how will you find the starting point of the loop then you are you are finding whether there is a loop or not but the question is yeah i detect the cycle then what i am doing is i fall into the like somewhere in the somewhere in the cycle right but uh in the code you wrote just now you're returning from there right whenever you're finding that point where this cycle is there or whether the two pointers are meeting each other you're returning from there and then you are again coming back to the main function that is the function uh starting point rather the arduino cycle so you are again yeah you're just getting the boolean point right whether it's true or false whether you are having a cycle or not sorry so instead of boolean i can return the point like here i put the cycle where these two pointers are equal okay so in that case like they are meeting at this point four so i return the fourth address yeah then uh if i again traverse like two point two poles then i guess i point to that if if the pointers are meeting at the point four but that's not the starting point of a linked list right starting point the loop of the linked list how do you find the starting point then two pointers are pointing here so again i'm like one second anyways can you discuss the time complexity here then we are actually running out of time demands so do you have any questions for me definitely like i thought like i am not okay so the first and foremost thing is that whatever you're thinking in your approach right whatever is going on in your mind the approach or the time complexity just keep on speaking out everything like even the approach even the thought process that you are going on just don't sit idle in the interview but you are doing on maximum time of the interview uh just avoid that because it becomes monotonous for you as well as well as the interview and network actually wants to understand the thought process or how are you actually coming on to the optimized or the solution that you are providing right so that's the first one that i would like to give you second is that the first question when you were discussing you were actually switching on between the two solutions time and again one time you were going on to the vector approach the next time you were coming on to the stack approach and so on so just provide your brute force approach first discuss the time complexity discuss the space complexity if the interviewer is not satisfied with the approach if he is asking you to optimize your solution then move on to the next solution initially start with the approach you're talking about be confident be uh on the safer side to complete the approach and then move on to the next of course this is the second part third part is that just go through the fundamentals and time complexities ones right any more questions you may you may turn you must switch off the screen sharing right just be consistent what i recommend to all of us or all my friends all of uh to anyone who asked me the same question the answer is that be consistent don't uh being consistent doesn't mean solving the same question again and again being consistent means learning new things in a consistent manner consistently learning new things try try solving some harder questions because when you're solving a hard question you actually cover two to three concepts at once and for all the viewers out here if you want to get featured in any of the next live mock dsc i shared the link once in the comment section and or is you can move on to the description box you may find the link over there and any last questions thank you thank you yeah not an issue thanks lord you may drop off now thank you thank you thank you