Live Mock DSA

[Music] [Applause] [Music] hello and welcome to geeksforgeeks so today is the next session of live dsa mock so myself university i am a five-star related code chef and expert at code forces i am our dsa mentor at geeks4geeks today we have sugam with us hello sugam how are you hello yeah i'm good and how are you yeah i am also good so swam please tell me tell us something about you yeah uh that from academic point of view uh i'm from non-ip background and currently i'm pursuing m tech and i have been coding uh since four to five months and i have a good knowledge of dsa up to the intermediate dsa in java programming language and right now i'm looking for an opportunity in itself okay fine so you basically code in java yeah yeah okay so can you please share something about any project you have created with java or your past experience with java yeah like uh like uh i have made a one project based on oops like a banking system okay in that uh in in that i only without gui actually that is not uh i have not included the front end part but i've included that what basically is happening here inside the banking system inside the real what concept concept how can we implement it so that how to send money how to make a bank account how to uh how to just send money and something and all other banking related activities okay great so fine so i have saved your document shubham can you please open it yes and please save the screen okay yeah i have said is it visible right yeah fine so okay so boom uh now uh the first question which i'm going to tell you is that uh we have an array okay so that is the array of integer so we have an array of size n okay in which there will be elements from zero to n minus one okay so it is a yeah from zero to n minus one so what we have to do is we have to find okay yeah so we have to find all the elements which are occurring more than once okay so let's let's take an example array okay our first example for example this is the first array given to us which is three one two okay is it visible yeah yeah so this is the first array given to us here you can see that all the elements are occurring just once so in that case you have to output minus one this will be your output in this case okay okay all the uh what can all the elements are occurring just once you can see that the frequency of all the element is one only zero is acting only one time three is actually only one term similarity fine okay if i take one more array like this okay this is the second array in this case you can see that two and four are occurring more than once there are twice two present there and twice four present here the frequency of two is two and frequencies four is also true means they are occurring more than once yes so this is what you have to find you are given with a array of integers and one there is one more thing as i told you that the size of this array will be n if the size of this array n then there will be elements just from 0 to n minus 1 as you can see that for this particular array the size is 6 it is an array of size 6 and here the elements are just from 0 to 6 so maybe there are some elements who are repeating which are repeating so you have to output such elements like in this example 2 and 4 are the yeah yeah you can you can write and explain your explanation so first of all go with the yeah brute force approach and then make try to keep it efficient more yeah so first uh one of the brute force solution i have came in my mind that uh first i will just let's let's i will take this one then i will find is there anyone present is there any one present if there is present then i will print that one then i will take this two then if i will check that if is if any two is present or not so okay o n square approach i think uh this would work okay okay so can you write that approach uh just a pseudo code for that approach like uh and then also one more thing this array is not salted okay that can be unsalted area also yes as no but the problem is there if see that will happen actually yeah so basically you have taken a for loop which variable i this so yeah so what this i will do it will start from zero to n minus one okay fine means you are checking for each and every number from zero to nine yes yes okay okay yeah when it is there so there should be n minus one okay otherwise it will go out of bound yeah okay yeah maybe when you will call that particular yes you can complete this so i will just check if that yeah suppose the err i is there so is if error of i is equal to like 0 then i is it here if your r of i is equal to z okay error of j then we'll simply i will simply okay so what can be a more efficient approach okay so basically here you are checking for each and every pair of that particular yeah yeah so yeah so fine so what if the input arrays there are three twos in the input array in that case there are three such pairs whose are repeating means yeah there is this 2 is also a pair this 2 is also up here like this there will be 3 pairs so in that case you will output 2 multiple times so maybe you can use any other the data structure to store that numbers so that there will not be multiple numbers same number basically yeah so i can say that when this will happening then i will just put a like asset i can use has said and just put after this printing okay before yeah and before uh before this if before going to in this file if condition i will check that if the that is present or not if that is already present then i will not yeah yeah i got it i got it fine so yeah yeah so let's move towards the more efficient approach can we do it in a more better way because this is a on square complexity solution so yeah more efficient yeah yeah okay let me think like one or i can simply uh put this first in hash map okay first i will put all these enhancement then i will check then i will again iterate through this area then i will check that if the frequency or i will make a hash map or i will can use also frequency error also so i can i can just find that if the if uh the frequency is greater than 1 fine then i will print the that number okay okay so that is of that is o of n is time complexity and o of and space complex space so means you are saying that you will use make use of a frequency array or a snap and you will store the frequency of each and every element of the array yes like that okay so can you please implement it yes yes yeah first i will just uh iterate to the whole area you can zoom the document so i will just check i will just put map dot i will should i declare that map or this simply like yeah you have to write a pseudo code so you can just like the simple format okay okay so i will just put map dot i will make use of map dot get or default as it will it's okay so i will just put and then i will again i do it fine so i will again uh i will again i create an error okay and then i will check if map dot get here of i dot i've era caterer of i uh is greater than one then i will simply yeah i got it okay yeah so you have to first count the frequency of each and every element using the hash map then you are checking for the values of the hashmap that if it is greater than one then we have to opt that it is occurring more than once yeah right i got it this is what i want fine so okay yeah you can complete this thing is there any i'm thinking of is there any solution will without offense solution okay so you're asking for the uh a more efficient solution from over i'm just thinking that not o of n often time complexity is fine but i'm taking space complexity right yeah so i'm thinking that uh can i optimize that uh that of n that space complexity okay yeah yeah of one specifically you can think of that yeah okay so i think uh for that that you are you have given in question that 0 to n minus 1 right that all the elements should be 0 to n minus 1 so i can think with the that with the help of that hint that 0 to if 0 to n minus 1 only element is there let me i'm not confirmed like can i write here yeah yes sir 0 1 [Music] to 0 1 index i'm writing 0 1 2 3 4 5 and 6 so i'm just thinking of that one like if there is one i got occur one means you have added a one to the array also fine yeah but you have added a one here it's okay so now here you have this is the index what is this yeah this index index indexes okay fine i've used index for referencing myself okay yeah yeah i'm just thinking of that uh how can i make can i make it by keeping that element putting uh just just modifying the that array that minus one can i put uh if suppose suppose 2 is there so i will go to 1 index 2 minus n minus 1 index means this is 2 so i will put here minus 1 right if uh yeah yeah yeah i got i think i got the approach like uh i'm just discussing with you uh that is it uh right or not i'm not confirmed yet yeah that uh if i will make i i will make minus if i will put minus 1 in that array of that 2 minus one like uh there is two so i will get i will put uh that index two minus one is one so i will put minus one in one index like uh like when i will go to this so i already put minus 1 in this so i can think of that that 2 has already been visited yeah yeah yeah yeah okay so like in this example 4 in of index 4 like 4 like 6 so i already put n minus 1 means 4 minus 1 3 okay so you means you have to just put like if you have listed two so you have to put two minus one means uh minus one at index number one this is what you are trying to say yes yes okay okay okay so you you can also implement a bit of pseudo code for that so it will be more better understanding for us okay okay am i going i may am i going right yeah yeah currently it is not very clear to me because it's just uh oral talk maybe you will just when you will write a pseudo code then it will be more understood for me okay okay so yeah just refer referencing copy page name here yeah yeah just for you that yeah there is the oven solution possible also yeah you you are okay yeah you are thinking right away just do that so i think i will first get to an array so two i will find then i will put minus one in one index okay i will just uh use for dry iron yes so you can take you can take z one two minus one one so i will put minus one so it's already removed four so i will use three three minus one two okay okay so there's a chat okay okay you got it okay so i will just write the sudoku then i think i can make you understand better yeah yeah so if area of time then so you have taken a for loop or id from zero to n minus one means you have to traverse through the arena yeah yeah i will traverse through the array okay then i will uh like first i will go to first index then i will put two zeroth index means one number is one so one minus one zero so i will put minus one in place of fine then again if again one will come then that will find that uh a minus one already has been put in so if again one will happen then it is it will catch that uh yeah minus one already you have put it so means one is occurring more than one time okay okay okay yeah okay try to implement then we will figure out okay if i is greater than zero so then i will array of is greater than zero then [Music] i will put area of ie so you are checking if a arri is greater than zero fine yeah means you have not done it minus one basically you are checking that thing yeah yeah yeah but what if it is zero because uh the range is from zero to n minus one so it can be zero also or uh just one more have you have salted this area before traversing or not have you salted no i have not sorted okay fine i have not sorted i just uh keep vis keep visiting without sorting okay because because in the examples we are taking salty that is maybe there is unsalted array also yeah yeah it can it can happen so i'm not considering that sorted okay fine fine then it's fine so i will just i will use better than minus 1 then 0 x will cover right yeah so i will you i will put a r of i into error of i minus 1 okay one yeah what is first error of i is one so yeah one minus one zero zero minus one in this okay okay so let me give you one more one more test case to consider okay so for example that the test case given to us is okay so for example this is the test case given to us or let's say one more change is there yeah so for example this is the test is given to here you can see that the value of n is five or uh let's take let's take one more example so basically what you will do here according to your approach you will just traverse and then because there is a two so you will make it change it okay yeah so try to try to dry run this particular test case on your code i hope this is completion i hope this is completed thanks this is the yeah yeah so try to drive in this particular test case on your approach okay okay like i will just if so zero one two three four so two minus one one so i will put minus one in this and if i will go to this index okay if i will go like for like for this two yeah minus one here and if i will again go to this index so that one will be this one will be gone from its place that is the problem yeah that is the problem we have to consider so basically as your yeah your your approach was near you are very near to them yeah yeah closed approach but the thing is when you will change this value to minus 1 then the value present at that particular index will be replaced with a new value which is minus 1 so and maybe this are minus 1 will be a future index which we have which you have two traverse which you have to pass now so in that space you have lost your value that is present at that particular index so yeah you are doing your approaches you are quite close to the solution but you have to think something that your past value will not be so i will first check that you you can you can take your time you can dry it and you can use pen and paper okay so there is something in the chat we can just sort the array and check we can create a set of pairs and update keys and data ok ok but sorting will take n log n right so i will go to [Music] check if a rfi s1 okay yeah so you try to also uh consider all the different test cases as this is a test case which we have encountered which is not okay for that particular approach yeah okay so that will be more okay for a more efficient approach yeah okay okay okay you can take your time okay sure one if i will go if i will go to this okay i think i can zero one two three four five repetition okay if i win this wow okay we'll take okay then it is asking i don't get why is he not using has map you can you can go on okay what so it's uh yeah i think we are trying to observe our oven solution which takes constant space basically so we have discussed that particular approach using hash map but now we are uh considering our approach which will take constant time without taking any other space like hash map or frequency array yeah yeah yes yes i think i can little bit um it's okay it's okay if you're not getting that particular approach we we can discuss that thing okay okay okay yeah sure okay yeah okay so fine so yeah so the first approach which we have discussed yeah it is a brute force approach that we have discussed and yeah it is a great one so there what we have done is that we have a check for each and every pair of elements right yeah yeah so we we can yeah please to come can you please tell us once again that what you have done in your brute force approach okay so like uh here i had i already explained that i will just use the concept of two for loops nested two for loops and i will check and i will go at first i will find one like if like i find one then i will find in the whole array is any another one is present or not if that present then i will put i will print that element yeah yeah so and that in case in that case there was a problem like maybe there are some values which are printing multiple times which we are encountering multiple times yeah for that you have used the hash map as you have okay so yeah yeah yeah i'm just telling this approach over here also that yeah efficient approach fine tell us that uh first i will through the array and i we can make a frequency hash map or we can make a frequency array also okay yeah so i will we will just make a frequency array then i will again iterate to the array so then if if we will find that frequency is greater than one of that element then we will directly print that element okay okay yeah so we will take to the array we will uh create a hash map or frequency and then we will check the frequency of each and everything yes yes fine fine fine i got it okay so so let's take uh just a very small problem just related to this concept only because the time is going on okay so we'll take a just a small problem which is similar to this particular concept okay so and then we will also discuss more the both the approaches and also we will discuss how can we perform this in a constant space the first problem okay yeah so yeah so the just uh uh just the next problem okay uh so in this problem what you have given with you are given with the array okay and you have to sort the array according to its frequency so just let me write the thing for you for example this is the array okay so the output this is the input array here this is the input given to us so the output array correspond i hope you it is visible to you okay yes so yeah so the output is you can see that the frequency of two is most among all the other elements so we'll first print two here because it has the most frequency then we print four because it has four two frequency and then one and three sorry then one end like this okay i i hope you got the problem yeah yeah i got that yes so one of the approaches uh that again i will simply put on the again simply put all the element in the hash map then i will iterate through the hash map okay fine no can i sort it has map yeah we can i think we can sort the hashtag right or i can use the concept of yeah yeah we we can use hash map to store the frequency of each and every element and then we can sort that particular hash map uh based on the frequency yes but but to solve the hashmap maybe uh it is not possible so we can take a frequency array also no yes yes instead of enhancement because if we can take a frequency array or a vector or a pair of uh java so you can we can take pair the data structure custom comparator yeah yeah yeah so you can take that and then you can sort that particular we can do it like that yes yes so actually that uh so what you are telling that i will make up you can go with your approach actually yeah you can go with your approach yes so i can you can use because you you code in java you can use comparator with hash map also like that as you are told so you can go for that and actually the custom computer only not well command in that i know that this can be solved by a custom computer yeah so can you first please just uh store the frequency of each and every element can you do this yes yes yeah so yeah so for that i think that we can use a hash map yeah highest map also and uh that frequency is simply simply iteration also that like that one then i will put frequency like frequency of a rri plus plus like that i can make a whole array of frequencies yeah like uh i will just for reference i mean using i'm making the frequency array of this like zero index is zero like one index it is one like two index it will three three will come in two index and uh in the third index one will come now in the fourth index two will come okay fine which you are yeah yeah you are very close to the solution actually you are very useless solution yeah so i made that is what we have to do yes yes so yeah so i just make the frequency array then i will gray uh then i will or i will simply sort this short media instead in the reverse order okay in the reverse order yeah or i will sort this and or i will can travel from back side also then i will simply print that index with with the help of index also like index denoting the that element like 0 1 two three four five zero one two three four five four only yeah four so index here denoting the that element so i will if i will sort this array what i will get is accelerating 0 1 2 0 1 yeah yeah i got it yeah so yeah i will yeah okay okay so means we have to first just store the frequency of each and every element and we can solve that particularly yeah but but while sorting we have to uh just need of that particular index it should also be salted respectively yeah fine i that's what i i was also thinking so yeah it's a great approach fine so i i think that you can also tell the time complexity space complexity for this solution yeah as a time complex space complexity what the that maximum index can happen here yeah maybe like yeah so what the maximum element is this that's the space complexity okay yeah because if i yeah if i tell that the elements are from zero to n minus one only as in the first problem also so it will be yeah o of n over yeah and what will be the time complexity time complexity is often only because i yeah i'm iterating over the array only once for making the yeah that frequency but we are also sorting it okay yeah yeah sorry so n log n n log n the time complexity so you can you can write over there that what is the time complexity is complexity so time complexity is of and what in login of login space complexity is often fine yeah okay fine so yeah the second approach was very clear that we have to just store the frequency and then solve the elements it is very clear and also in the first two approach you have made a very clear approach like we have to first that the brute force approach were also good in that good principle we can also do like that that we can also check for each and every element of that because we know that the elements are from zero to n minus one so what we can do what we can do like that we can check for the zero element that if it is occurring more than once then we can check it so i was just uh trying to say that uh let's move to it is the same your code which which you have done we can start it from like zero from here and go up to n okay then we can take you are explaining no no i you are explaining something there okay for the first problem actually the first yeah yeah yeah yes yeah so this was the problem that if there's a given of size n fine so what we can do is that then what we can do that if this arr is equal equal to i because we are checking for this i intj yes then we can increment this c plus plus and if c plus plus is greater than 0 then we can output it then we can print it right so your approach was also a very nice approach and this is also good for the course that time complexity will be same yes yes and yeah again the second approach which we have discussed was also a great one means this is what we have to do we have to take a has now then we can restore frequency and that and then we can check for the frequency of each and every element yes fine yeah so yeah we were also discussing uh approach with space complexity of o1 yes so here also you you are very close to the solution actually but the thing was here you have made it minus one i hope you can uh yeah that's where i am yeah so you have made it equal to minus one but in this case what you have to do is if you will made it minus one okay so you will lost your past element so what you can do you can add this particular with n this this particular element with n and when you are checking here this arri you will check for mod of error with n okay because uh sorry so because when you are checking can you explain it with the help of that example you know yeah yeah i i will like so what uh what i am telling you is this is the example which we were having i hope you can see zero ones yeah yeah yes right so what i am telling you is that first of all what you will do here is a 2 present here yes so we will increase the value of the second index okay means second minus 1 because you have taken minus 1 here so but we will not take minus one because there is a zero also yes it is zero also now and zero is also yeah yeah so so what we will do because there is a two so we will increase the second element by n so in this case n is equal to 5 yes so now our first array will be 2 1 3 plus 5 8 4 1 okay now when we are at 1 so for one also you can see we will increase this particular because this is the first index now yes this is the first index this is the second index this is the first index so we will increase the first index by m i hope you are getting it yeah yeah yeah we will increment this one to six here in this case one yes okay now when we are here we have not we have not lost our three because we are checking for mod n value and the value of 8 mod 8 mod 5 will be 3 only so we have not lost our 3 here we have our creator in this case so when we check we will not check for 8 we will check for eight mod m so that is why here it is fine so now here it is three so we will increase the third index which is before he's present here like this and similarly we will increase the value of each energy now how we will check that which number is uh coming more than one time so you can see here that for this particular uh this second index or this first index if i take a zero by interesting so there is a six present yes so obviously if there is a number greater than n present means we have added n there so what we can do we can check for each and every arri and we can divide it by n and if this value air r by n is greater than 1 it means that that particular element is occurring more than once okay are you getting it yes no no i get it no just uh can you explain greater than one i will check yeah because because the thing is when it is because it is ranging from zero to n minus one because it is ending for zeros and minus one so maybe the the previous value is less than one less than n yeah it will always be zero the value of a r i n will always be equal to zero in the initial area okay yeah yeah because all the elements are less than n and when we are adding n to it then how many times and for each and every index we can add it one time why we can add it one time because obviously one is possible ah element can be present one time but yeah more than one time then we will just output that fine thank you yeah yeah so this was a this is a overnight a constant approach what is the time complexity for frequency array we have to just traverse through the frequency error so it will just take off and actually yeah so i was good yeah so i hope that you you got the problem and yeah you you both the approach were very nice means in the first problem you do force approach and that has map approach what exactly what i want and in a second problem also you have used the exact approach uh yeah that that constant space approach is quite difficult for it is just a difficult approach actually so if i rate both the problems the first problem was basically easy if i talk about the hash map approach but if we go towards the constant space after it is a medium or hard problem yes yes and if i talk about the second problem so it is a uh you can say it is a medium problem in which we have to count the fragments right yes yeah so now let's move towards the feedback session so now you can answer your screen uh okay so now it's okay yeah fine so yeah so first of all the way you explained your approach and the way you represented uh your approach it was a very good and there was one more thing which i like that when you are also writing on a paper you are trying to explain these things those things so it is also a very good thing to do fine so whenever you have you are writing one approach or when you are explaining it on in our document also then you are explaining in a very very fine way so it is good and the thing was that when you have to uh when you have to implement a particular solution that you have thought uh also try to figure out some other test cases also for example just that you have uh tell about that minus one approach and that was not possible for a particular test case yeah this is all from my side uh overall it was a very good uh yeah for me also yeah for me also it was a very great experience like uh for practicing purpose of just interview real life interview so it was a very great experience so if you want to ask something about you can ask [Music] yeah in the like question wise no i just only want some experience from your side that what we should in what way we should develop our dsa skills okay more like uh yeah can you just say a little bit your experience or something yeah if i talk about the dss this nbs is basically the your problem solving skills how you are approaching your particular dsa problem and it's just a thing of practice actually so whenever you are basically approaching a particular problem and for example if you know that this particular problem is from binary sets or this is from hashing okay so first of all as as we have gone through it in the interview also that we have to first think about the brute force approach and a more efficient solution right and the best thing to improve your dsa skills is to just practice just pick a particular topic for example if you are weak at binary sets or if you are weak as or some advanced topic dynamic programming it's just a thing of practice more you practice more it will be good for you to understand okay yeah yeah yeah so fine okay then uh so is there anything else you want to ask no okay that's it from yourself yeah fine so it was a great experience thank you thank you thank you thank you thank you so