Live Mock DSA | GeeksforGeeks

Key Takeaways

foreign [Music] [Music] [Applause] [Music] foreign 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 Jake's learning together foreign 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 yes hey uh what do you mean by a self-based course well the course material is available in the form of video lectures and there are multiple practice problems that come along as well so you can access all of it anywhere anytime and they are available to you for Lifetime no way oh yes way don't delay and enroll now Geeks learning together hey uh very good evening everyone welcome to this amazing life mock DSA interview session and here we are yet again back with our another episode so uh firstly let me introduce myself my name is suniti and I'm a mentor here at Geeks for Geeks so let us add our today interviewing and here it is Hi gopal how are you hello man I am great and how are you yes I'm also doing great thank you so uh let us start with your introduction first sure man hello hello ma'am and hello everyone I am Varanasi well I love to solve problem that's why being the non-cac student I chose the software profile as a career because I feel the role of the engineer is to solve problem and if we integrate a problem solving abilities with Technologies then we can solve problem in a large scale well I also had done an internship during my college days with iot and solution private limited where I get the exposure of java Tech stack or m2s like hibernate oh crawling and scrapping tools like selenium beautiful HTML unit and also apis like Google's recording API I also have clean interest in project development sorry about the few projects like MVC which is built on the top of NVC design pattern sorry the project name is e-nose and the other projects are due to Chrome extension and chipmunk which is basically a crawling and scrapping tool and apart from my technical introduction I love to play flu cook and travel that's all about me great gopal that was a wonderful introduction so let us start our today's session I'll just tell you what we need to do is a doc file link has been shared with you so I will write down the question there all right and then after that you can you know start with your approach you can write down the pseudo code and then once when we are done on that part I will share the link for the gfg practice portal and then you can code there all right yeah can you please share your screen yeah man is it visible yeah it is visible uh can you open the doc file okay so let us start with our first question and that is given an array of n integers considered it as a stream as a stream and out it largest element in stream it does not exist minus okay okay so let me help you with the test case see say this is okay so what is this that an array of size n is given to you all right you need to consider it as a stream like a continuous stream of integers and what you have to do is that for every element you have to print the kth largest element like for say example the array will be like just one okay and the K that is given to you is 4 right as you can see here so the fourth largest element when the element is only one the fourth largest element will not exist so that's why it is returning minus one all right so in the next case when we have two Health in that case as well the fourth largest element is not there so it will print minus one when we have three here in that case as well the fourth largest element is not there so it will print minus one but when we have four here we have our fourth largest element as one all right fourth is the first largest element three is the second or third largest element two is the second largest element and one is the fourth largest element right so in that case we will be printing world when we have five in that case we will print one like two two is our fourth largest element and when we have added six so in that case the fourth largest element becomes three right so you are getting my point how are Aries like is one then our array is now one two our array is now one and three and now here our arrays one two three four foreign yeah so uh this is the problem statement let me know if you need any clarifications no man uh the question is asking that uh we have given an input of array and okay and we need to return V for every index we need to need to return the create largest element in the screen is I am right exactly yes till that point what is the kth largest element okay till that index value okay okay let's suppose uh we are at index left of course we are at element five then our fourth largest element will be two yeah exactly it will be three yeah so um first thing is coming in mind that uh the array can be um have duplicate element or not uh array is not having duplicate elements okay okay so for nothing is coming in mind that um we will uh what can I do let's suppose we will run a loop for every element uh let's suppose we are at index 4 and we will move backward so it will be one two three and from there we will find the fourth largest element which is the largest element that will be um we can simply we can simply add into the array or we can add into the error disk and simply we will and we will sort that analyst and from that point we we will find our clear largest element at TM minus 1 for example let's suppose we are at uh we have the element one two three four five six and this index will be 0 1 2 3 4 and 5. so let's support our I which will iterate into the array in four at four at four index and element will be 5. so we will move back forward and we will we will get that element and our element will be one comma two comma 3 comma fourth and what you can just simply we will just come on you are moving backwards from fourth Index right from third index from third index you are going backward right so you have written the requirement as fun uh yes man sorry uh my bad uh we will move forward from backward from Fifth Fifth Element that means fourth index okay so you are moving backward from fourth index and uh like you will move backward till K minus minus right I'm until fourth uh position we will move backward to the uh zeroth index and we will take all the element okay okay and like you will be using a data structure to take all the elements or something like that uh I will take the RLS in Java okay and then I will sort the array then I will find my K minus a create element at a minus 1 index all right so that you will have to do for all the elements inside the stream right going backwards correct yeah correct so ah listen uh I will tell about the time complexity then for we are moving through a look virtually we go off and and what we will be doing we were moving backward so it will be the uh we go of L square and plus we are also uh sorting the array so it will be and we go of n square plus log of n at worst case yeah it will be big of n square and can you write the pseudocode for this and also your uh the space complexity you are using an additional data structure as well right it really big off and okay now I also have a better approach yeah please can you share that with us yeah I will uh for now what we are doing for uh each element we are moving backward and we are sorting so what can we do this is simply when we are moving forward we will put that element into our data structure like priority queue okay and from that point let's suppose uh we are let's suppose we are at index 4 and our element will be 5 so we will put all that element in the priority queue it will be one comma 2 comma 3 comma four and what can we do no no what can we do here we will we will need to find the key at largest element let's suppose uh for now we don't have any stream and we have only an array then how can we find the key at largest element uh so for that I am getting the problem into smaller problems so we can add that so we can get our approach of bigger problem so for now I am thinking I am thinking we have not the stream we have onion array so what can we do we will put all the element in our priority queue then we will simply we will simply and we will make this private view uh and we will remove that element if our practice queue dot size is greater than K and at last we will get our kth element am I right for the if we don't have any string uh let's suppose uh three and we are equating with zero index then we will fill try to give it one two and three now we add 4 we will fill that with four and what we will do we will simply check if our product view dot side is greater than k then we will remove that element from the top of the product review so we will remove uh we need to find a clear large f so yet larger so we will remove the largest element yes we will know the largest element no no you said you will be using mini right yes I am you I will use the main hip and and if my priority research is different than occasion we need to remove because I know in my priority queue uh the element has the element so which element I need to remove maybe I need to remove the maximum element or minimum element so it will be I will remove the minimum element and then yes I will remove the minimum element from that from that there so I will remove that then again I will put in the priority queue I will check you will do this remove operation when the size of the priority Q is greater than K write correct fans so when it was one two three four I don't think the size is greater than k what I told you uh for now I am not thinking about the stream only I am thinking about the array I need to find the clear largest element for from this for this array so what will be our answer Solomon like you are trying to find out the case largest element in this entire array right from one to six okay yeah so let's suppose our third largest element is for our create value four then our create larger element is also before so what I will do uh I will check first of all I have now what I will do I will add into private Q5 then I will see if my plenty two size is greater than K I will remove the minimum element simply then again I will fill the particular reflex element and again I will check yes my science is fine but we want only four elements so we will remove this two so it will be three four five six and what we need to return we need to return the here's largest agreement and for 4 for our create largest element of three and am I right okay if the array is from one to six then fourth largest element is three if I am correct yeah that is correct so I got exactly what you are doing so uh yeah okay proceed yes uh this is not for the screen but now I will think about the screen what can I do for that okay we are creating we need to integrate we need to find for how can we get the key at largest element foreign check we will check if our price TQ dot size is less than k then we will simply add in our answer minus one yes we need to return minus 1 because yes I am making here the answer array and I am I will do above priority queue so I will add I will add private view that is name like PQ 1 then what I will do I will go for the next element so it will be two I will fill that element with in the priority View and again I will check I can see my private Q5 is less than k so simply what I will do I will simply add minus one so yes it is correct again I will fill with priority queue with three and again I will check uh is it less than the K value is 4 okay okay so I will add minus one now what I will do I will add 4 here now what I need to check foreign I can make the maximum Heat or the main Hymn for here so what I'm thinking I will make the map zip here yes let's try so we will you know we know in our maximum name the clear largest element in the top so we'll know we need to maintain the Millet yes we need to will hit so what can we see in our project is equal to K so we simply we know that our clear largest element is one so simply add this one now what we will do we will add another element that is five and we can see our privacy size is greater than K that is greater than 4 we simply remove that one okay I'm now our size of priority or Min if is equal to okay we can simply make our answer now again add the next element again we can see the main hip size is greater than okay we will simply remove and now our answer will be three so I think this approach will work minus 1 minus 1 minus 1 minus one one two three all right gopal this approach seems fine uh can you help us with the time complexity and space complexity of this approach yes ma'am here uh now as the previous approach we are using the priority view in the same approach we are using private DQ so it will be we go off not n but it will be big of K because in priority we are adding only the kth element maximum so our space will be bigger of K and our time will be n into log k y l because it's written over the all the array and by log K because in the private view we know if we add or remove then it will take log N means log K the size of the private View and we are removing here and the size of it try to use K so it will be log a our time will be n into log k and space will be k yes all right so uh inside the priority queue what a data structure are you exactly implementing I mean what you are implementing through the help of priority queue uh we are implementing the Heap because okay so like you are implementing heaps so what exactly in the Heap is helping you to sort the elements in the priority queue I mean how it is happening as we know man uh private you if you make the minute then we know uh in the let's suppose we we make a priority of four or four sides and it will heat then I know in the top of the priority queue it will be fourth element so I am maintaining a practice of 5K that's why foreign discount okay so yeah what is that process which is exactly keeping that four at the top or you know what is that algorithm and what what is the time complexity for hipify uh it is yeah in this case it is log of K because hipify is done over T elements here okay okay so yeah the question statement has been shared with you so if you can please open that link and you can quote there or do I no this approach is fine no the approach is fine you can start so we have given the a array and the size of the array that's okay so as you are discussing we will run a loop and we will use the private view data structure it will be and it will be an integer time a name I will use Mini and it will slice a project you okay then in Java in Java it is if you don't need something to specify then it will be a mini okay then what we will do we need to iterate over the array create over the array okay so what we will do we will simply create with our eye pointer length and I plus plus okay then what we will do simply we will add the elements first this is First add the element array of I so for now let's suppose in our practice view one is added then we will see yes my priority dot size is less than a then in answer I will add minus 1 and also I need to take the answer array so it will be in length okay now what we will do uh there is a condition now let's suppose one two three is added and now 4 is added so this will not to True condition so we will humanly else condition and we will see if if our relative to size no will simply check the two three four we have two conditions now here uh it can be equal to or it can be okay okay then fine for me if if it will be size is greater than a then what I will do I simply remove that element and now my practical side is confirmed it will be a size of K so I will add into my answer So my answer will be priority queue dot Peak but I am using many sorry so at last what we will do we need to return the answer okay so first let's guidance so I will add one minute then what I will do I will check it is less than K because it is less than k then I will do nothing I will continue then again I will add two okay then what I can see it is again with less than k then I will add my answer minus one okay again I will add and I can see again it is less than k and I will simply add minus one and continue then again I will add 4 then I can see it is not satisfying it is conditioned we will came into the health condition and we will see that the size of the priority field is not greater than k okay that's fine then I know my minimum will be at the top the tth element will be at the top so I will take it one in the answer then again I will continue my Loop and five I will add then what can I see uh this condition is not satisfying I came to the else condition the size of the private Q is greater than K does that satisfying the condition I will simply remove that and my next element will be 2 yes and I think this approach will work all right uh so can you just do this um compile and run I guess oh sorry okay for five number it is clear and again a million we are passing the sample test case okay so you can submit it okay okay great so um that was about this question uh you performed great and you explained quite clearly everything about your approach so okay let us now move to our next question and uh that question is okay I'll just write down the question so you are given upgrade and the elements are one two three uh sorry zero one two three okay find out if a path exists from source to destination okay and your Source Point is your source is sell with the value one and your destination is cell with the value 2 right and also if the cell when yeah if the cell value is zero this means that we have a wall here wall there and means you can't move through that cell okay and if Cell value is three it means that that's a blank set okay that means we can move three yeah yeah you can move through the blind cells you can't move through the walls one means that we have a source there and two means we have a destination there okay so basically you need to find out whether there is a path from one to two okay considering that zero means small you can't cross those cells and three are blank cells okay and uh how can you travel Traverse in four directions okay okay so everything's four directions that is up down left and right okay so that is the fourth directions in which you can travel and let me help you with the example okay so let us say this is our grid okay so this is our grid all right so here just say let us say you want to see the sources here okay the source is at one okay from this cell you want to go to the destination cell which is here all right so as you can see there is no any path as such because in this grid as you will see okay if you are at one then you can either go to this 0 or this 0 okay okay yeah so uh there is no any paths there is no path to reach three one that is a destination from The Source right so basically you have to find out that if you can reach to 2 okay with the help uh you can reach to 2 starting from one right so that is the question and yeah you can first start with your approach then pseudo code and then we will go to the practice link okay uh first I want to clarify the question that we have one that is for two battery destination 0 that is blank cell and three that is wall sorry zero is zero is wall actually let's see Zero is wall actually 0 is wall so yeah foreign yeah uh empty cell exactly and 0 is the wall okay and ma'am uh indicate it is always one and means that source and that destination will present yeah always there will be a source there will always be a discolution and there always be a single occurrence of source and destination okay there are no multiple sources or there are no multiple destinations foreign destination uh I think the first thing is coming in mind that we can use the VFS approach uh we can use both VFS and BFF but for now I am going with the BFS approach and what I will do in my in BFF we are using a few data feature so in Cube what I will do I will simply add the source first that will be uh index it will be let's suppose it will be X comma y for now X comma y that is the coordinate of the source index then I will move the in the four Direction and for moving in the four Direction what what I will use I will use the direction array in my direction array what I will do 0 comma 1 comma 0 comma minus 1 and minus 10 comma 0 so 0 comma 1 is the horizontal right right direction and one comma 0 B 0 comma 1 is the horizontal right direction zero comma minus one is basically the horizontal left Direction one comma zero is upper vertical Direction and minor sorry it is not down down one and yes it is the up upward and 50 downward so we have all the fourth Direction so what can we do are you sure one comma 0 is for Upward Direction because you are keeping your Y axis constant so I don't think there is any difference in the vertical positioning maybe that is for left and right and zero comma 1 and 0 and minus 1. yeah see zero comma 1 is basically the the right direction and zero comma minus 1 is basically left Direction Direction no no no no no no okay you can just go ahead you have added the four directions it's okay just go ahead yeah yeah okay and now what I will do from The Source I will simply go to my neighbors right up over downward and backward move left so it will be X Plus direction of uh through the direction of I I if pointer to it creating me all the direction array and I will move the x with the zero chord the X direction of zero and we will get my X new x coordinate mu mu x coordinate and what I will now what I will do I will try to find my new y coordinate and it will be why plus direction of I comma 1. so uh we will get our new X and mu y that means we will we are able to get our neighbors and we will move to the neighbors and we will check my neighbor is a wall or not if my neighbor is wall I am checking the condition that is my neighbor are walls or let's suppose we move outside the grid outside grid then what we will do we will we we will not go there then we will go we will go only when there is a blank cell and that is the three empty cell so from this way we can reach to our two we can go to three okay and we can see now we we are not able to go anywhere and also one thing we will maintain the visited array let's suppose for now I will make it minus one uh that will help me that I will not go there again so I will go to Upward downward right and left I can't go anywhere from this so I can't do nothing and in the same way I will approach to all my neighbors I think this will work okay and what do you think is the time complexity for this code time will be big off and into M because we are equating to all the cell and space complexity will be we are using a few data structure so let's suppose all the cell present uh can reside in the queue so it will be also n into m all right okay seems fine so let us move to the coding part all right I will just share the link okay so these two conditions that you have mentioned that if neighbor are walls like when you are traversing in the neighbors and if you are traversing outside the grid then in that case you will stop the traversal right I will know what I will do if my neighbors are walls and outside the grid then I will not add into my queue because they are not valid Neighbors yeah so do you think there is any other condition that you need to add here or yeah cool so I have shared the link you can uh yeah to see it with the link so as I told you earlier I will use the BFF approach okay so I will you will take few data structure in view I will add the I can use to click list here okay now what I will do first I need to find the source find the source coordinate so it will be so X and for now it is -1 it is so why for now it can be minus 1 and we will try to remove the Matrix uh and for that I will oh hello goodbye all right I don't know if uh someone can please in the comment section confirm if the problem is from my end or if whether he has stuck foreign guys yes so everyone uh till he will be rejoining us uh you all can share your approach like okay uh how do we share candidates for mock interview as you all can see there is a Google form Link in the description so you all guys can fill it and then we will be selecting the candidates for the mock interviews like usually we select uh you know mostly all the people who fill the forms so that is how we do it so make sure you are filling out the form that will be great until then you all can you know share your approach what you guys will be doing if this has been the question thank you DFS right I would have also preferred DFS is Okay so it's okay last problem was harder that was the case largest element in this stream yeah okay but his approach was quite well for all the questions I mean he explained like you know all the test cases he did dry run for everything and all so his Concepts were quite clear let's just wait till he is joining us now are you guys you know doing this potd thing like that we have daily and then you know you all guys are going to get amazing goodies vouchers after completing those potd on daily basis so make sure uh you are doing that as well yes of course he's all right uh the problem is with his internet connection so let's just wait he will be rejoining us and if there is anything any suggestions any feedbacks from your site please feel free to add it in the comment section right and yeah we will just look into those and we will try to Implement and also if there is any interview experiences of any of yours so please make sure that you are sharing that with us as well that will be very helpful for everyone who is preparing for their upcoming interviews again for that the link is in the description section so these are the things that we can do you know we all are here or just learning together and everyone is in the learning phase so we can help each other for this also if there is you know anything any sessions or any series that you want from us so if there is any those ideas please share that in the comment section as well we will be very happy to implement them if possible and keep practicing thank you okay how many of you were in that SD sheet series that was the 30-day streaming you know wherein we used to solve three questions every day from the SD sheet of the Geeks Who gigs so that was also quite uh amazing Series so make sure you are accessing that as well all right guys so seems like you know he's having some internet issues from his side so uh okay I'll just share the feedbacks so as we saw that in the you know first question he did amazing like uh he first started with a Brute Force approach and then he moved towards uh using an optimized approach with the help of a data structure so that was a very great idea how he started off and you know how he implemented everything and the one best thing was that he was able to do the dry run for Brute Force as well and for the optimized approach as well so there he performed extremely well and for this next question as well he was able to explain his approach right uh I guess he would have coded it as well because the approach was clearing his mind so all in all we can say that you know it was a great session he knew what he's doing his communication skills his confidence and his problem solving skills everything is great so uh we can say that you know that wasn't I like you know you all can say that you know there was a lot to learn from this interview session because everything went quite well so uh that is about it so yeah that is all about the feedback for this session we can rate him as nine out of ten so that was about it and any suggestions any feedbacks you all guys can add in the comment section and thanks for joining us and make sure you are filling out the forms as well that is there in the description of this video so thanks everyone keep up the hard work and keep on practicing bye everyone foreign