Live Mock DSA | GeeksforGeeks

Key Takeaways

thank you hi hi 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 yeah this way don't delay enroll now Geeks learning together [Music] hi hi are you sure you can prepare for product based companies through this course yes sitting at home no way yes way don't delay enroll now Jake's learning together foreign [Music] hello everyone and welcome to Geeks for geeks myself of University I am currently working as BSA Mentor at Geeks for geeks I am a five star at code Chef expert at code forces and ICPC regionalist today this is a new life for our series not like like DSA and we have September with us hello satyam how are you hello I'm fine sir how are you sir yeah I am also fine so September before starting with the interview your voice is breaking so a bit thank you hi hi 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 thank you hi hi 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 foreign guys in the in the chat box that am I now clearly Audible and visible to you all just a pleasure in the chat and we'll just move forward with our session okay fine so yes attempt uh so yeah before starting with the interview let's first tell me something about you Institute of Technology and science I am currently in my fourth year I have keen interest toward data structures and algorithms I have solved more than 400 questions in gfg and Lead code uh I have added two internships as back-end developer and two pure based startups currently I am holding two offers one from jio and one from persistent and that's all about me so can you also just tell me something about your projects which you have built yeah I have made a calendar based uh web application in which it almost look like Google Calendar works like Google Calendar I use node.js for a back-end development in it I also use express.js for routing in node.js and we have used several you know functionalities of node.js to implement the calendar-based web application and in front end we implemented HTML CSS although and you know styling and that's all JavaScript also jQuery for you know front-end things okay okay great yeah Santos we I have written a radio comment uh we will create a video on pre and cap it's okay fine okay so set them let's now start with the thing and uh I have shared your document in the chat okay so can you just please uh share your screen and open that document so that we can start our interview yes uh the screen is visible sir yeah it's it's visible uh also satyam I am also sharing uh travel link with you okay you can just open that problem uh too and that is going to be our first problem fine so let me just explain your uh you can also login I am just I'm saying that you can you can log in at your platform and it will just start it's my okay just take your time okay you can feel it no one is saying that nobody no no problems okay okay so yeah I hope that now we can start so yes so this is a problem so the problem is check if history is rotated by two places or not also guys don't just Spam the chat I have a radio comment please don't do that fine okay also okay you have to just stay on that page only don't just move yeah okay so the the problem is that uh check if string is rotated by two places or not so basically we are given with two strings A and B okay the thing is we have to check that if we rotate string a with two places or string or string a with it means right side two places or left side there are two types of rotations now in that case can we achieve that b or not can we achieve that bee sting or not this is the problem yes have you got that so if you can just open a seat I'm also giving you example just open that seat yes I do yeah so this is you can see here that if uh the string is let's say Geeks okay so after doing two right rotations or two left rotations we will get uh I can just say you that all the will be at the right so it will be like this and after two left foot is right or distance uh it will be like this so you again with a string B you have to check that whether after two right notices or two left rotation of this string a is that b is still possible or not this is what you have to find okay okay yeah so you can just first of all take your time to understand the problem and then if you are just clear with your approach you can tell me the approach in this thing okay so I've got to copy and pen with me sir when we left rotate the string first the zeroth character G goes at the end of the string and then the second character goes at the end of the string am I correct in left rotation yeah if you are doing two left rotations basically yeah in one left rotation all the characters are just shifted left one one and the first one goes at the last position this is what we do okay uh yes sir I got the problem yeah okay so how can we approach this problem in this case sir I think yes I think sort of it's just the you know we're just playing with indexes we just you know uh removing element from the front and adding it to the back we are not doing anything else to do that and I think we can just you know match the character with indexes like first we start from this e you know our second character e second index e then we match it with the zeroth character this K with this K and this s with the you know second index s and when we have you know done length minus K suppose if the rotation count is K we'll iterate first from thin string dot length minus k you know you can write it you can write a reference yes one more thing sir uh we have to do this two times basically for left rotation there is there are chances of either left rotation or right rotation right so there will be two different approaches I mean that's what I think I I'll first check the string for the left rotation then I'll check if it is left rotation then no problem but if it not if it is not a left rotation then I'll again check it for right rotation okay um first I'll uh create a Bank minus okay suppose it is K equal to 2 here we'll create a remaining variable which will be Str dot length minus 2 minus k now I've got three in rem is equal to 3 in this example now suppose given string B is e k s g e suppose this is the given string now highlighted from 0 to 3. okay and I'll check okay I'll keep checking ith character to K plus I H character from the first string okay all right I'm gonna write it I'll match with 0 plus b you don't have beetroot so means you are saying that your remaining will be length minus k and yes you have got that string B then just repeat that thing string B is given string okay fine this we've got two straight I just supposedly write that this is the B string I mean it might be something else but in this case I'll suppose that this is the string B fine fine okay I compare zeroth of sprb with a zero point with K plus zeroth of Str a basically you can see if it is stringing and we'll keep uh iterating uh both the strings like I will start this string from here and this is string B from here I'll keep on matching until K is less than okay okay the E matches with the first e k matches with with the this k s matches with this so I've got to you know first thing is done I have compared the non-rotated part e case which is not rotated so I compare the non-rotated part the remaining is GE now I will start from K which is equal to 2 plus 1 that is we I'll start from 3 this is 3 and this is 4 I'll compare it with the remaining characters remaining First characters of the given a string I'll do it okay okay so uh just just let's take another example and uh just tell me the thing because what you are doing we are first rotating a and the string a and you are saying that no no you are not rooted you are just comparing the indexes yes can you recite the pseudo code and then we'll move forward to the uh to the code part but further code uh RAM will be Str auss it's a DOT length 5 minus 2 that is three quarters minus 2 that is three thank you okay here Plus I equal to equal to uh [Music] foreign yeah it was Amazon and I'm just so let's do this for this so the value of K is always 2 9. uh here giving K is equal to 2 always you have to check that if this thing is loaded by two okay sorry I have we have to check if the string is rotated by two or not only two right you can you can again read the problem that's not a case regarding again with the problems even though yes I think the code will still you know yeah you're right that K will always be two you're right it's a uh so should I keep on doing this you can continue [Music] this is Amazon okay I'm finished okay so um so you have you have compared the if character of uh a plus is character of string B foreign [Music] that's what I'm saying nothing okay okay fine should I you know process with this yeah you can just continue it's okay I'm uh you know so finding some you know incorrect but uh can I correct this obviously sir you can do that uh what what I'm saying sir is that I'll take first two characters as K is always true it's a good thing for us we'll compare first two characters with last two characters okay because you know rotation will go if it is a uh what it is a left rotation right if it is a left rotation we'll compare first two characters with last two character if it matches then we will compare remaining characters with remaining for character you know okay okay yeah fine fine fine it's your writing now you have got the exact point which I was just expecting explanation yes yeah so that was the again again that was the approach which we were just thinking of so uh we can just move forward with the code part I just wanted how you are going to implement should I code in gfg sir yeah and I compiler only as a GSG compiler only okay why are you taking into cases okay it's okay just to you know sort of okay it's okay yeah comparing two characters foreign [Music] okay so you are checking that if the first character of str1 is equal to first character of CR2 uh okay okay fine first character with Ram plus one okay n is time complexity of and fine okay but what is an N is not given here what is n foreign foreign character and uh first and I'm pressing okay fine fine it's Ram plus one yes sir first character I mean we have got two you know two characters rotated so I will compare first character with the obviously second last character and that character to the last character okay and you've got this we have highlighted from okay to the length and here I write it from zero to the end so I have a character completely if you're having difficulty you can just skip the code part you will move your next problem just let me take a few minutes okay yes take your time Google generation [Music] second last character yeah if it's not equal then um let's fall uh so it's given that it will be left rotated or right rotated or it may be any of those any of those case you have just checked at it it should be rotated back to only at the right or left that's just not the case I just wrote the code of left rotation okay and you know just increment the right quotation foreign [Music] and let's see how good okay in Java sorry foreign [Music] [Music] [Music] so I think that when your eye will be at the last venue means Str dot length minus one in that case that I plus K that 43rd line will give a error now means I plus yes yes you're right so now that that line is going out of bomb yeah let me I have to you know decrease the yeah yeah yes I think it's working correctly so for Amazon at least okay fine fine I have to check for right rotation also okay all right fine fine okay okay fine so this is what I was just expecting from you uh okay uh now let's move towards the next problem okay and that is going to be just uh I just want that how you are going to approach that problem and that is based on linked list okay so let's move towards the next page okay the next page of this document okay okay have you got my contact yes I got okay okay so the problem is detect a loop in a lane place you are giving a linked list let's say I'll increase this one then two then three then four then five and from this 5 we have again we can just write it like this getting so from this five we again have a uh let's say here's the six one more six this is the thing how we are getting so if I just again open the problem it means I don't want you to uh actually code this thing okay I just wanted to explain it in a good way let me explain it with the help of a problem okay that is what I think that you will understand it more clearly so this is a I have I haven't certain uh images if you are able to see okay so I can see it so this is how you have to get the loop so you can see that there's a loop present this is from one then when two run three then four and five then again two this is a loop you have to detect this Loop that whether a loop is present in your linked list or not so let's assume that I have given you a function Okay so let's assume I have given you a function the function is like uh Boolean and a function is detect blue in that function I have given you the node of the head of this link okay you have to tell me how you will detect this Loop in this link okay so I think [Music] something to 4 is 4.5 okay so I think so we are visiting you know some notes again and again because of this Loop in linked list I can I think you can use a hash map of nodes and Mark yeah or hash chat of nodes and if we visit any node more than once then this means there is a cycle in the linked list but what if there are but how you will for example for example in place of this uh let's say that the the loop is like this it's not a it's it's not a loop it's like this then also we have one two times then also we have one two times maybe they are duplicate values then how we will check for uh I don't know yes I I will in hash myself I will create the node as the key of the hash map okay okay so means you are saying that uh you okay so you will create a hash map and so what will be the time complexity and space complexity for that time complexity will be so big of N and we'll use a on Space complexity for you know storing all the nodes okay okay can we optimize this thing can we optimize these things can we if we can optimize the time compressor space complexity whatever we can optimize the time complexity from osr I mean can we perform this in constant space yes just a second sir I mean I have to dry run one or two things you can take this example you can take other examples too thank you guys you can also tell me that what will be the optimized space complexity if we will get the optimize solution okay and guys okay how many of you also knows about how we can detect a loop how we can find the length of the loop and how we can remove the loop so basically this is the flow of the problem which I am going to ask okay so let's see how how we will move and I hope that many of you just know this thing so [Music] um uh I think we can use two pointers okay two two pointers starting from the head of the linked list and we'll start we'll you know move one pointer uh only one node at a time and another pointer uh two nodes at a time okay okay so candles please explain that thing so let's let's just Define this thing in other way because the diagrams was a complex set let's see that the node given course is this it's one two then three then four then five and then let's see the result through again assuming this two is there this one only it is there no this this type of thing is there okay yes getting or not yes I'm getting it means if you just open the diagram so I've just replaced that diagram with this language that too is again repeated from five to four so now how you will Implement that whatever you are saying for the two point is approach how we can Implement that here uh sir I'll make two pointers uh I'll name them pointer one and pointer two I'll start both of them from the head uh pointer one will move uh one node per time per iteration and pointer two will move two nodes per iteration so supposedly both pointers are at one then pointer two in the next iteration pointer two will be at 3 and pointer one will be at 2. now in the next iteration pointer 2 will move from 3 to 5. because it's moving two nodes per iteration right but pointer one will move from two to three now we've got a pointer 1 at 3 and pointer 2 at 5. now in the next iteration 5 will move from 2 to 3 again because there is a cycle so pointer fast pointer is at three back again at three and slow pointer is at four fine now in the next iteration there is the that's the gist of the you know equation whatever this is algorithm Maybe we'll move from four files slope pointer will move from four to five and fast pointer will come from 3 to 5 and both the pointers will be at the same point all right so what does what is the importance of this uh the significance of this is Sir that we have created two pointers one for pointer is a fast pointer and one pointer is a slow pointer if we are iterating a pointer uh fast pointer two nodes then it should reach the end of the list before the slow pointer right it should reach the null null point which is the end of the linked list and slow pointer should reach the end of the list list uh after the first pointer reaches the end of the list but the meeting of both the pointer shows that fast pointer never reached the end of the list there's a loop there's no end of the list yeah there is no end that's why fast pointer is moving at the list again and again and is not reaching the null null pointer which is the end of the list and slow pointer also reach the same position which means there is a loop in the linked list okay okay great there's also one more uh phenomena there's also one more thing where fast and slow pointers are used some other cases just tell me some other ones just tell me one other case where this method of fast and slow boundary is used yeah sir I think you know when there are more than one occurrences of number as far as number in an array uh we we can use this approach of fast and slow pointers approach uh you know we can in every how we can uh yeah okay let's just focus on linkages that in linked list what can be another thing where we can implement this thing tell me okay so for getting the uh suppose the length of length is 10 we can iterate a fast pointer it will reach the end in five iterations and slow Point uh and slow Point uh when the fast pointer reaches the end of the necklace the slow pointer will be at the mid node of the link list exactly exactly so this is exactly that we have got to set them that when so this mid pointer and fast pointer phenomena is also used to find the mid of the link the thing is that when we will start from a starting point and let's say that there is no Loop in the language in that case what will happen is that fast pointer will go at the last of the link phase but the slow pointer will be at the middle only so this is the another phenomena where this particular method is used of slope under and fast pointer okay great so shut them uh let's just start with the Sudoku yes okay so I've I've written the function above that is while fast hello we're asked is not equal to I am going to buy the do while Loops are because you know I don't want fast and slow you can also write it in uh give the ID if you have any difficulty otherwise you can write not an okay so you can continue no problem let's continue no problem uh fast equal to fast dot next and there is [Music] always check if another one and after the loop I'll return to the iron I you know started both the pointers from head and every at each iteration I um move forward fast pointer by two nodes and slow pointer by one node if at any point slow or slow pointer or fast pointer becomes null then this means this means there is no Loop in the cycle in the link list okay yeah I think I think that this code will fail for a case for a case for a corner case can you just figure it out there will be a I think syntax error is exactly same yes there is an error if there is no next node of fast then the its next call will be you know null if uh dot next is not equal to net and only I can improve this exactly exactly you have got it you have got it yeah [Music] you can also place that second condition of slow that also inside that yes I mean it will just you know improve the equally fast um that's what you find that that is what I I was saying I was just saying that if you will scroll up Scroll up yes so you will see that that slow is equal to slow dot next that should also be inside the bracket of that condition so it will be easy that both of us going at the same time so that it will be very easy okay in a perfect circle inside the files.next oh yes if there is no next or fast then there is no you know Okay so now I set them uh let's just change this problem a little bit or just don't change change it just add one more thing to the other problem which I am asking you let's see let's uh see that you have to find the length of this Loop if you will just figure on the we will just focus on the figure this this code image which is given to you yes if I just ask you what is the length of this Loop what you will say what is the length of this Loop four four four yeah there are four nodes in this uh in this cycle that is what you have to say so exactly so for that thing I have to start from from okay I am not at four I'm gonna find this I hope that you have got the problem you have to find a length yeah yes I got the problem here [Music] just a second sure four five and then again to I went to four also guys just hit the like button I'm not seeing much likes there are 60 students watching now so I'm expecting the likes to be at least 100 yeah code hacker that duplication of a number doesn't effect because we are just checking the loop nodes should not be duplicate the value of the nodes can be duplicate it's fine we are not comparing the values they are coming in the nodes okay I think uh sir uh the moment the node where both the pointers will have been met then I'll re-initialize one pointer to the head again okay yeah uh supposedly slow pointer will be re-initialized to 1. and then I'll again start this uh you know traversal but this time I'll not uh move a fast pointer two nodes at a time I'll only move it one node at a time okay yeah so the moment okay the moment these two pointers will meet again will be the starting of the cycle I mean that's what I can uh draw from this question supposedly we met at five yeah supposedly we met at five then I'll re-initialize the slow quarter to one then I'll again move from five to two and I'll move from one and fast pointer will move from five to two and slow pointer will move from one to two and at two fast and slow pointer both met again this means that this is this might be the starting point of the cycle this might be the starting point of the cycle and after I have got the node where both the pointers have met I from this point I'll only move one pointer I'll not move both the pointers I think I think that the approach you are saying is something of when we have to do to remove the loop also for that approach we have to just reach the starting point of the loop that is what we have to do when we have to remove the loop but uh certain thing is that for doing this thing we have to find the length of the uh before doing this thing called doing this operation or starting from the head and then just going uh one by one we have to find the length of the loop we hold a processible to that connection here you can see that the length of the loop is five and the first pointer will get the head and the second one is at five so it's just a coincidence that the difference between both the point is just four you are getting the answer but but maybe if I will just say you that take some another test phase then that will fail yeah yeah your life's getting you're right yeah so but uh what are things are one more approach I can think of is uh if I am inside the if I if both the pointers have met at one place what I can do is uh suppose with their you know met at four then I'll uh iterate one pointer from form that is one pointer goes from four to five I'll increase the loop count as one size of loop then 5 will go to 2 I will group the increase the size of a loop two to two then two will go to 3 then 3 will again come to 4. the in this process I'll increment the count by four times so maybe that's the length of the cycle okay okay so can you just please uh Implement that thing but it's possible yeah I can do the do it in this one so maybe you can you can write down a new one otherwise it will be confusing Okay so yes you know that f is equal to head foreign [Music] this is the code for cycle sir and one more thing after I've got the cycle if I'll take here if fast okay if I'm here I'll do this thing and return true I have to give it five five sorry while I'm increment count every time every time and when when the fast and slow becoming equal again then I'll stop the stop this while loop and I'll simply print and this is the code for I think okay okay I don't incremented fast equal to okay find something fine so means you are saying that you will have your fast and slow pointer inside the uh inside the loop basically and then what you will do you will just take one of the two pointers you are taking the password and you will just iterate it till it will again go to the skill now this is what you are doing okay okay okay fine uh satyam I think that it's fine for uh uh about whatever I want to want it to and it is correct yeah it is it is fine it is fine it is completely fine so you can you can okay it's fine so certainly you can again move towards the steam system it's okay fine so find September so let's talk about before going to the uh okay okay swarn it and uh yes it's it is not possible now to take any more question because we are at a time in this going on so it is not not possible so okay the thing is uh so I I was just figuring out to ask you some problems and the first problem was something interesting rooted by two places so it was something like that I was expecting that at that solution probably maybe you you have told me that say that you have to first rotate using a rotate function or something like that but yeah you have just pick up that point that you have to start from the I plus k at index and that thing that was uh something amazing which I I want to speak now because that is what the space of my solution is not taking an extra space and that is why Europe the code was of or spr men whatever them from the string that is what that was a time complexity and the space complexity was just uh constant of one okay fine and similarly if you talk about the uh the next problem which is the the loop problem so first you will just continue between the half mapping and let me just tell you that that is not uh acquisition solution and that is not expected solution in any case that that should not be taken that has nothing uh the second in which we always thought of that fast and slow pointer and then when I asked about one more use of faster that was the middle of the link is that is just got it so it is it was also good uh the thing the next thing which was the final length of the uh for the loop maybe there there you were just confused between that removing the new yes and detecting the loop he was just confused with that I was just also thinking of asking that question to how to remove a linked list uh and uh but but you you have already told me that the pros that you will start from my start and then and so basically uh folder viewers also this is a very important question this question is are then more than 10 companies you can just check that this problem and the gfg bulletin I'm just saying the link with you all okay and there are in this problem contains some several sub problems too the first problem is how we can detect a loop the second problem is how we can deter the length of the loop how we can detect the starting point of the loop how we can detect the how we can remove the loop there are some three or four sub problems involved in this problem so it's a very amazing problem okay okay guys uh okay September so now uh this is the time for the this is a time for all the feedback session okay just a minute okay September so you can just again open your tab of that seat yes you can just scroll down I have written a feedback okay in the fourth page I think yeah so if we talk about the coding oh accordingly if I will just read that coding skills of you so it is something that yeah you are you are able to implement a solution sometimes you got confused like uh when when implementing the first problem you understand take them then from which index you start what is the K and that's that is what this country is about maybe your the problem is not firstly clear to you clearly okay that was the thing but overall it was uh would I will let you some four out of five for this okay for a coding part now if we talk about the implementation part so yeah how you are just thinking the approach how you are implementing it was also good things that would support the following and mostly our second problem the approach we should have thought for like the fast food under a solo founder you have implemented it in a very good way that is also what which is good in this case so I will just also rate you four out of five in this implementation file too if you talk about the communication part so communication part is something which is I can say is quite weak for you so because the thing that if you will just observe one thing when you are just uh thinking of approach or when you are just writing something on a notepad there was a break-off connection between us okay because you were just thinking in your own and then just coming up with the solution always try to just be communicated means uh and also by regular code when you are adding a code you are not trying to just communicate with or just saying everything I was just asking you and then uh so each and every one before in sliding uh or while initializing while creating a new variable or something like that you have to basically uh tell that they are what it is doing and also try to write comments and that things through here now so that is also something uh that that it's to be considered from that is a feedback from my side sector I hope it's fine yeah for it for that I I will just give you some three out of five because uh and that you have to make something that you have to make your communication and some uh that connection between you and interview or something good okay yes overall if I will just yeah they use it it is good and the overall rate is 3.5 out of five so it was a good experience for me uh interviewing you and I hope that you have also enjoyed this particular Journey uh in this particular esteem and I hope that you have learned something new uh here and uh yeah yeah guys so you can apply you can apply shortly for the this interview the link for that form is given in the description you can just fill out that link and you can and using that you can apply for this particular live mock base Center okay okay uh September so I think that now you can answer your screen it's fine and you can again move yeah so yes thanks for any feedback for me no sir you're good thank you for interviewing me sir yeah sure it's what is uh it was also a great experience for me interviewing you and just just that feedback from my side at communication thing that you have to just make yes okay okay great guys I hope that you all have also liked this particular stream if you have like this team just hit the like button and subscribe to the channel for more such uh amazing uh particular videos and Such live streams great great code hacker so okay yeah enough you can apply using the code this is given in the description interviews every week on Thursday on Friday and Wednesday so we have some this type of item that twice a week you can just check it out in the in our ideas for YouTube channel okay and uh yeah so someone's asking about the three series and other topics for uh SDC so for SDC we are having our four hours live streams on our gfg practice Channel you can also check it out you can check it out of the gfg practice Channel you can find out the SD seed Series where we are solving the complete as we see it means the important problems of SDC in that particular time we're gonna check it out okay thanks thanks for joining uh okay guys then thank you uh have a nice day happy coding and thank you