Live Mock DSA | GeeksforGeeks

Key Takeaways

foreign [Music] [Music] [Applause] [Music] hi hi are you sure this course is just for 2499 yes and you know this is the only course with this expertise across the world no way yes way [Music] don't delay enroll now 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 foreign yes hey uh what do you mean by a self-paced 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 everyone a very good evening to all of you and welcome back to this live mock DSA interview session very pleased to see you all here and uh quickly in the chat section can you all please confirm if my voice is clearly Audible hey hi everyone Hi Ashok hi Sunil good evening pradeep all right thanks for confirming so uh let me introduce myself my name is suniti and I am a mentor at Geeks for geeks and today we are taking our life mock DSA interview session and our guest for today is stages and I will be adding him into the stream and then we will start the session so yeah here he is hi Tejas how are you I am fine what about you yes I am also fine thank you so they just can you quickly introduce yourself hello guys I am I am from uh I am from uh Pune I am purchasing my third year B Tech from vishwakarma Institute of Technology and I am in computer science all right teachers thanks for the introduction now uh before we start today's session uh could you please tell us how much would you rate yourself on the basis of your DSC skills on the scale of 1 to 10. oh not sure but uh I will rate myself seven eight out of 10. all right fair enough so uh your primary language is what C plus plus all right so let us start our today's session I will quickly explain you what I'm going to do is a document link has been shared with you right so you can share your screen with us and then in that document I will uh write down the question and then you can start with solving the question right you can first tell us our approach and then we can move towards solving the question okay to the coding path all right so if you can share your screen with us yes visible is there any issue from my side is everything okay all right so uh can you move to the document part I will be sharing the questions there great so your first question is who are human and sorted area of size and the world even and integer X need to return the sub array fixed the event Target okay I will just write a test case so for this case when we have one two three seven five without adding and our Target cell is 12 then in that case output is expected to be as 2 4 by 2 4 because starting from the second Index right till this third index okay which is two three seven the sum is 12. all right is it clear to you the question statement and the test cases you know okay are you facing any issues from my side like it's like voice clearly yes your voice is yeah so I got my Approach okay so uh see what you can do is first of all explain your approach all right and then I will share the question link with you and then we can go with coding path what is it okay so basic good first approaches to uh to travel all the sub array and count if we find the that sum in sub array then we will just return the that to index start and end but this will take over p n square and then the optimal answer should by using an order map so in which uh we can in each situation we can store the sum of some of some till that index in a match and if we find the sum minus K before uh before the math then we get then if we find the sum minus K so simply we uh uh we found that sub array in with somebody in that array which has some equal to S so we can simply return okay and how are you see you need to return the index value right the first index value and the last index value okay so we are doing like so in each iteration we can store the sometimes how are you going to do that uh to return the yes so we will store the an order we we will use our order mapping an order map we will uh store for that sum we will uh store that index only and yeah and in each iteration if we find the sum minus that value so minus expected value so from that index to till we we are iterating they can uh oh you can can you write this pseudo code inside the document okay so foreign uh sorry pages but what is K here what the variable key for you I write okay it did Yes actually yeah so if you find the sum minuses let us say I will explain it one by one it's directly on this basis how what what is my Approach one two three four five and yes is equals to 12 yeah example test case for your Trident approach yes sir so if we first for first iteration our sum will become one right and four and map of one will become some map of one we will store we will miss we store uh in map sum of math uh of the to that to that index like map of one is index zero then in second iteration the sum will become 3 then map of 3 will become 2 like that and in each iteration uh what you have written is snap at I is sum it means I is the index value right so for the current index value you are storing a sum at that for example at map at 0 it will be 1 at map at 1 it will be 2. okay yeah so and in each situation we will also take it some minus it we know sum is 2 sum is 2 and S is 12 so 2 minus 12 so 2 minus 12 is equals to minus the minus 10 is not presentation so it will not do anything then in third iteration our sum will become 6 right sum will become 6 and we will store and again we will not find anything and then in last iteration uh then again uh in next iteration like here is seven actually the foreign 13 and we will just take a we got 13 minus 12 is equals to 1 is present yes so 1 is present in I is equals to zero so we got like 10 from 2 index to index 4 we got our sub array sum is equals to that value then we simply return map of some minus k and current iteration here in BS okay uh Map Pack 3 will be one right map of three will be one the map of yes map of three will be one of the map of six will be two and likewise and up for fourth iteration we will find that if uh one is present so we will directly return map of 1 which is map of map of 1 plus 0 plus 1 sorry next next to that index like we will get one right so we will uh all right what is the space complexity and time complexity for this code yeah so time complexity will be uh European and space complexity also be a European all right uh we are doing a lookup as well right we are searching for an element inside the unordered map so is that not going to take any time yeah it will take time but generally uh we can we say that on order map takes a o up one for search nearly open what is the time complexity for this lookup thing inside an unordered map I guess nearly uh constant nearly constant yes you have to find something it's exactly constant okay so all right uh I have shared the question link with you in the chat section you can click on that link and then uh you know you can start recording this on the portal itself okay so I will put it right now yes thank you [Music] okay at the end you have written return minus one yes yes you cannot find that somebody okay but to return Vector right oh yes okay you can submit yeah so this passes all the fourth time limitation okay uh do you think this can be done without taking an extra space do you like you are using a map here right so uh do you think this question can be done without use of snap one give me one minute foreign see maybe we can do this thing that we can create a variable and like see what map is doing map is keeping the account of the sum that we have right and the index value till which we are having that value right so maybe what we will do is instead of having a map we can just have a variable right and then you can keep on adding the sum value in that variable tool and if at any point the say the variable name is current sub okay and if at any point the current sum is getting greater than the target sum then you can start yeah I think the values that is okay yeah so you can try that approach by just and it can be done with the use of a variable only right so in that case you won't need to use any extra space foreign can you uh first of all explain the approach what are you trying to do just uh I am doing like here if some become s then we will just simply written one I and one and I plus one as one base indexing if some sum of a some become greater than yes then we will just take uh like uh some if if some minus save some equal to s then we will just uh return the payout we have to finish uh take two variable I guess for Brave sum and to keep our index in that direction here thank you see if somebody if sum is getting greater than else right if current sum is getting greater than S then yeah you can keep a track of the first index and you can start deleting the values from the first index itself so that may be of help right here foreign foreign what is the concept behind some minus previous sum C what we can do is just keep on adding the current Aries element inside the sum right if at any point that sum is getting greater than the target sum then let us just start erasing the elements from the starting of the array right like keep a variable which is pointing to the start index let us say first of all it is pointing to zero right then if sum is getting greater than the target sum so it will start erasing the elements like you know current sum minus array at 0 then minus array at 1 minus R8 until and unless the current sum is greater than the targets so till that point you can you know keep on erasing the elements keep on deleting the value from the current yes so it's similar like two pointer approach on both pointer will start from zero yes so similar thing I am doing like yeah like I am doing a similar thing like sum Plus or if some minus Square sum has become then I just uh I will just return private index lesson if some minus creation is less than sum then I will do nothing but but it's a minus wave sum it becomes greater than S then I will increment the previous sum value save index sorry when there's some is equals to pair of Brave index and save index plus plus okay button foreign foreign thank you never even go to next question I got the approach all right we can okay so uh you were able to explain through one of the approaches right which was taking linear space in linear time so okay that's cool let us now move to our next question and the next question is uh I will just type it in third document you can open your document where I will be giving you the next question yeah yeah so um largest animals inside the array right for example let us see all the summaries press fight scene and then 123 and let us say the value of K is 2. so two largest elements here are seven eight seven and twenty three all right so you are given an array and the size of the array is n of course array is not sorted and you need to print the K largest Elements which are present inside the array all right so let us say this is if your array then the first largest element is 787 right and the second largest element is 23 so that is the output okay and keep in mind the output should be reverse order that is the most large element should be printed first okay so yeah this is your question you can go on with solving this yeah so I will tell you my Approach so let us know and then you can start with yeah so I will uh I will give my Approach so first approach will be sorting the array it's the simple one so it will take a n log in complexity this uh your login complexity we can do just sort the array and if we sort the reverse then if we sort the reverse then from 0 0 to K till that index we can zero to K minus 1 till that index we can uh that element will show store in vector and we can return that element so it will be uh n log and complexity but uh using priority queue we can do it in a time uh time complex setting of uh n lock case only n log k uh yeah uh not in in login only but uh we can reduce uh yes so like uh what approach you are going to use here I will use a prioritical um sorry time complexity will be and login only but uh and it will take up this complexity I guess oh okay by using priority queue okay so for the priority queue time complexity will be n log n right um 125 . well it will be okay first of all let us know your approach how are you going to use priority queue help right so we will use a mean hip we will use my mini heap and not maximum yeah so by using uh then we are doing just like uh yes so if we do a uh if you use a maxi then it will uh if you do Max it then wait a minute okay what is the difference between a mini heap and Max Heap yeah so uh in mean hip the top I mean hip the uh for a maxi the topmost element is a greater element and in a mean if the topmost element is a minimum all right so here we are printing the largest elements inside diary then why we are not using Max sheet and why we are using mini pair so we buy we can use max hip too I guess but uh it will take I guess uh Co-op space complexity will be uh n Only and what will be the space complexity in terms of mini uh in terms of in terms of mean hip it will be a soft key because we can just keep a track like uh if we got the okay if we put the K element in mean Heap then we we can just uh for your the furnace next situation we will say if the topmost element which is mean in a Max elements right so it so it mean in Max elements it uh less than that uh that element then then we will just simply pop it and insert the next element but if it is not then we will just pass that iteration like that this weekend the time complexity just maxif will take uh n complexity and mean Heap will take off lock here complexity what is the time complexity for the hippie file process login yeah logo login login log open sorry I didn't hear you what is the time complexity login okay okay maybe you can yeah maybe you can start with solving the question right uh first of all let us know your approach inside the talk and then I will share the question link with you and then you can solve it in there okay okay yes you are thank you yeah you can start with uh explaining your approach inside the dog okay uh am I clearly audible to you approached go ahead yeah so first we uh Define a priority queue priority queue we mean hit and just uh iterating over the array okay iterating the iterating over the array then from K to n we will check if uh top of where it tissue to less than there's been a r of I then simply pop out and push that element in priority here else we do nothing and at the end we just simply uh put all the all the element in vector and return it okay tell me one thing why you are iterating till K only yes so yeah so first we will just uh store all the elements till uh K in a mean hits then we will just then from that uh from that then if we get the next element then we will just check the top of the mini if it's it is less than that element then we will just simply pop out that and we will push the new element into our priority View suppose K can be anything so firstly we have to put that uh K elements into the domain here then from next element we can start comparing do you think uh traversing till K is going to work and you don't need to Traverse the entire area foreign go to the portal and you can start your coding from there okay foreign wow [Music] thank you great uh yeah so you have used a priority queue and what you have done is you have inserted the elements and okay so see uh this could also have been done like you can just you have done here like one iteration from zero to K and another from K to n right so instead of that you can just directly Traverse from 0 to n and if the size of the priority queue is getting greater than k then in that case as well you can pop out the top row statement okay yeah but that button will also help now tell me the time complexity of the code or can you just open the code that you have written yes the time complexity will be just here again login okay can you please open the code yeah so my screen is visible time complexity will remain same yeah so see screen is visible what is the time complexity of this code you know what I guess time complexity will be again login only but uh the coin complexity will remain less than salting the entire but it is still be in login I guess hi you are seeing a login y n are you inserting all the N elements inside the priority queue yeah like from here we we are inserting K element right elements and now here we are again if we get the topmost element or less than a arri then then also we can uh doing a push operation so I guess it will be definitely above n log k University okay so inside our priority Queue at a time inside our priority Queue at a time there are only K elements right or if will there be any time when there are more than K elements inside the queue will there be any case like that no yeah okay so in which cases time complexity will be unlocked exactly our time complexity will be K lock K okay because inside a priority Queue at a time there are only K elements right there are not more than key elements inside it okay so time complexity will be K lock key for this code this is clear but I guess are you able to get the point why it is scale of K and I I'm not sure about K lock K or Ian locks I thought it will be unlocking if I am not fine are you able to understand why it is scale of K I thought it will be unlocked I guess all right also uh did you hit my point why I said it should be Kayla uh I am not sure about uh K lock K or Ian lock okay I guess it should be unlocking okay yeah see we are what is the time complexity for the hippie5 process uh it will be login or a number of elements it will be log K right yeah the number of element is k then it will be locked okay exactly and and why uh you are multiplying it with n because we are traversing for all the N elements inside the array right yeah okay so what my point what is the time complexity of the port and uh what will be the space complexity of this code State complicity will be okay only off okay okay cool all right so uh that was all the questions that we had for today and uh let's just move to the feedback question all right so uh okay first of all you tell us like how much would you rate yourself on the basis of this session that we had I will rate myself 8 out of 10. first of all regarding the first question okay uh can you share your screen and go to the first question that you have solved you know okay so in the first question you were able to reach to our approach right you started from the Brute Force approach and then you reached to an optimized approach but uh still there is an approach that is more optimized than this right and interviewer expects you to to reach to that most optimized approach right and also uh the thing is that you should be walking a little bit on your communication skills right because see while you are doing something first thing is that you must think out loud cool so like more loud you will think more easier it will be for the interviewer to grasp uh what you are trying to you know explain right so that is the first thing you must be very communicative I felt a little bit of lack of communication from your side and also I think that um some point maybe you were not able to get my thoughts as well because uh in this question I explained you that you know maybe we can try just taking a variable and a checking if it is getting greater than the current sum or not or whatever approach I was suggesting so you did the right approach no doubt that's right but the thing is that you must be good at communication okay you must be able to understand what the interviewer is saying and you must be able to see what you are saying okay what you are doing you must be able to say that okay other than that you did good in this question uh press like as because you were not able to reach to the most optimized approach so maybe we can keep it a 7.5 for this question right and for the K largest elements yeah for this question as well you did right okay and uh uh no n hints were required for this question and also uh everything was good for this question but yeah again I would say that in this question as well there was a little lack of communication okay once you are able to explain your thought process well cool or then you know people will be able to understand what exactly you are doing and where you are heading to right so you know that's how we work in team so you know everything except for that everything was good in that question you were able to reach to the correct approach and you figured it right so I will give you eight for that question and yeah overall for this interview we may rate you as around 7.5 in all for the session okay it was a great session and uh yeah certain things were good like you were able to reach to the optimized approach logic was clear in your mind and so that is what we have okay so anything from your side Okay so thanks for being here with us thanks for you know uh taking part in this session I would like to thank you uh dear victims for beginning this opportunity yeah you're most welcome gfg is always there to help you all right so uh all right and also one thing that I would suggest you in the first question if you feel uh like you were not able to get to the most optimized approach right so see that was an easy level question right and there is always a certain time that is allocated for the questions right so if at any time you are feeling that you may not able to get to the most optimized approach in that allocated time window then uh you may ask the interviewer to move to the next question okay because it will you know give you more time for the next question it will save some time right so like you know rather than utilizing time in the current question try to move to the next question okay if any idea is not popping in your mind cool so yeah that is all about today's session uh thanks for being with us and yeah we wish you all the best so thank you bye teachers bye all right guys so here he was we had Tejas with us and uh there was Interview session as you saw uh some things were good like he were able he was able to reach to some final approaches starting from the Brute Force approach and there were something like uh he should have been able to think out loud right so yeah that's the thing at some point of time we all need improvements right there is an always scope of improvement all of us are in the learning phase so yeah any feedback from any of you and if you are any of you is interested to take part in this sessions then do fill out the Google form that is in the description section and I'm very pleased to see you all here attending the session and let us keep up the hard work keep up doing the work because you know we all are learning something every day so any feedback any suggestions are welcome okay and do fill out the form that is uh there in the description section of this video and we will be coming back with uh more such amazing sessions with more such amazing questions right so keep we stay updated stay tuned two gigs for gigs and keep up doing the hard work thank you guys bye everyone