Live Mock DSA | GeeksforGeeks

Key Takeaways

[Music] [Applause] [Music] 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 [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] foreign welcome back to Geeks for geeks this is another life session for mock live dsv myself I am a VSA Mentor at Geeks for geeks I am a ICP citizenist a five-star at code chef and the expert at code forces today we have suryakant with us hi sorry Khan how are you oh it's my voice yeah I think you have some Network issue you can just take your time and correct it no problem okay guys till then just I hope you guys are also excited for this mock interview also if you guys also want to be the part of these live mock interviews you can just fill out the form which is given below description box and you can also get a chance to be a to be a participant in this type of mock interview series at Geeks for geeks sure so we will start in some minute yeah I'm connected back uh my audible yeah yeah now your audible it's fine so are you excited for this yeah yeah I'm really excited like on live stream even until yeah but yeah okay so just so you can just tell me something about you okay so hello everyone uh myself currently I am at uit Chandigarh pursuing ambassadors of Engineering in computer science and currently I'm in my fourth year and I have done some web development and I was also doing some company programming [Music] foreign one of my major projects was an nft based warranty system uh can you just please elaborate more about your projects yes what do you have uh we developed a web application that was based on blockchain which helps uh you know e-commerce sites to create nft of their products and that could be done uh you know that could be then used by the seller to verify the product details and other stuff and also that can be then used by the users to you know or find the authenticity of the product and also the uh then further it could be used for the ownership verification of the Border so that was the project okay great it seems great uh so uh let's start with the interview so I hope you are ready so I have the sale uh Google doc link with you yeah you can just open that document and Screen the sale the screen so with my screen is it visible in this case yeah now let's finish as well okay can you please just also Zoom it out so that viewers can see it completely just zoom it out yeah oh okay fine yeah now it's completely fine now it's completely fine yeah it's great so okay so first uh the first problem is that I'm just writing the problem statement here only okay so this is the problem uh sorry Khan the problem is that you are given with an array of any positive integers and you have to reverse every sub element whose size is scheme so the thing is that let's take a sample case Okay so the sample example is something I am just writing here this is the sample example you can see that the value of n is 5 and the value of K is 3 that means you have to reverse every sub array group of size K you can see in this array which is of size 5 this is a sub area of size three so we have reversed it and maybe at the last you can get a sub array of size less than K in that case also you have to just reverse it okay so this is the problem so I just want uh from you that you can just give me the best approach for solving this particular problem and how we can implement this problem okay so the idea that is coming into my mind is basically okay so we want to uh reverse every group Subaru group of Senses so what we can do is we can have a for Loop which will jump at K steps okay okay uh which will jump at a distance of k each time and uh there would be a condition uh such that we could you know check if if there is uh if I jump more okay step one more time if it is possible to be in the array only or it is going out of point if it is going out of bound then we can just you know take the size of the array for that and then reverse the from descendants to the end of that okay yeah it's it's seems to be quite good uh so you are basically saying that you will take a for Loop and you will just iterate for the everyday except yeah yeah okay so just just can you just tell me that how you will make the reverse operation let's say that you have added you have a sub array but how you are going to make the reverse office can you just okay so uh like for the implementation part I could I could use the STS reverse function or I could Implement a reverse function myself which will basically what it will do is basically let's say we have one two three and four so I will have two pointers one more time towards each other so it will be like after first step it will be four two three one and my pointers will be at 2 and 3 and then also I will reverse it so it will become 4 give me two and one so the complexity of the reverse function is open foreign what will be its counterplex flow if I am implementing it okay so so I am having a k jumps and at each K jump I am reversing the area of size k ah so I think the complexity would be of n we go up and as you know we are having three jumps and at each jump we are reversing the you know uh the K sub array the Subaru of size K so uh each element is you know uh um each element is listed one time only and that will cause to have a competitive whole end fine just can you just please write a quick pseudo code for this problem how you are describe so let's say we have voice so let's click let me give you a function just just give your function at that place only so let's take that having is sorry let's say that you are given with her let's say reverse groups and inside this you are dealing with a vector v and the value of n which is the size of the vector and the value K which is the K means the subgroup size and you have to basically let's say return this particular uh reverse with proposal reverse rewards Vector okay so now how you uh can I use the reverse function of the SQL or should I write the reversal to myself okay so can you just please tell me how the reverse function of that STL works okay so like the reverse function of the sdl hmm like uh as much as I know like it has uh it has two pointers and like other approach I already told you I guess that was the implementation of reverse function um that means you are saying that it works under two point of support yeah okay fine let's let's implement the code so uh uh okay so I will go with SQL Rivers only sure so we have okay so we are having and we could have n minus K but we are not sure like will it be okay let's go for this moment for now okay it would have n minus cases but there is um so I will go from okay I will reverse function we thought oh plus I comma V Dot plus K I would reverse this because I think this will be fine and okay and not k x i plus k okay so here I could have minimum of n comma I plus k and uh now I put closer can I just zoom out it's uh um let me see uh I can leave it down that could be uh just let me check uh let's say we have on the report we would go for uh let's say okay the first group two for now so we'll go from one to from this and if I'm getting I plus K is more than uh okay plus okay should be more than this but this could be a condition okay so what I'm saying basically or two when we have issue I think three would be fine so we would not see and let's increase the size like this okay so now what I will do is I will go to zero I will reverse this array it will become uh three two one and then I would have a pointer at three degrees and I have size and equals to equal to 3 and equals to 5 so this is [Music] fine okay so I think it would work for now yes I think it will work yeah I think that it's fine from my side so just can just please tell me about the time complex chain space complexity for this approach which you have written um okay so our space complexity is bigger one like we are not making any extra spaces and let's go for time complexity it would be okay so we are having three steps so the number of steps would be n by K uh approximately not exactly but it could be it would be n by K only and for each step we are going uh K times in the reverse function so it would be n by K into K which will will uh like which will be and like K will be canceled and only n will be left so the complexity would be of n okay okay great okay so we can't find so that is what I was just searching for it's fine so let's find from my site for this problem so yeah I think that now it's time for the next problem let's move towards the next problem okay so the problem is something like you have to merge I think that you you have heard this one you have to merge two salted areas okay but there is also a Twist so I'm just writing here so just move towards the let's move towards the next page okay all this problem okay right uh yeah so the problem is that you have to merge two salted arrays but without using any extra space okay so the thing is that let me just write the problem statement for you so the problem statement here is this one which is you are given with two solder it is arr1 and arr2 and their sizes are given to you they both arrays are independently sorted in a non decreasing order you have to basically merge these two solidarities means the final errors would also be sorted but the only thing is that you don't have to create another array of n plus M size let's say that let's say let me just give you example let's say that our array which is given to us is ARR of 1 is [Music] of 1 is something like one four six eight ten okay similarly ARR of two is something like 2 and Lexis 7. so the final array will be one two three four six seven eight ten I hope this is right if I will just merge these two arrays this means the finite so what I want that the final error should not be written as a part of a new array you have to just make changes in this array and the first five elements will be in here because this size is five and the next element will be normal so this will be the value of these two arrays after the operations are performed so you have to do the in place merging without using any of you the problem is clear now yes yes Okay so again let me just give you a function for you to just write so let's say that this is the function that which is merge you don't have to return anything just make the changes on that array only and the first area is arrival error 2 when the size is NM of both Diaries um it's okay so let me just call this story so what I want to do is I want this to be in this array since it is smaller than 4 okay so how would I do it I'm finding an element smaller than this I want this in this area but okay this is not I'm not sure because like 4 could be in this area or could not be in this area it could be shifted into secondary also depends on the array the elements of the Arabic okay okay so if I am here and I have to you can also just tell me first about first approach then we can move towards the more efficient one okay like with extra space or without excess space yeah brute force can be any any okay come here okay so like one Brute Force could be we could like we could uh push back every element in a new vector and sort it and then take the first 10 elements in the first and second uh M elements in the second error so that would uh that would be the first fruit pose it would cause us o of n plus M complexity in terms of space and N plus 1 log n plus m in terms of time complexity as we are sorting the most value okay fine okay so fine fine so now how we can optimize it in a better way that the space complexes should be o of one only and I think that for this problem as the arrays are already salted boot there is so the the compressive linear the time commission linear in case okay so let me just just yes we can do that uh what we can do is basically uh we have two and we have four now uh if we have 4 and we have a smaller element than this in the second array we are sure that the last element of this array because since it isn't sorted and so largest element would be in the end so okay okay yes I think I got the question yes let me verify okay yes okay so since the errors are sorted uh if I am finding the smaller element in the second array now which is smaller than any uh element like let's say for 4 we are finding two we can just swap it with 10 since 10 is the largest element of the array and if we have a smaller element which needs to be swapped or which means to be you know placed in the first array then there would be some element which needs to be getting the secondary okay so I can I think I can swap these two and okay so and [Music] if I find this I can swap these two also because since we have two elements we won't surfboard this so we would add something like error one this is equals to go okay three and two and we would have added two as so put it with a pen see and some okay and then we can sort both okay so I think this is uh the approach okay yes so uh the time complexity would be um but we are sorting it it would be n login and login like we are sorting it uh yes and login basically n log in or M log M uh whichever is the higher okay okay so can you just please again repeat the approach what he was thinking of okay yes yeah so uh like I would have two pointers uh one in the array one and another in the array two okay uh so if I find a smaller element in this array array 2 which is smaller than the current index let's say we are at 1 we found it is larger than this then we move the pointer to 4 and our this pointer is still at 2 because we didn't find any larger element but at 4 we found it so we would like um like for four we have two which should be in the array one so we can say that the largest element of this array would come in the array two only because like if we are moving some element up some element has to move down in the array two also okay yeah fine fine yeah that was the approach so I would uh swap 10 and 2 like this then I will move the pointer to three and here also I'll move the point I will keep the pointer here only to check if 4 is larger than 3 it is larger than 3 so again I will start for that too you have just continued I mean first you have compared between one and two now that is what you are saying what you will do if one is smaller than 2 then I will move the first pointer fine so now the pointers are at foreign now the pointers are at four and two yeah four and two and now I find that 4 is larger than 2 so 4 so this basically the idea is basically two is smaller than 4 and if we are having a merge sorted array then 2 has to come in the array 1 only okay yeah I got it yeah so to swap this uh is it clear fine it's fine so uh after doing this uh we are sorting both the arrays wow and the time complexity is based on this video will also break off one because you're not using any extra speed foreign approach so okay let's see why is representing everyone increases while I is less than n or should it be what let's see I'm not sure it should be all right because uh because if we are at the end of this still we will do uh like if I have a pointer at 10 and a pointer at 3 still I would compare the elements like 10 and 7 so it there should be all okay for sure one of I is less than a dollar one k what do we have equal duplicates elements now let's assume that we're going to have duplicates okay we don't have okay so there would be a lesser than like the element would be smaller or larger there couldn't be any element that would be equal in the good salary so let's not looking and we could do this and I'll so we have else part let me just come out a bit not okay okay um [Music] so uh next we have a greater element so what we wanted to do is basically what is it yeah yeah uh what we want to do is we would swap it with okay we need another pointer for that of K is equals to n minus 1 as we are dealing with and my well of course therefore so K would be n minus one so I would swap uh ARR 2 of J and here are one of K is it okay and uh what I will do I will do basically J plus plus myself okay okay got it sorry K minus one [Music] yeah it's you know the line is colliding with each other I am not able to see correctly K minus X that's fine it's fine I've got it oh okay I'm doing I plus plus so this is okay so in last what we have to do is basically sort we are uh one plus n and so here are two comma here are two plus M and before you just do that let me just check for the while loop of I'm not sure about the wife uh about this or condition because there could be some overflow [Music] they're also thinking there is a time when maybe I can become an so in that case this will go out of bound index out of bound again that's what I was thinking so if I go okay I think I could do this I could go with and end and if I am at the end of an array I could just you know do nothing because like uh okay if I went here [Music] um I think that after every swap in the second array you have to also sort the secondary so that the elements of at least one area is really salted because when you are just making the swap operation so that is completely fine that for the first array you are sending it the smaller element but for a second one let's say that when you will swap when your first point will be at the fourth of the array one and let me just explain you that there let's select your first point is at here okay at this particular element I hope that it is this one and the second is at six two so when you will make the swap operation here you will have to and here you will have four getting but in this case now your arrays are you know your error is not salted so in that case you have to uh in each swapping you have to also solve the second way is the m m array so that will just take of M log n okay and that will be completely fine uh and this is all you can do I think that the other individual part which you have done is is quite good means you have just used the two pointers but there are some test cases there are some Corner cases where it may fail and because of just one of the corner key which I have told you that here I think that it is what do you say um let me just go about it I'm not sure because like uh what you said basically was this but uh like Okay so uh What uh like so like my Approach was like yeah you can give me um that if I have a smaller element than this and I'm uh doing it here so my K pointer would play a role here because like if even if like there is smaller element here and we are swapping it with this and we we are having a k pointer also which is pointing at this now after the swap okay so uh if I could use K pointer to know like K pointer could uh tell me where the last swap was there and till when the array sorted like in this case till here the array sorted okay okay and fine uh then I could you know know which part of the array is not sorted because this array will be sorted everywhere every time like I am at one I'm at two I am swiping it I am moving at three so I am not doing anything uh after this after three seven okay and so this error is not the problem I think is it okay because like find things can you just again explain the code uh the pseudo code I'm sure I will uh drive on it for you yes let me just you know I I'm I was thinking something here okay let me just make the approach once again is n minus 1. for now okay so the first iteration will occur I will just check for one and two so since 1 is smaller than 2 we have no issues because in the merge diary also they will be small like it would come after that only after one only minus one and what we can do now is basically we have four and two now four is larger than two and in the merged array 4 should come after two so what we will do we will select this with this so what the array will become is basically like this uh previous work this and this and we will move the pointers let me just for you the pointers would be I will be there only J will become 1 and K will become n minus 2 okay help me here uh J will be here only and our sorry I will be here only and they will be here now what will happen will we will compare these two and still 4 is larger than Earth 2 3 so we will again swap it so the address will become like I think like this oh it would be 3 here and our pointers would be like our contest would be like I want to remove two this would move to 3 and minus 3 this will move to six only our eyes one now I will compare four and seven so I can say that 4 and 4 is smaller than seven then it is okay and now if I move to six I can still compare six because like the value of K would be 0 2 and I would also also be two so I can compare this index for now but I cannot uh you know move uh like move my K pointer from this point so what I can say basically uh this will be the final array once my I become more than K I will see I've got it I've completely got it I've completely got it just just go again to the code part okay so my uh I didn't cover this uh this was the array I am J pointer and I pointer if uh error two of J is larger than array of I I could just do I plus plus because like one and two case if I have one and two like in this part uh like here but then I could uh you know swap the last elements and increment the J pointer and decrement the K pointer and lastly I can't just sort those two fine fine it's it's completely fine I've got it so just can you just please tell me about a time complex change space complexity for this problem oh okay so we are sorting both the arrays so whichever is higher I would say the time would be time would be bigger uh maximum of n comma and should I write like this or I could convert it into analog in something like that like and since it is a two pointer so it uh yeah it would be uh oh and login only because we are sorting the array and the complexity of while loop would be I Plus uh eight plus sorry n plus M and the Sorting complexity will be analoging so the maximum one is unlocking so time comes to the end login and space objective would be a big open think of one because we are not using anything we are just swapping in the area and sorting it after the loop so this would be the thing like this I think I think it will be better if you write your time complexity as n log n plus M login should be a plus it's fine it's fine so um that is what I was just asking from you so it's fine means you have optimized it in a good way and the dragon will also converting fine so overall the approach which you have used is also completely fine so we have some time we have some 10-15 minutes so let's go with another problem and a really exciting one so I just don't go on the you to just code that problem completely because maybe that that will take more time we don't have much time this one from you a good approach for that problem and till not because of proposal problems you have given a great approach so I hope that you will just good right you have to win the the given arrays are all are solder only okay they are solid right so so we have multiple areas no no uh I'm just here no I'm just writing the protocol just a minute this is the problem okay so you are here with a number of characters or basically you are remember the string and you have to find the minimum number of characters to be added in a particular string to make it a palette so it will become like this which is b c d a and uh you can see on this is a pen domestic so this is the doubt can we insert at any position yeah sure at any position okay sources okay let me just count a minimum number of insertions required okay you can just come up with the approach what you're thinking for if you if you are able to find out the book for example the answer is fine if any other approach then it will be fine so we have to have okay we are we could insert at any position convert it into a palindrome [Music] I hope that you know string yeah sure I know um is basically if you reverse this thing both strings should be you know same the first half creating it from starting and reading from and both should have same yeah exactly thank you so what I was saying is so we could yeah okay you know to find Minion number of students so let's say we have something like give me TV so we put different sorts here then you could find it okay just giving you a hint uh just keeping your hand oh okay can I if you need I have an idea for now like but I am thinking something like this so if you have a ABCD I would just have two pointers at A and B um okay so I'm thinking something like if I would iterate through a b c and b okay and I would try to find it at the end of the string if I am able to so like in this uh let's say we have a better example let me write one more example A B C so let's say like this okay hmm so we can just insert it is okay at each position I have an option to research at the back um so if this is the straight thing what I would try to do is basically I would try to find this character at the end of this okay if I'm unable to find it I will just insert it here like this okay and I will move the pointer there and again I will try to find this in this but I am not able to find it so I would insert B here now I will go to C then I am able to find C uh then I will move both the pointers like this control will go to here this control will go to B and these are not equal so I could insert B here a better approach is like uh we could only insert this what was it oh see see yes so this was the original swing so we could insert C here only and this would become a palindrome okay so okay uh yes so the approach is like the first approach I only told you like I could I would try to find this at this position if I am unable to find I will insert an element and then again I would move pointer J here I it means I will move the pointer here and I will try to find if this is possible uh so I could do it two times one with this like the string only and other with this reverse thing there is a corner case uh the corner case is something like let's let's just let me just give me give you uh example okay so let's take that just like here what you were having was it was like where is it like it was okay then C A so you can see that in this string if there you will just add a b here it will be a parent room okay yes so for that you are saying that yeah you can just make it like that but you can observe one more thing let's let's say I have just removed this a from here and B from here so it will be that in the first case you have to insert a B in the right side and a in the left side getting but if you will because so if you will just if I will just follow your approach you can see here that if I just follow your approach you will first check from here that b is not present at a B then C is not present at a c then a is not present at a so a is present this will be your strength okay okay because there could be an insertion at any position so I will basically your logic was absolutely clear that you have to check for the first element also whether it is present at the last call or not similarly you have to check for last element whether it is present at the first order fine hmm but this can face in every position in every comparison I'm able to understand it like uh which is the examples I took it has like it would work only for the elements uh for if the question was like we are able to you know in certain insert elements at the end of the end points of the string then it would work it won't work if you are allowed to you know insert any at any position yeah it can work but basically it works when uh you are just taken from a single side that uh you are basically what you're doing certain element at a single time another single side either on the right or in when you reverse it then on the left basically so just your approach is very clear just just think uh a little more and you will get the solution can we do a recursive approach here yeah I'm thinking about that okay so okay so I think I have an idea so uh what a recursive approach would be like I'm what I am able to think about that is basically uh what okay yes I think I got it so our um we would have two pointers in I and and B in the recursive state okay so if these two are equal let's say for uh for what uh let's say for this one day if these two are equal then we could you know decrement both of these okay okay so what is the address if both are equal if s of I let's say s of I equals to S of a then we could uh you know decrement every like I would do I plus plus uh incremental left pointer and decrement the right pointer and if they are not equal then we have two options else then we have to option what are these either I could insert it here or I could insert an element here which is equal to this exactly so uh so we could have a recursive you know answer of uh in answer as opposed to minimum foreign and okay so if I is equal to equal to J then we would return 0 because we don't need any you know we don't need any um more uh insertions and if s of I is equal to equals to S of K then what we could do is we could basically do I plus plus or we could have uh return um foreign [Music] and we are saying that let me write just like this problem I'm able to I would write the recursion and I and I I could write the DP also Deepu would be of two states and we could use this in that uh so I if I have I plus 1 I could if I have a and b at I and J pointer I could say that I have inserted uh a here and I could move the pointer to the from a to I plus 1 and J pointer will be there only uh like this yeah and similarly there would be J plus 1 and J minus one answer equals to minimum of answer comma um and I think I could return answer here exactly exactly and I could you know memorize it yeah and then that will be DP I got it I got it completely so fine fines with cancer as we are also done with the time so let's it's time for the feedback session so first of all let's first talk about all the things sorry should I close the door I I have just removed your screen from there no problem oh yeah so okay so so we can follow three problems it means for the first problem it was a quite easy one because this wanted to start from Easy problem just to know that how you are just performing and for the first problem you have just done a welding and you use the reverse function uh how we are reversing and that is what I was figuring out is thinking of and the most challenging thing in that one was how we can find a time complexity because maybe someone will this confused that it is n2k or something like that but that is also what we have just got done you know confused but yeah yeah so basically uh what you are it was great you yeah you have told the the exact thing that we are just editing for uh each element just once when we are reversing it or anything whereas I didn't punch so it's just too often and uh if you talk about the next problem which was again a hard problem and uh which is merged disorder using the same which it means merging two arrays is a quite of similar an easy problem of two pointers but without using an extra space that was something hard to uh to implement yeah exactly but yeah you have just done it wonderfully and I was just not expecting that myself but yeah you have done it wonderful and the thing you will just approach about the three pointers it and K so that was really nice how you were just swapping how you're just comparing with the first element of the first round starting with the last element first that was a very amazing logic yeah it was like that was very tricky like I was not sure like it is correct or not but I did some you know dry run and I was thinking like it was like yeah maybe maybe it uh it means I I have some doubt with the corner location maybe it can but I think that it will run for most of them will be right I was just the approach you just came with up is also quite good uh now for the third problem it was a really uh difficult problem of DP it is so that was very impressive yeah that is a great problem I was just thinking I was just thinking to take that problem before that merge through sorter areas but then I think that as I see your profile your resume already you are good at VP this thought you just play something with arrays and then move to the DP part so that's really amazing now the feedback the time for the feedback session so you can just scroll down the feedback part yes yeah so where I have given you in accordance is 4.5 out of five because uh the way you have just thought of the thing and that wasn't really fine and that way you implemented uh the first problem just use the reverse function the last problem using the uh recursion and uh that are depending the two states and for that three participles for a second problem time limitation was really great for the communication I just give you uh feedback from my site that uh like when you were just thinking uh in your mind of when you're just trying to get on the problem this just make it loud means when you're just debugging your code in that case you were just talking by your own or just thinking on your own just make it interactive with the interviewer also that yeah sir I am just I was thinking this but that may fail at the per case so I'm just changing this thing or like in the second problem you were just thinking by your own that I've taken three pointers I haven't not not getting worse that was the case that just be are interactive with that interview so it is just otherwise it was also good and for the speed I have not expected for the last problem so the speed is for the last problem basically uh it's like you have just done it in the last 10 minutes and also the first problem was also then in the last first 10 minutes so it was also amazing great for the second problem you have taken some time to understand it but overall it was a good one so overall it's just 4.5 out of five and that that's from my side you can answer your skin it's fine and also any feedback from for me so we can't so like I have nothing to say like he was great like you were quite supportive and you know uh like you were able to you know clear the basically when I was lagging like you heard me so it was great okay thanks thanks okay guys so this is all for today uh I hope that you have loved this particular session if you also want to be the part of this this type of live long DSS you can just check out the link which is unboxing you can fill it out you can also get a chance to be a participant in these type of monthly basis okay guys then thank you for selling my stream thank you have a good day bye