Live Mock DSA | GeeksforGeeks

Key Takeaways

foreign [Music] 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 Geeks 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 wait don't delay and enroll now Geeks [Music] oh hey hi everyone welcome to this amazing live mock DSA interview session where we conduct live sessions with our candidates and very happy to see you all here and taking part in these sessions that we are conducting so uh let me introduce myself first my name is suniti and I am a mentor here at Geeks for geeks and today we are having with us uh our next interviewee so let's just get started and yeah I will just add him to the Stream hi Suraj hello ma'am Hi how are you doing uh ma'am can you repeat like your voice is cracking yeah how are you doing like how's everything going ah very nice ma'am all right that's great to know so uh can you please just uh introduce yourself uh hello everyone hello ma'am myself Suraj Patel pursuing B Tech from group in computer science department okay actually I am finally a student uh passed one and 1.5 here I am doing competitive programming I am a high five star quarter on code set i'm expert on board forces and I'm a guardian okay and uh in this summer I have interned at zero lab in software developer software field that's great Suraj that's quite an impressive profile that you have so let's get started I will quickly just inform you what we are going to do is a talk link has been shared with you right foreign so uh I will be giving you the questions in that doc link and then uh you can start with explaining your approach and then once we are done on that part then we will move on to the coding part wherein I will share you the link for the gigsaw Geeks practice portal all right yeah let's get started I will just help you with the first question of our session and that is okay before that can you please share your screen uh I have chairman I think the screen is not visible uh are you sure on that part that your screen is okay just disabled yeah all right and uh you can open that all right so the question is given in Array of size n find the next that each let me give you our first test please just say um okay so yeah this is our question and that is given to you at the size of the Aries and you need to find the next greater element for each element in the array all right say for example the first element is 1 so the next greater element to one is three all right and our next element is three the next greater element 2 is 4 right similarly it goes from two and four four as we are not having any next greater element to it so that's why we are printing one okay so okay yeah that is a problem statement that we have here so you can start with your approach uh what I can do from here I'm like I can run a flow for each element and for every particular element I will be running another loop inside a loop I will be running another loop if I am getting let's suppose uh for this example together one three two and four okay first I will be iterating every element for I will be checking for one then three then two and then four then after that I'll be running Loop for one from index of one I'll be going further if let's suppose I am going 3 here I am getting 3 greater than 1 so for one the answer will be 3 and for 3 I will be running low uh next to the two I will be going on to the next to the four here I am getting 4 which is greater than 3 or 3 I will be matching we do four so then for two I'll be running low from 4 I'll be getting a four so here answer 4 and for four I am getting nothing so for 4 answer will be management for this for this approach my time complexity would be very high it is the order of n Square so for the optimization purpose I can use a stack I guess a monotonic aspect let us take contains uh this data structure that contains increasing order of the element I can say so using a stack I can do this in O of one time complexity so I will be iterating from the backward so for this example one three two and fourth for this I will be maintaining one a stack so initially my stack is empty and then I'll be iterating four for the 4 my stack is empty so the answer will be minus 1 for that like there is a four space for four answerable management then in my stack I'll be pushing four then my stack content 4 okay so next for two I will be checking top of the stack if I'll be treating uh I'll be checking if the top of the stack having less than of my current element then I will be popping the element if I am getting the element just greater than my current element I will be like considering the answer for that particular element so here the top of the element is 4 so for 2 my answer will be R2 and the next my stack contains 4 and 2. then I will be coming to 3 and I will be checking the top of the stack so my stack contained 2 so I will be popping I will pop in 2 because 2 is the smaller than 3 so I need now again I will be checking for the top of the element top of the stack which is 4 and which is also greater than 3 so for 3 the answer will be also 4. and for and again I will be popping I will be pushing in a stack three so my current strike is 4 and 3 and then one for one I will be checking top of the stack that is three and also greater than one so for three for one answer will be three this is the my Approach okay uh so what will be the time complexity of the approach and space complexity as well the time complexity of this approach will be order of n and a space complexity as well will be order of n all right okay your approach seems fine to me and I will just share the question link to me yes uh I've shared the link you can go ahead and then you can type your code inside the folder so should I start with optimize one or okay so first I will be checking I'll be taking there is one answer Vector then I will be taking one empty stack then I will be iterating my array from the backyard then so here first I will be checking if the stock stack should not be empty then also I am checking my top of top of this tag if less than or equal to my current element that is arri I will be popping so if I am checking if that stack is not empty this means I got the greater just greater element to the my current element so answer of my ith element would be St of top and then I would be pushing my current element to that step and then at last I will be returning my answer I am again explaining here I am taking answer vector then I am taking one stack okay and then I am checking for the every current element first I am checking if what if my stack is empty or not if the stack is not empty then I am comparing the top element and my current element if the top element is less than or equal to the current element it means it's not greater than current element so I am popping that top of the element then again I am checking if the stack is not empty it means the top of the element the top of the stack element is greater than my current element so I'll be assigning answer of I equal to the top element assigning to the answer of it then I am pushing a current element into the stack and then at last and returning the answer so should I have to submit yeah you have to submit it oh great Suraj that was a really nice attempt by you like you solved it just in the first curve without any kind of hint required help required so yeah that was great so okay we are good to move to our next question all right yeah the next question that we have here is that okay yeah so let me just let me have this [Music] [Music] yes [Music] about your time of the tree [Music] I love them [Music] platforms required so that all the trains can move okay we'll just help you with the test case okay so let I'll see the size is given is six okay we have two arrays here that is uh arrival area departure array all right so what we have here is that arrival time of trains are given in departure time of the trains are given okay so what you need to do is you need to print out that how many platforms are required all right so all of the trains can arrive and depart from the particular railway station cool so here as you can see uh the old part arrival and departure time is arriving at nine and departing at departuring at 9 10. all right so for this we will be requiring one platform and then next is uh starting from 9 40 12 as uh in this case we will not require uh any new platform right we can use our one platform that was already there so that's why answer remains one but here we may require another platform when the arriving time is 9 50 right so that's why the count is incremented to two and in this next cases we will be requiring a new platform for the arriving time of 11 and does the count has been incremented to three so that is what we have our answer okay so yeah uh that is the question so you can uh is the question statement and test case is clear to you yeah my first approach would be of n Square what I am doing first okay one one doubt is there like arrival time is sorted order like always in the sorted order no no no none of the arrays are in sorted order so what I will be doing I will be okay first time telling uh my Brute Force approach so Brute Force approach would be I need to I think I need to sort the array so I'll be sorting the array uh according to the arrival time and then by Brute Force I'll be checking for the every platform so what I mean so let's suppose I am taking the first frame okay the enriching to that like I'm assuming there is no platforming in select so there is one platform okay and the trend one is reaching so train one so the first thing that you have done is you are sorting your arrival array right yeah arrival array okay optimize approach okay this is brute force all right today I have to go with optimize approach directly no you can start with groups approach so what I'm doing uh actually I am like I'll be making pair of departure time and arrival time and then I'll be sorting my array Vector pair of array okay so I can assume like so what I tell you you understood now yes exactly like in Brute Force approach you are sorting the array I'm sorting that I'll be making a like what I'm doing this yes so I am like arrival of I and uh departure of I'm making pair and sorted correspondingly foreign according to the arrival time okay and let's suppose I have the trained with the platform one and directly uh then I'll be checking so what I am checking just greater uh like 9 10. just greater than this which one is the translator so 940 is the just return so what I can do I can assign to the train to to Platform One and then just greater thing no no I am checking which train arrival time is greater than departure time of previous Trend just previously just last Trend which is reached initially okay so when I'm going like 1200 like I'm coming here 950 is greater than uh departure time of trend two so for this I need one more platform okay I will try to print here so for 1100 I need one more platform because departure time of uh Trend too and print Trace greater than arrival time of train four so I need one platform for that okay and for 1500 like 1200 is less than 1500 so for I can assign so it from one to train five and uh for trains five I can assign uh like platform 2 or platform 3. all right so three will be done so this is my Brute Force approach because I'll be checking every like when I I am at ayath element I'll be checking every train to the right of the element so I'll be checking like I'll be running two loops loops inside the loop this is the O of n Square thanks all right so like if you are already running two Loops then what help did this sorting thing did to you uh no sorting thing what a like what I confirm inside my mind like I I'm taking the train uh which uh reached the first like which arrival time the first okay so for that you use the Sorting thing okay all right like okay let me just share the link you can you know just execute this Brute Force approach as well right just okay I'm telling uh optimize approach as well and simultaneously I'll be writing both of the code okay all right go ahead Okay so for my optimized approach I will be sorting arrival array as well and departure array as well and then uh I'll be taking guys so what I can say uh let me explain [Music] so 910 11 20 11 30 1200 [Music] 1800 and 2000 okay so by this uh I can shortly say that that this departure time is less than all of this and this arrival time is less than this so I will be only considering if my departure time this departure time is greater than this one so what I am doing here uh like this let me write on for you my current like initially my platform should be needed my answer would be one and my current departure time could be 9 10. like at 9 10 uh my station is I can say uh at 9 10 there is a train there is no vacant I can say when I will be reaching 940 so my departure time would be update to 11 20 because so an answer will be not increases because this arrival time is greater than this uh this um this departure time then again I'll be coming here so I can see foreign all right I just want you to try so like maybe after a minute or two I shall give you a little bit of wind but before that I just want you to try because I guess you can reach to the approach your logic is quite good but maybe I like I'm thinking like is it working or not like I'm confused all right okay so till one here is platform required only one so when I am reaching the trend to so the departure time of previous train is greater than the arrival time so I need one more platform so I'll be adding one more platform okay and I'll be updating my departure time to 11 30. so when I am going to train number three and make current Max departure time is so I need to so what I need to I need to track the minimum departure time of of current elements so here the platform is only one there are two platforms I have assigned one departure time is 1120 and one departure time is 11 30. so there are two Platform One departure time is 1150 and one departure time is around 11 13 11 20. so when I reached to platform number five so there is the arrival time is number four so when I will be at 10 number four the both of the platform is not empty so I have to make one more platform okay and and I have to enter departure time of that frame is 19. okay and when I will be reached here so I did not to make another form because here is my lowest platform okay so here will be in platform number assignment okay I got the logic so I can explain the logic again so for this I think I need a priority queue for that so by that I can make sure like I can get my beauty queue which platform has a minimum departure time okay and how is that going to help you okay I'm explaining again so let's suppose I am I assigned let me erase this off okay so I am at platform number one uh so uh and that that is only there is only 110 with that departure so if okay the train having arrival time less than 9 10 that would be not able to reach that platform number one if the if a train having a rival type greater than 9910 I can assign the trend to the platform number one okay so when I am going at train 2 I can check the platform number one have departure time less than arrival time so how what can you do I can assign that for uh train number two Platform One okay and that platform number one uh would be empty at 11 20. so when I will be coming to 10 number three so it arrival time is less than Ln 20. so for that I need one more platform platform number two so for that and the at the time of 412 uh at time of 12 the platform number two would be empty okay and no no no no no we were on the third yeah 11 30. yeah when I am going at platform number four so I am checking platform number one is also not empty and platform number two is not empty so I need to take one more platform pocket and at what time platform 3 would be empty at 12 o'clock and when I am going 15 like 15 o'clock I can check so I can assign any of that so I will be assigning here so how are you doing this checking thing second thing I'm I'm keeping the priority queue I'll be getting so minimum departure time let's suppose I am making the periodic minimum of 3 is 11 20. so if 11 11 20 is uh I can say greater than 1500 so every other element is also going to greater than 1500 okay why can you say that that if 1120 is greater than 1500 then why every element will be greater than 1500 I I am keeping the mean hip not mean if the top of the mean if he's always giving the minimum element all right so let us say if uh the place that where you have written 1200 it could have been 1600 right okay yeah but in that case as well 1120 would be the you know minimum element and 1120 is greater than 1500 so this platform you will have empty but you can't conclude this right that all the elements are greater than 1500. can you can you repeat again let's suppose let's suppose it is 1600 yeah yeah so in that case you can't conclude that if 1120 is less than 1500 that all the elements will be less than 1600. no no what I'm telling now what I'm telling I need only one platform required for the only one what I am telling if let's suppose that's true if 1700 is the top of the my priority queue is greater than 1500 so all the element in the periodic U Q written 1500 that is I'm telling okay all right okay fair so for this I will be assigning platform number one and departure time will be like at the time of 19 and for similarly for this 11 30 is minimum so I'll be assign this so the answer will be uh free for this is there any error error does not seem but uh okay uh like uh are you confident with this approach with this priority you think you think that you really need a priority queue and you are just keeping track of the minimum departure time that we have and the maximum departure time that we have till that point right uh these are three two things that we care about the minimum departure time and the maximum departure time so do you think you will be needing priority queue because I have sorted already yeah priority queue does nothing other than the Sorting I have sorted already so maybe I need not required priority queue but with the help of creative I can solved surely okay so okay let us you have already explained to two approaches so that's quite Fair it is just move wired with that all right so okay I will just check the link maybe you can get the intuition while you are solving so you can yeah [Music] foreign [Music] keyword can you exactly tell me what sorting algorithm is implemented internally internally uh yeah wait uh I think there are two algorithms mutually they work together one is quick shot and another one is there are two algorithms I know one inch quickly I can say and uh one is what one is let me memorize I cannot memorize rate no okay I am telling you in between and I remember guys all right okay I'll just go ahead with the question we will discuss that later so first first time solving with the help of creative then I will be optimizing my the solution all right all right so my current answer will be one and my so there is I'm making priorities Q [Applause] [Music] so while you're taking please so then I'll be going through one two and then what I'll be checking if my current arrival time is greater than or equal to so one also think if arrival time and departure level let's roll it what I am telling you if a station vacant title 10 and simultaneously if a departure time of another trend is 10 so can I assign a trend in that platform if you need a new platform for that okay for that I am checking if my arrival time is greater than me top of the priority queue nothing to do with greater than if less than less than or equal to so I'll be again and surface plus NLP to show what you need to do I need to pop that element because I have to send one more element so I have to PQ dot push here I'm assigning new element so departure I looks pq.com what I'm doing here so if my top of the periodic queue is greater than it means of the no platform arrival time departure time is less than my current arrival time then what I am doing I will be taking one more platform and then I'll be marking his like that particular platform departure time and if if there if there any platform exists that I can assign what I will be doing I'll be popping the current platform departure time and then I'll be assigning new departure time similarly for this yeah yeah so maybe rather than writing that PQ dot push two times maybe you can write that one time you know outside your printers so I think this should work thank you [Music] one thing I have to do I have to remove this periodic view how can I remove this so like how can I remove this [Music] how can I do so I take not to give this I need not to take anything so what I can do I can take one point there so what I'll be doing if my [Music] tomorrow [Music] foreign yes I can hear you can you hear me um I don't know if problem is from my side okay guys am I Audible can I just yeah okay thanks everyone yeah all right I guess we are good now so wait [Music] thanks everyone for the confirmation all right [Music] so what I have done here so what I've done here so I have already sought the departure around arrival array so what I am doing if I'm checking my current departure Trend so I know like my departure La will be sorted in sorted order so I am standing at platform number so if my departure of J is greater than so it does mean key I need one more platform yeah so if my my departure time is uh greater range so I'll be uh not need not to uh required another platform so I can explain from here I'll be taking here example so enraging all this I will be taking so first I am assigning platform number one to my train one okay and this departure time is nine ten so I know here is Twin one so then I will be going at train number two who so if I am going at train number two I can see that departure time of plate like train number one is less than 10 number two so what you have to do I have to assign that form number one to Trend number two and again I have to increase my counter J from 0 to 1. because I cannot compare train number one departure time to other because the last frame that is reaching to platform number one is Trend number two so I can only compare of arrival departure time of train number two only okay increase the count I will be increasing the counter here okay so again and if I am going at Trend number three so I am here uh looking for that departure time of train number two is greater than arrival time of train number three so what I have done I assign one more platform to train number three so and currently I am standing here okay uh again you're just checking for departure time departure time was greater than train number two so why are you checking so initially I have answer equal to 0 and J equal to 0. so what is this there is a tracking the minimal departure time like to what I can say the platform having minimum empty time a platform at that time would be empty okay the minimum departure is keeping track of the minimum departure time that we have ah yeah yeah okay what I can say key at that time at least one at least one platform will will be empty so okay skipping so I'm returning So currently I'm so I am taking already so okay so platform number one is quantity and one is there okay so what I am at turn number two So currently I am uh J equal to zero so I can see uh my departure uh departure time is less than my arrival time so again I will be ascending to and again I have to uh my increases the counter because I have assigned platform number one to platform uh Trend number two so my departure minimum departure time would be 11 20. okay so when I am going here I can see the arrival time is less than my current departure time so I have to make another platform too okay and I need not to increase the J because uh this is already less and I am assigning new platform so my current arrival departure time should not be changed so when I'm going at train number four uh I can see that my current departure time is greater so again I have to make one more platform when I am going to add Trend number five I am seeing my current departure time is less so I need not to increase the counter rather than I have to increase the my JJ J I have to increase what what how why I am increasing J because this arrival this departure time is already taken by this trend so yeah that platform number one would be empty at this time so the minimum departure time of any platform will be 11 30. okay yeah so when I am going at train number six I will be not increasing the answer because my current departure time is already less rather than I am increasing the jth value yes all right okay yeah that seems fair so uh can you just go to the portal you have already submitted this new code right yeah are you yet to do that no no I'm okay submitting again okay yeah yeah great this seems fine okay so now the time complexity for this code is here I'm playing sorting things so the time complexity would be I can say off and login [Music] okay so coming back to the Sorting algorithm so with sorting algorithm for this sort so I know my by manually I can sort the array optimize sorting algorithm is not sort and for this I think one is quickshot and one more algorithm is there they mutually work together but right now I cannot memorize that okay no shows actually there are three sorting algorithms that work together and collectively they are known as intro sort all right so that is actually a combination of quick sort Heap Sort and insertion sort yeah okay okay thank you that is the thing that we have to say all right and the space complexity here you haven't used priorities you okay space complexity would be one yeah so all right uh that was great so yeah um that was okay just a second we have Okay so yeah that was all about uh today's session those two questions that we had now let us come back to the feedback part okay so yeah on the basis of the session how much would you rate yourself I think it should be nine but in last question I fumble a little bit that's why it would be nice for me no actually it was a tent but just because in the last test case uh you just kind of took some time but uh that is not really a matter of concern so yet again it is a 10 but just let us keep it 9.5 right because uh you know just uh you do some things because you were not knowing that what is the Sorting algorithm behind the keyword see we use sort so frequently like that is the most common thing that we use all the questions that we solved so you know we must be aware of the fact that what is actually running behind the screen okay how it is getting implemented so for the first question it was great like you know you just come to the optimized approach from The Brute Force approach very directly so 10 or 10 for that and for the next question yet it looks it took you some time but you were able to get to the approach like logic was very much cleared in your mind you were very much you know aware of what you are doing what is the demand of the question right uh you were very much aware with that so yeah 10 on 10 for the next question as well 0.5 deducted because you didn't know what is the Sorting algorithm all right so that was a great session you performed really great all right it was a really great interacting with you and your enthusiasm your communication skills your confidence your coding skills everything is 10 on 10 okay so keep up the good work and yeah anything from your side so nothing much I want to ask just I am want to ask so in terms of my communication skill how much you will rate myself in communication skill like how I am communicating I am able to explain the all the things properly or I am missing something no you were not missing something okay see there was one point a value where solving a question you said that okay first of all I will just solve in my mind and then I will be explaining to you so that one thing was that but that is not an issue your communication skills are good you were able to explain what you are doing right you explain all the test cases right for all the three approaches in the uh second question you did three approaches and for all the three approaches you explain using the test cases so your communication skills are pretty well there is no any problem on that part okay thank you thank you so much all right yeah and here we have people as well who are yeah who are complimenting you that you know you were extremely good and you know you performed really very well so yeah that was very impressive I need to perform well because I'm doing competitive program from 1.5 years if I am not able to solve this is anything else from your side no I think it's enough yeah that's it yeah that's nice okay so uh keep on practicing keep up the hard work and we wish you all the best thank you for joining us thank you thank you so much [Music] thank you all right guys so uh we had Suraj with us and we as all of us see he performed really very well he was able to solve all the questions and he did all of it in a very limited time frame his communication skills were good his problem solving skills were good and uh his logic part was good as well he was able to you know get to the most optimized approach so that was very good thing so all in all it was a very good session very impressive session so uh any feedback anything from your side do let us know in the chat section and we would love to see you all as well in our upcoming sessions so do not forget to fill up the Google Doc the link has been provided in the description section so do fill out that form and we will be having you in our next interview session and yeah that's all for today anything any feedback any suggestions you all can add that in the comment section and we would be seeing it and thanks for all the compliments all right guys so that's it for today see you all very soon till then keep up the hard work bye everyone