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 yeah yes way [Music] don't delay enroll now Jake's 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 expert at code forces and uh this year I've qualified for ACM ICP seasonals with a rank of 57. so today we have four window with us so let me add Hi how are you I am doing great how are you yeah I am I too so so can you please tell uh tell me some something about you your introduction so my name is currently I am a student of civil engineering at yadavpur University I'm in my third year also I am pursuing my online BSC program from IIT Madras parallel I2 competitive programming and im2000 plus rated at lead Code 4 star at code shift and specialist at code forces also uh I do projects uh with flask as my backend tool and for the front end part I can I prefer it's a normal HTML CSS bootstrap along with JavaScript okay great so can you please tell me something about your projects and stuff you have done with the development site so one of my projects was uh which I made while in learning flask was to was a Blog application so there basically a user can ask the admin for posting his or her blogs and like there are facilities to edit and modify it later on uh like this was mainly the concept also I have added the login part for the admin to make it a more secure and another project was made as a part of my coursework so basically it is a happy tracking uh app where you can like track your daily habits and there was three there was we were asked to made it like there were three options uh one can be numeric multiple correct like this and I have added those three separately and uh like it was a good one I have got the feedback it was a good one yeah great great so guys we are just going to start so before starting please hit the like button and write a one in the chat box uh if you all are also ready and excited for this amazing interview which is going to be and just write up one in the chat box so that I can know and then we will start okay so I have shared you uh doc a Google doc file uh I've got a link yeah yeah can you please open it and share your screen so that we all can see should I only share the tab and yeah so you can just share that just a tab with that Google doc okay no worries okay yeah can you please Zoom it so zoom in somehow so that uh we can see it properly yeah great so let me first tell you about the first first problem the first question so in the first problem what you are given with is that you are given with the string foreign so you have to find I String which is anagram of this string this is the first condition and which is also palindrome so the first thing is that so basically the first thing will be that you have to find that whether a parent domestic exists or not means a string which is the anagram of it and palindrome so first let's take it like that you have to first just tell a true or false but whether ice cream which is a anagram and a palindrome both exist so let's take example so let's say that example given to us is foreign so for this example if you will see that yeah we can create another thing let's say S2 which is like this this is a palindrome and also anagram of the first string so that is what you have to do so you can okay so I hope you have got the problem yeah yeah so just to clarify anagram is I think uh the free number of characters occurring in string s should be same right character number of characters means let's say there's a string with length five another length they had anagram or not no no like I am telling like that only the string s can be shuffled to make another string right okay got it yeah okay got it so should I write only the function uh yeah you can first tell me the approach what you are thinking okay so like foreign it is anagram so I know I don't need to find a new character I have I only have to shuffle these characters uh to get my answer so if for a like a set of characters to form a palindromic string the frequency of a character should be must be even and there can be at most one character which has a odd frequency like I can put that uh character in the middle uh middle portion and hence I can create a palindromic string so this will be my Approach like I will check if this I will first calculate the frequency of every character if the frequency uh frequency is odd for at most one character I will proceed with creating the string by answer otherwise I will straightforward return a false like it is not possible okay okay yeah I am getting somehow uh okay I think that we can continue with the with the implementation yeah okay so should I start the coding part yeah let me let me write a function for you let's say that there's a function uh check so it contains a string let's say s this is the function which is given yeah there exists uh another string which is an anagram and a plain room two got it so uh what I can do is I will uh create like mail count the generate the frequency of every each and every character so it will be frequency and uh like I can do it in this world so I through this frequency of I minus a I'm sorry uh I plus plus so this will uh tell me how which character appears how many times in the string is now uh I will Traverse this map and I will check if order like I will count how many odd frequencies exist here so this will be like end count odd frequency to zero so if I dot second so this will give me the frequency mod 2 is not equal to zero I will increment this value okay okay uh and if any time I find out that this odd frequency has exceeded one like I cannot put create a palindrome with two characters which have odd frequency like like Suppose there is one a and one way I can it is impossible to create a palindrome so if I by any means if this uh count exceeds one I will return 0. like written before return false yeah um and at last uh if the test passes this part so I can simply return true or I can at last check if count or frequency is less or equal to 1 or not okay fine fine okay so can we make a diagram on it on the given test Keys which is given to us yeah sure sure so like uh here first I will check H so h foreign will have a frequency one as of now then I will go to a a will also be incremented with the frequency of 1 now n comes then will be there with frequency 1. now another n comes and hence I will increase the frequency to 2 and another a comes so I will increase the frequency to proof so this will be my content of the frequency map then I will Traverse in the map and I will check if the frequency is odd so here I will encounter odd frequency and this if will be executed and my account will be incremented to 1. next I will check for a uh the frequency 2 equal to 2 the if will not be executed and uh it will not be executed anywhere so it's fine again in uh for the frequency 2 this if will not be executed and hence odd frequency count remains one at the end and hence this if will never be executed and and since it has there is no condition over here it will simply return a true that yes there exists a string which is a anagram of the given string and a palindrome okay okay got it fine uh just uh modification the problem you have to print that that possible control so how we can do that okay okay so while printing let us say if no such uh when it means you have to just print one possible with anyone any of them I if it is not possible so just return minus one in the form or by string okay so should I modify this code only yeah you can do that too so I will change the return time at return type at first yeah and uh uh instead of returning false I will return minus one here okay now if the check passes I know that there exists there are answers always exists and uh what I will do is uh let's say my answer string is our answer now Okay so care uh character with odd frequency equal so I am creating this character uh uh like if there exists of a character which has all frequency I will be storing it over here uh so that my string can be made up more easier like more easily DOT first okay so in a given test case uh this character with odd frequency will have H as its value now okay now I know that uh there is only at most one character with odd frequency uh yeah so I will Traverse the um frequent map so frequency so I will initially check if I dot second mod 2 is equal to equal to 0 if it is even so there is no problem I will uh like I can add it half times like if the frequency is 4 I will add it two times and uh I will like duplicate reversely duplicate it to make a palindrome so I uh I will run a loop for J the frequency by 2 I will run the loop for half the frequency and I I'm sorry and I will increment uh add the character with my answer okay okay so like if the frequency is 4 I will be adding it two times so 4 by 2 is 2 so the group will run for 0 and 1 and this will like in this particular test case if the frequency is two plus two by two is one so only one time a or n will be added now else if the frequency is old so like if the frequency is suppose one so one by two is zero so the loop will run 0 times if the frequency is 3 I need to put two characters uh like in the opposite fashion and one character will be put at last in the middle so what this will do is a three by two is one so it will run two times but I must ensure that it should not run two times no sorry uh it will run one time only okay this is fine since three by two will give me one so J equal to zero J less than one J plus plus so it will be executed only one time so this is fine and hence as I can see there is no requirement of the if statement so I can remove it like this can be done now uh now what I can do is like I will check if this uh like any odd frequency it exists or not if it exists so it will have a value one like the count is one and I can do is what I can do is answer I will add that character that specific character foreign and I'll replicate the part so I will create first create a copy of this temp plus equal to this character so basically now it has whatever temp has whatever half of the frequency of whatever I have already done and the character with the odd frequency now I can reverse my answer and like so and simply return temp plus I'm sorry else like if there is no problem of odd frequency or whatever as reverse reverse answer okay and if there is no problem of odd frequency I can omit this by part like I will simply reverse it and append it with the answer okay yeah seems good okay that seems good okay great uh let's let me just yeah I think that that is what I was expecting Lord actually uh you you are wrong you can check that uh I'm not saying I'm replying a comment sorry so actually we have to take the frequency of each character okay Lord so it's not like the it is not checking the frequency of a credit checking how many characters are there without frequency so I think you have got the problem or implementation quite wrong please check it okay it's right okay great great uh I think we can move towards the next problem is it fine okay yeah yeah okay okay great uh foreign name is this is the problem name let me changes just okay and here's a statement that we are you are given with an array ARR of size n and an integer key you have to find the maximum of each and every sub area of size scale so the maximum of VC memory is a value of size let's take a case key this is the array which is given to you so here the will of case 3 means you have to take all the contiguous arrays of size three you can see the first three are there and then I'll put the maximum of it which is this three then next three is their maximum of it this is 3. okay then next three are there maximum office which is four so this is how you will check for each and every uh summary of that size K and you have to tell the maximum that's what we're doing about it okay um okay so the first Brute Force approach that comes to my mind is uh I will like create an array or Traverse the for K elements individual and then find the maximum so it will be the time complex it will be n into K which I think is not a feasible one um uh can you please again repeat what will be the time complexity uh n into K according to me like I will first choose K first K elements then the next K elements so I have to select K elements one at a time so at most there can be n into K I think the time complexity will be okay okay uh like here one time two time three times four five six and seven okay okay and like I have to find the maximum for each class so like case sub array so yeah that's why it will be an into k for traversing will be n and then again okay so okay so I can create a map like since map not another map it will be map since it stores the elements in a shorted order so I will create a map and not a set I will also explain that later like I will create a map and select the first key elements and the maximum element in a map will be at the last pointer so I can access it using like C plus plus STL map.r begin it will give me the value 3. next what I can do is uh like this will be kind of sliding window my window will be initially here next I will move my window to here and okay I will decrease my frequency of this pointer and increase the frequency of this pointer okay so again it will be like the last element will remain free now uh I will move my window over here and decrease the like if the frequency of 2 is 0 I will just remove it from the map so the map will now hold three one four again the last value I will like add it to the answer like uh is the approach okay yeah fine this is so basically you are doing the sliding window and uh which is basically you are using the map so using the map to find the maximum like to find the maximum in login time otherwise it will take a k time to find the maximum it will like it is basically sliding on the problem but to find the maximum is the challenge finding the maximum will take uh in Naval native way like it will take o of K but if a map is used it will take log of K okay so I'm just sharing you with the link to uh I think now you have to yeah I'm writing there only so um this is the link I've shared it to you you can you can first if you want you can first add a brute first approach in the seat only if you want otherwise you can Implement Your solution directly in the code part uh so I can write a Brute Force since the sub array finding traversing the server apart remains as the constant so I can write it there is no issue but uh just implemented the code part just implement the code yeah we demand yeah I mean most efficient approach you are you are thinking all right so do I need to code it in the doc file or in the link no in the link in the link okay and uh should I change the yeah yeah you have to change no worry I'm I'm unsetting from here yeah great great okay um okay so I will create a map let's name it I can name it frequency only uh so for the first K elements I will just blindly add the first K elements frequency of ARR of I plus plus uh okay I will I need to also create a answer vector so I can add this answer Dot pushback whatever is the last element in my map so frequency dot are beginning so this will give me the maximum one uh in the map because that is currently present and uh it will work like that okay now I need to create two pointers so let's name it as start is K and N is 0. so what I'll be doing is increase the frequency of the value that is at the start pointer and decrease the value that is at the end pointer and I will go on like this so for start I will do it until start is less than n uh my bad I have like I have flipped it so yeah this is the better name so end is less than n n Plus okay okay uh I will increase the frequency of the end one so frequency of ARR of and plus plus and frequency of ARR of start minus minus and I will check if the frequency goes to zero I will just delete it from my map so if this thing becomes 0 this thing becomes zero I will erase it but it is okay okay and uh at last I will just do this thing only push whatever it yeah like okay so there is another understand I need to increment my pointers also uh whatever is there at the last at the ending of my map I will just push it to my observator and At Last I will return the answer oh look at this let me run it no matching function to call okay begin dot uh first since I need the element and not the frequency foreign to the end just like a comment this down and check what is the value of it star frequency dot I'll begin okay so it returns me a pair constant okay sacrificed okay so there was a syntheticular copy and there's a Double T at the line number 21. double line number 21 last two characters line number 20 first okay there are like uh one two three two same for line number 292 yeah yeah yeah yeah no worries nowadays okay so the sample test cases has passed yeah the second second right 10 and 4 and The Limited numbers even copied no worries yeah okay can you submit it yeah foreign okay okay so expected is O of n uh actually for a map because you are storing it in a software it's taking log of n so can we do that thing in means if you will see the overall time can you just please tell me the overall time complexity for your code so the loop will run n times and the map will con contain at most K elements at a time so it will be M into log k yeah so I think that uh if we can perform it in uh order of n so it will be uh yeah it will be a expect means this is a this is absolutely right means if you can think of it means uh I have not constants so I I haven't seen it before 10 7 constraint oh yeah so that's the reason that I think that you have to take anything if it is order often got it okay so these things can't be done here um I I mean I don't want the complete Implement implementation of it from you because we have already implemented this this particular approach if you can just come up with uh can you use any other data structure instead of this or which else data structure can be used to store the sliding window or a window getting that means what we are doing here we are basically so if you will see one thing let me give you some things that we are having we are having a window frontal window we are adding an element from uh basically we are adding a new element and we are removing element from the back that is what we are doing right if you can so if we can use any data structure where this can be this can be implemented easily without that log got it so maybe I can use a DQ to like since you told like we are adding an element from the like backside and removing element from the front right so I can maintain a DQ to simulate the sliding window portion and uh uh okay so oh that's what you're thinking about yeah so I will copy the test case here sure okay now the thing is three so one two three right then two three one okay two three one and then three one four three one four so this two will like when I move this window over here I know that two can never be my answer since I already have a element which is greater than 2 I always know that 2 can never be my answer like for the first window of size k I will uh initially add every element then what I can do is since I will move my window towards this side so I know that if the answer is 3 for this particular window 1 and 2 can never be the answer for any of the possible windows right okay got it yeah like uh and in the next window two three one here also I know that two can never be my answer from the past experience but one can be my answer since the elements here can be one one everything can be one so if a number which is smaller than the number uh in front of it I will add it in the DQ otherwise I will skip it uh like so two three one in the two three one I will keep one now as of now then okay then how do I find the maximum one in Okay so uh like after the care elements are inserted I will clean up the stack to contain only the element three and I can just like I know that 3 is my maximum since any number which is greater than 3 if it comes in I can remove the three safely okay so initially I will I will keep I will be like keep the three as of now then we will proceed further well I like we will think later on so three then one so that as of now the DQ will contain three and one and I will just like have a Max on Max uh answer which is which will keep the track of which is the maximum element which like yeah it will keep a track which is the maximum element in the step either it will be the first element like first element in the stack uh DQ or whatever element comes in got it got it okay now uh so this was for the window two three one but since 2 has already already been removed I was looking at the window three one only now comes c14 as soon as 4 comes in I will remove the three since I and like I get it that three cannot be my answer in any of the possible test cases okay and similarly one can one also will not be the answer in any of the test cases like any of the sub errors since I have already got a four and I I will move the window towards right this will automatically be deducted and 4 will remain my answer okay okay I think I I think yeah I have got that thing can we just write a small sudoku for it means just uh quite implement yeah I don't want to complete no just assume that you have to just write the you have the array you have done you have an okay the side is okay so I will create a DQ uh first let me add uh add all elements from 0 to K in q uh then I what I can do is and also uh I can keep a track of what is the maximum like if the value over here is like this so 1 3 2 and keep track of Maximum keep track of maximum okay and next thing what I need to do is whatever element is smaller than the maximum I need to like pop it out from the front Okay so drop elements smaller than maximum from the front since I know that they cannot give up part of my answer so currently for this particular test is the Q will hold 3 and 2. now uh I will add one so Ronaldo from so it will run till K minus 1 from K to n minus 1 uh and okay these are my steps yeah yeah run a loop from K to n minus 1 and add the element okay we can also write the we can also write the importance it's five minutes the basic one I don't want to run network yeah yeah yeah so sure means you can first go for it and yeah so I will keep track of the maximum okay maximum comma the area of I and I will Q Dot push back area 5. here pop elements that are maximum from the front so while yeah queue is not empty and Q dot front is less than maximum I can pop them safely this part is done okay fine uh yeah I got it uh I think that there's there's a thing missing let me just tell you a corner case for it then you can surely think of it so if you will see one thing that if the test case is something like this okay let me just copy it and it will be like so in this case your answer will give 9 I think for all the uh okay if you can see now it means it will give 9 for all the cases no not for all it actually like uh because whenever we are getting a greater element we are popping the smaller one that is what we are doing so but if we have all the small elements after it so guys the greater element will never pop ingredients can you repeat it this is right on the thing which I mean okay okay while not hearing and the keyword front is less than maximum I can pop it up so like I'm driving as of now like whatever I have written uh as of now so okay I assume nobody is okay okay uh no like uh it will help me better understand it so like what is happening okay whatever okay so go for it so uh like for case three here I will simply add 987 and I will keep at the track of maximum no problem up to here and while not Q is empty and Q dot front is less than maximum I can pop it so maximum is itself nine so I will not pop anything as of now uh so the queue will contain 987 only as of now next uh I will run a low current I equal to k i less than n i plus plus the first thing that I will do is remove the front no like no not always remove the first element like there might be a chance that I have already removed some of the elements so I need to check if the size of the queue is K then Q Dot pop front so why why are we not always remove the first element because or we know that the first element will not be in our uh in our window actually but why we like like uh in this test case the maximum was three right in this part in this window the maximum was three and uh while executing this Loop I will make sure that whatever element like is smaller than the maximum I will pop it out so here one will already be removed like the only content of the DQ will be three and two so in this case the size of the queue is not K like I have already removed it so I need not remove it again if we are if we are at index I so means the elements before I minus K will not be there I think yeah so so we can also store the indexing means we can also compare with the indexes like yeah like we can push instead of the elements we can push the value of I index that can also be done yeah like instead of pushing error I I can push I that can also be done okay sure uh [Music] so I will make sure that and then now I will add the last element uh Q Dot pushback okay so here 987 now will it will convert to eight seven six but uh uh okay eight seven six now the thing is my answer will be eight okay okay one three two the uh it will be removed so three two will remain then three to one okay so yeah okay 987-876 no one three two three two one two one four okay this maximum is also Dynamic I cannot do it like that maximum what if we can just make a keep track of indexes and whenever we have a finder index before I minus K we can just pop it if we can take track of indexes like my problem is not with the popping like uh I need to find which is the maximum in that K like okay so because because you are just uh popping all the menu elements so whatever will be the front will be the maximum identity whatever will be in the front yeah I am also thinking in that way but uh uh like how many times I have to pop it out that is my problem like uh here in the window of 214 I will just pop out two and one but how will I keep track of what is the maximum that is currently present uh that is the issue actually no worries no worries mistake maximum so like here the maximum is three no problem then here the maximum is also three here the maximum becomes 4. so here it will be the first element here also it will be the first element now as soon as it as this is removed How will I know that I need to pop the this elements [Music] but I think that I have got the approach what you are thinking and it just just it's just the confusion between the popping thing is there and I think that the approach which we have we have thing thought means uh just remove the element which are small that is exactly fine that that's exactly what India should be uh yeah that is fine that you are just like that is the point key how we have to pop the elements how we have to uh when they are when there are multiple props now then stored in the maximum is I think a problem it's fine it's fine I I think that uh that that's from knights right now yeah okay great so uh yeah I'm just removing your screen you can open that stream yard no worries okay understood means no need to unsure the screen but yeah I have removed from here yeah okay have you opened a stream yet yeah okay yeah okay so fine so it's it's I think that uh feedback time is there so fine so if we talk about the first problem which I've asked you that was a quite it was just a observation based problem and if someone knows about parental and diagram one can observe and yeah you have a totally uh observative I think just in some seconds only and after that how you implement the things how you then the implementation that was also really good okay so on that I I don't have any type of things means you have done I think right and the time you have taken for it it's also Finance you have taken some 20 minutes for the first problem that is completely fine because there was extended version also I've then told you to print a screen written as string and that was exactly fine so if you talk about a second problem uh it was quite tricky one because it was a data success based problem which we call as a tsa-based data successor based problem which is basically implemented review queue only because the other Solutions of it is using the other is basically uh we can say DQ only sorry RTA like we can also do it by selling window or we can also do it by a map that we have implemented but that basically gives sliding window because of the time complexity it should be solving order of n actually but yeah how you just uh thought of that map solution because that if I will say you truly that map solution is actually not present even in a gfg portal uh and you can certainly add it there if you want right so I have told the solution to one of my friend like there was another problem to find the maximum I have told my friend you like this he told me that no one does it like that everyone is a segmentary to find okay so this is your unique one yeah exactly that was that was a good exercise even I was not knowing it but yeah so it was a good one fine and it was basically dependent on Q and we can also solve it using priority view but yeah we can we have to solve it in TQ and the second thing which you have observed I think that was exactly correct exactly correct but uh there were some changes that whenever you have to remove the moves that from the and from front we will only remove the element when we will apart from the window because that will always keep that of the window that uh that the Q DQ will always contain the last key elements it should not contain elements which is not in the window so for checking that you have to check the front otherwise I have to perform the background okay so that was the case actually and otherwise you have got it I think when I have given the hint of DQ you have gotten in a good way that is arguing the hint and this is you just pick at that in some seconds so it's it all it was also great so now I'm against in the screen of you uh just just please uh open your uh say it again that dog seat yeah and this is excluded down to the next page to the next place okay yeah here is the feedback so yeah so for coding uh I will give you eight uh uh out of ten okay by the way the coding uh expand was was really nice for me uh means how you basically go through was the approach of the SEC the second problem that map and then after that it was really good and the only thing was that uh that was a common problem of DQ and uh it's something happens again it was not capped and the implementary part I can give even nine uh I even 9089 okay it's more than 8.5 actually because how you'll implemented the first problem actually how you're iterated and you have just stored in a count thought frequency count even frequency and the different things so that was actually really great okay after that the communication part is really amazing if I will say that in each and every step in each and every line you are writing on the code you are just explaining that to me that is a very important thing so for those who are who are the viewers also guys please remember listing whatever you are writing on the pen on the paper whatever you are writing on the code whatever you are thinking even that you have to communicate with the interviewer you have to think cloud you have to write loud everything whatever you are writing you have to communicate with the and that is what he does so you have done that very amazing even if you are just in communication with me for every line you are writing and that was a very best point for for the interview actually and for the processary part two I can give you 8.5 or 9 it means from eight to nine something because yeah how you solve the first problem uh that was also great that was a quite easy one but how is for the second problem is come up with a new approach and then and then you also just just got my hint of the EQ and then go towards that in a quick visit that was also great so overall it was 8.5 out of 10 and I I think that it was a good good uh good rating and one should hire you on this if it is a real interview I think so so that that's from my side so yeah any feedback from your site no it was great the questions like they were standard questions and uh like yeah that's it it was a great experience to have the interview yeah if you want to ask anything anything so you can ask uh so like are this only the type of like foreign uh so for for internships if I will tell you that the questions are basically depends on the company or the role you are applying for so if you are applying for a good product based company and so obviously it will ask you some medium high level problems and what what I think is that the first problem which is ask to you basically is somehow which is which is to check your skills so it's not that you can say that the first problem which I've asked about not so tough because it should not be that you ask the problem which is very tough and that the whole interview is just going around it and it's going to be very easy so it's something which say someone asks and for a second problem uh uh if there are two or three problems it is of something medium medium level if you talk about the very Advanced topics like DP like graphs we have tries we have the other Advanced topic trees so for that I think that only the for Inter Point of View I'm not talking about the in terms of very big companies like Google and other these top Tech jams they basically ask the CPA level questions and just for the for the in general uh only standard questions are asked if you talk about a very hard topics like a problem which is based on recursion and then you have to implement a DP on that recursion it's not like that they will ask you a very Advanced DP or something bit Mastery questions like that it will not be there so yeah and yeah if you talk about the uh the very basic one so the greedy approaches the basic problems over like this was a basically one of Q at the basic program stack we have next religion we have different basic problems which as you can say standard problem of particular structure that yeah this problem can be solved by this this one can solve this so like find the care smallest element from the ks largest element that should be solved by Heap protect you so these type of Standards also be done so that that is that is what we have to do yeah yeah I hope that it was a great experience from from your site now you cannot save the screen nobody 's uh great it was great experience for me to interview you uh thank you then thank you very much thank you for that okay all right guys uh okay guys so this was another session of our mock live DSA I hope you all love this particular session if you guys also wanted to be a part of these amazing sessions you can check out the fill the form which is given in description you can fill it out and you can also get a chance to be with me or a environmental add these four gigs in this particular amazing channel so thank you for watching that's all for today lets me with you guys in another stream till then uh all the best happy coding