Live Mock DSA | GeeksforGeeks

Key Takeaways

hello everyone welcome to geeks4geeks this is our new session of live mob dsa interview myself abnorsti i am a dsm mentor at geeksforgeeks and today we have lisa with us hello how are you i'm sir i'm fine okay so are you ready for the interview yes sir okay so please tell something about your projects and stuff if you are doing hello uh i am rishabh i'm from and i have some interest in machine learning so almost all the projects that i have done are quite related to machine learning and the uh the one project that i want to mention is emoji file the main idea behind that project is um we are given any uh picture and we uh we are detecting our face in it and the detected phase is then uh passed as an input to the neural network and the neural network then predict the emotions uh on that picture the main idea to implement this project is to give recommendation uh according to the reaction of the humans recommendation of emojis okay i got it got it great yes fine so yeah uh you saw i have shared you uh google doc with you okay so can you please open and share it save the screen you can just turn off your all the notifications for privacy purchases okay is it visible yeah okay fine so i'm just writing here uh just telling me that it is it is visible yes yes yes okay fine uh okay sir so we will start with the problem okay and uh so let's first start with the basic problem statement that what the problem is all about so problem is basically of offer you are provided with the array okay and the array has n numbers so i will just if i would write it so the array has and numbers okay okay so basically for example the array a r r s is like from one to and let's see it does not like that it is always from one to n only it can be any random inverse in that particular okay got it but the thing is that the array basically this array basically denotes the version of a product so there are basically any products given to you okay so there are n products and each element of the array basically tells us the version of that product but what's the version of the product fine so if the version of that product is for a non-negative if it is non-negative means greater than equal to zero that means that product is a good version that is a good version getting it okay and if if it is less than zero that means the project is a bad version okay cool cool so i'm just uh yes listen yeah fine so this is what you have now what you have to find is that after every bad version all the following versions are bad only for example the first version there there are five version let's see there are five versions or five projects okay so let's say that the first product is something like two its version is two so the second product will be of four and obviously obviously if the first product has a version two the next will be a greater version only it will be a greater version obviously so it is something like that and the next the next will be something like six and then the the fourth version is bad version means it is a negative basically minus if there is a minus one that means it is a bad version and all the all the versions of all the products after that bad version product are always bad only means after this minus one all the products are just minus let's say if there are seven products also in that case also the other two are minus one okay uh so the negative versions were only minus one fixed value with the minus one yeah it is it is always minus okay okay cut it so basically we have to find the first product which has the bad version okay for example in this case you can see that the answer is basically four because the fourth product is the first project having a bad version uh after that bad version all the products have bad words okay so the uh can i get the solution yeah yeah sure okay so the first thing that i can see we can linearly traverse and uh so we can linearly traverse and find the first minus one uh which which will appear in the array and uh we can get that as our answer but i can see here that oh the time complexity of this solution uh will be we go up and uh and that is i think bad uh for this question uh so i think i can do it in a login by binary searching it uh in uh in uh in time complexity we go off login and space complexity portfolio of one i think so okay yes so okay can you please write you can please just explain me the logic how we can do that okay okay okay so uh what i will do is uh i will take a take two variables low uh and lo will have the minimum value minimum index number in this array which will be uh obviously zero and uh high which will be uh the last index of this array and minus one and what we what i will be doing is uh i will binary search on this array to find the first first occurrence of the minus one so this is payment is uh is equal to minus one is greater than or equal to zero and what i will do is i will move uh forward so that midpoint is taking the average of that low and high means what is the logic fault at low and taking the average of low and high uh the logic is this that whenever i have an array and i want to see uh that what is the first occurrence first occurrence of minus one so i will see in the mid one and if i find the value uh version which is good then uh i i can see i i can i can say for sure that uh the first occurrence will be uh in the right half okay for sure so i will move to the right part of the array and the right part of that right part of the midpoint right yes the mid pointer divides there in the left half and the right half so i will move to the right half and if i find the minus one uh i can say uh i can obviously say that all the right mem all the right half on the right half members are the bad version only so we also i only have to see on the left half is this a last minus one or not so i will go to the left half and see whether it is the first first occurrence or not are you getting right okay yeah you can continue the code and i can take the answer as minus one and guys [Music] because the indexing that you have set is one based so i think that will work okay got it got it or i have to explain it yeah so it means by taking that low is equal to mid plus one what you are trying to do uh i am moving to the right half of the uh array uh the uh since the uh mid element is a good version i can uh i can say for sure the bad version lies only on the right half of the array so i i am going in the right half of the array and again binary searching on that right half so this low and highs are basically the start and end pointer of your sub array which you are considering yes yes yes yes okay okay got it got it fine and the answer is basically you made yes yes the answer will be made uh because the bad version will come in the else part and the last time when the answer will uh will the last time when the answer will be updated that must be the uh the first first occurrence of the bad version yes okay means it means basically you are storing the mid pointer whenever you are getting a negative value means okay so for more preference we can do like that because the first version will always that has the minimum index out of all the other bad versions the bad version which is the first bad version will have the minimum index among all the other bad words so we can take the minimum of a minute yeah yes okay fine fine okay fine so what is the time complexity and space complexity for this solution so the time complexity will be uh big o of log n because every time uh when when i have a full array i am searching in the mid and uh when i get the mid and uh i take a decision whether i have to move to the left or the right part and when i move to the left part i discard the right part totally so uh so the so the next in the next iteration my next sub array will be the left part only so uh this is why the complexity will uh will be log n i don't know whether i okay okay yeah then the space will be big o of one because i didn't use any space okay uh rather than other than uh variables it is constant okay okay it's fine yeah okay fine fine yourself that is what i was thinking of okay that's great so now let's move towards the next problem okay uh lisa so the next problem is that uh let's consider that there is a railway system okay and in that relay session there there are basically entrance has to be arrive and depart from that given where this is moving and for each and trains you are given with the arrival time and the departure time of the dreams okay so you have to tell that what is the minimum number of tracks or platforms required in that particular investigation getting a for example at the given time which is 5 pm let's see at a given time 5 pm there should be three trains there will be three things here let's say at 4 pm there will be i will just ask that what is the minimum number of platforms required so that no train should keep waiting they all should be at their given platform so there should be at least five platforms so that they can manage five trains at 4pm time getting it okay okay so here you have given me uh 5 p.m and what is this three no no no you will be with just a minute you will be provided with the departure and arrival time of day for example there are three trains okay uh there are three trains so means the value of n is three okay fine great now let's say the for for the first range the arrival time is given with two arrays which is the arrival array and a departure right okay so that and i will arrange something like something like this okay so if you will just you can see that for the first train its arrival time is two and its the pilot time is three for a second train its arrival time is four and departure time is seven so the third rate its arrival time is one and the departure time is four fine yes you will see that so the plane number one will be between two to three in the in that particular railway station the train numbers two will be between four to seven and ten number three will be between one to four so i hope that now you can calculate the answer for this given this case what should be the answer okay so the answer uh will be uh i can use one platform and um train four to seven and the second platform or one to four because uh i can see that the which is the third frame and because uh the third train is overlapping uh with the first first train yes first train and uh one point with the second train so uh we cannot use the first platform for the for that so the third train have to uh arrange to the another platform so uh i think the answer will be two here fine yeah this is the answer so how can we solve this okay what i can see from the problem is uh the trains which which have the overlapping range of the arrival and the depart departure time have to be arranged you know on a different platforms okay okay okay okay so what can i say is uh i can create a timeline okay uh like one two three four five six seven like this this is the timeline okay okay and uh i will mark that whether at this timeline or train is arriving or departing okay so uh i can see uh the first train is arriving at um at two uh two so uh here first and uh and it is departing at three and the second train is arriving at four and uh departing at seven and the third train is what can i see is uh at any at any moment of time the maximum number of trains that are overlapping is that will be the answer of this question fine at any moment so basically you are taking from one to seven means yes yes yes uh yes you can continue you can continue you can extend your file but what i will do is i will um increment ah yes i will increment the i will take a variable and uh whenever a train is arriving at at that time at particular time i will uh increment the value of that uh variable and uh whenever it is whenever any train is departing i will decrease the value of that variable so by this i and i will take a global max variable which will uh which will save the maximum value of that pointer at any moment of time yes can you please write in that logic in the given test case for me which you are thinking you'll get okay yeah so what well you are saying you are saying that the time when the train is arriving then you are increasing the value of that variable yes uh let's say the variable name is count okay and at uh okay what we can see is at uh timeline one the the train number three is arriving okay so uh initially the value of the count is zero so uh at time line one the uh count count will become one okay and when i will go to the timeline two the uh the train number one is arriving okay so the account variable will again increment its value to the two and at the three the uh train number one is departing okay so i will um decrement the value to the one decrement the value of the count to the one and uh at four one is arriving and second train is arriving and the third rain is uh sorry huh third train is departing so the my value remains same at the one and uh at five and six nothing is happening so again one one and at seven it again becomes 0 yes so uh what i will be doing is i will take a max variable which will uh which will find the maximum value of the count at any but at any at all the time whenever will be the count it will be the max and that max will come out to be two because at we can see at time uh at time line at time is equal to two two trains are overlapping which are three and one are you understanding your logic yeah yeah i am getting it i am getting it so uh what you have implemented is that at the departure time the train is not at the station yes and no oh uh do i have to take that at the next point no it's okay it's okay i think that it's okay basically the problem was that only but yeah it's okay means uh let's assume that already partial time it is not an update fine okay then also the answer will be two only fine okay yes uh so basically but how will you will just uh figure out that at a particular time a train is departing or arriving which data section will use which algorithm you will use to check that thing or for each time you will every time you will i trade through the given values that is what we have yes i i think i will hydrate into the value because i think that time of the trains are between 0 0 zero two uh uh 23 59 i think yeah so this is basically something like that it ranges from uh zero to twenty four hundred twenty space complexity will be a big of 23 2400 but because it is constant i can say that it is bigger one i think uh yeah you can say but the thing is n is not constant the number of trains are not constant okay okay and can we up to 10 to the power 5 or maybe 10 to power 8 or 10 okay okay so uh big row of n will basically it will be n into something now and into something means what will be your what will be your brains all the time and i'm not getting the range of the timeline you are getting now what is the range of the timeline you are assuming can you please confirm that to me uh from uh 0 to 2400 yes okay and for each time of the timeline you are i trading through that train yes no no no no no i am what i am doing is i will iterate over the all the end okay what i will take is the array of 2400 okay and uh what i will do is i will take 10 trains okay and i will iterate over them one by one and uh from uh the first train will be arriving at let's say one two two okay so i will increment initially all the way values of this array will be zero okay and uh since it is arriving at one i what i will do is array 1 with plus plus and array 2 minus minus okay and but i will calculate the prefix sum of it and that will give me the count i think yeah that is the world prefix some i was just searching for it means you have to find a pre because that that is what you not mentioned in that case now when you have a guide and yeah yes yes okay so we can find a prefix sum and so can you please again drive in that same test case using that prefix and logic okay okay so uh i will copy the test cases here so um initially my array all the array of size 2400 will be zero initially okay and uh what i will do is i will enter it over all the trains and on the ith highest train i what i will do is i have my stream i i will be uh incrementing the value of uh that particular arrival time okay uh that will be uh b of i dot first plus plus okay let's say uh it is in a pair and v i dot first is time and vi dot second is the departure and uh array pi dot second okay and then uh for all all the uh all the trains i will do this and i will calculate the prefix sum and the max value at any i any timeline at any point of that timeline uh will be the maximum number of platforms that i have to use because uh that value will be denoting the number of trains that are overlapping that overlapping with the timeline of each other yes that is myself you're not now i'm getting it so can you please write a pseudo code for me yes okay okay so you can you can just take this output in output you will give it the value n and you will given with a vector of pairs of size n okay okay okay so the i will be given a vector let's say it is a function and and that is the size okay uh so is foreign what i will do is i will be incrementing the value at the arrival time first plus and minus minus and first i have to calculate the prefix sum of that array i is equal to one less than four just this is scrolling down yeah okay yeah [Music] counter yes so that will be my solution oh great great yeah okay so for this solution what will be the time complexity in space complexity so the space complexity will be if i do not consider the vector that you have given me so the space complexity will be big off and if i am considering this okay and the time complexity will be bigger than and space complexity fine i've got it okay so now on the next problem are you ready yes sir okay uh also listen please increase the font size a little bit okay font size uh okay okay six now it's okay i think yeah so uh what is the problem uh we have is the uh that let's say that we are doing with the array again we are what you have to do is that you have to find a next greater element okay of a given number in that area for example the arrays three one four two that's fine okay so you can see that uh next relevant means the element which is just right to it okay this is right right to it okay that is what you have to find and for example if you i would just write the answer for this given case so it will be for three the next element will be four okay and you have to basically output the index of that number now index of four is basically two you have to okay okay okay for one the next letter is again four so we do four again for four there's no negative element so it is minus 1 okay and for 2 also there is no negative element ok ok getting it ok for each number of the array you have to find a next greater element okay okay so uh the first thing that i can say about this is i can uh for uh like for three i can traverse from 2 from 2 to the n minus 1 element and find the first element which is greater than 3 and i will mark it mark the index of that as the right pointer write element that is greater than three yes it means you can identity but can you please repeat can you please repeat yes uh what i'm saying is uh for every element uh i will uh go from for iath element okay i will go from i plus 1 to n minus 1 okay and i will uh find the first element in this range which is greater than the uh greater than greater than my ai [Music] okay fine so what will be the expected time complexity for that the time complex the expected time complexity for that solution will be big o of n square and the space complexity will be big o of n okay okay so can you do in a more effective efficient way more effectively uh yes i can uh i think i can use stack uh to find the uh ngr okay uh what i will do is um i will traverse from the last index and i will be uh taking the i will be taking the elements in the increasing order like uh like two for two uh i will mark the next greatest element as a minus one because uh there is no element uh to the right of the two okay and i will uh push uh two to the stack and for four i will uh i will be i will push uh i will pop the elements from the stack until i get the element which is uh [Music] which is greater than four okay so uh so so i will pop out two from the uh two from the stack and uh if the stack size is uh empty is uh if the stack size is zero okay uh then uh then again i will mention uh minus one as the answer because there is uh in that case there will be no element to the right which is greater than this particular element okay and uh on the uh then on the end of my loop i will push the uh that element to the stack again okay so now in in my stack uh element four is there and then i will move on to the one and i will see that the uh top element of this of that stack is four which is greater than 1 okay so i will mark the index of this 4 as uh as the answer for the one and again i will push the 1 to the stack why i am pushing the 1 because i there is a possibility that i can get i can get element which is lesser than one on the left part of the array uh in the stack and the top element will be the one which is smaller than three so i will pop the uh stack pop the pop this element from the stack and uh then i will see that the top element of the stack is four which is uh greater than three so then i will mark the index of this uh four element as the uh right and the right uh element which is greater than three so basically we have to just i trade through the array and then we have to post the numbers in that stack until you get a number which is greater than a top element of the stack that is what you are trying to say okay okay so can you please drive on that thing for me create a stack and then just do that yeah then maybe i will ask you oh sorry uh just none i have to start from the last this is i minus minus okay minus what is so i will now while [Music] i is uh less than or equal to my current element have to take is uh if the stack is currently empty then uh there is no element which is greater than that in that case i have to mark the answer as -1 okay else have to mark the answer as the top element of that help as a top element as answer do you want to change anything or you want to explain anything all the while using the while loop by using the a finals so uh i am using the while loop uh for the uh for for those elements which are uh actually less than the uh which are uh continuously less than um less than myself my current element okay fine uh fine and then i will reach to that particular uh element in the stack which is strictly greater than um me my current element means the top element of the stack should be greater than the current element yes yes okay for that purpose i have used this while loop fine yes and then if stack is empty then the answer is and if the stack is empty then uh that then that is saying uh that this is true then uh that is saying that uh there is no element on the right of that array which is greater than this current element in that case i have to mark my answer as -1 can you please run this can you please run this code for our test case which i have just given you just let me i'm writing that okay and the side of this program only don't explode let's take the test cases 3 2 4 ok ok so um can i use pencil in this something like that to store the stack let's say uh this is my stack okay it is currently empty okay uh so uh at the n minus one uh iteration the stack will be empty okay so this while loop will uh not function because it will break uh st.mt is equal to is equal to true so uh this condition is not fulfilling so this value will break and uh since the stack is empty so the answer for my fifth uh for my nth uh n minus one element will be minus one okay and what i am what am i doing is uh i am pushing that uh stack element in the stack index however i am pushing that current index to the uh stack okay so you can say that uh i'm pushing the fifth element uh to the stack and then i'm going to the one so currently in this stack what do we have uh five uh we have um you know four four index final index yes um and then i'm going to the n minus 2x which is uh which is a one one one element okay and then i am seeing whether this uh while loop uh will run or not since this condition is uh false again stack is not uh stack uh has some element but the top element on this array a st dot top which is 5 since the stop element is 4 which will be putting which i will put the value in it and a4 is uh [Music] a4 is actually greater than my current element which is 1. okay so the so this while loop will not run again and since the uh at this time the stack is not empty so the answer for this this iteration will be st top which will be the fourth index okay okay all right then i will then i will uh push this index to my stack uh because uh there can be a element to my left which is less than uh me less than this current element in that case i have to uh i have to update my uh answer to this one not to that file okay in future uh then i will uh traverse to uh four okay then uh for four since the uh since the top element which is uh in this stack uh we will be having four and three then now okay uh since the uh a3 is less than four uh just the top element on this stack will be uh will pop out okay so now i have four now a4 is uh actually greater than my current element which is four four is a five okay so five is uh actually greater than uh four so my while loop will break and uh since the stack is again not empty so uh this else uh will run and uh my answer will be uh st.top which will be four again uh so my answer will be for a minus for fourth quarter next okay and four for one and again four again four four four okay and then i will push uh push the index of four to my stack again which will be 3 which will be 2 okay then i will come to 2 my element 2 which is at an index 1 and as i can see the top element uh which is uh st top is will be replaced by 2 and since a2 is greater than my current element which is 2 so 4 is greater than 2 so this value will not run and uh my my stack is not empty so again this else will uh function and my answer will be st which will be two this time okay and then again i will push one to the stack so here i will be having one and then i will go to three and for three uh a one is uh less than three so i will pop it a four is actually greater than 3 so my value will break at this stag condition and since the stack is not empty so my answer for this particular ith uh in ix index will be st.top which will be two yes yes okay okay got it yeah yeah your answer is right great so means you are using so in in that particular root that the for loop you are just iterating from back side of the array okay and i'm just figuring out what you are doing okay you have dried in it but yeah then you are using a while loop and in that while loop if your stack is not empty and the top element of the stack is less than the current element right now in that case you are popping it fine okay this is this is good uh after that if stack is empty in that case you are making it that yeah we don't have any greater element in the right screen yes okay and uh else you are just means the top element of the stack is the next element all that given okay so and in that stack you are basically pushing the index of that current value and at the last line okay so yeah the the the problem is uh clear and your logic is also clear to me can you can you please transform this code this logic for the next smaller element uh next smaller argument yes uh i just have to change the sign and then my answer will be for the next uh smaller element as and now at this time i will be popping all the continuous element let's say i am at the ith index and then i will be popping all the continuous elements which are which are greater or equal than my current element and that that case my stack my stack will stop either at the either because the stack is empty or because the top element on that uh at the end this time on this stack is uh is having a smaller element than my current element yes got recorded and if we have to find the last greater element uh last crater element means the element which is at the left side basically not the right side okay okay uh to the left side uh means uh smaller element to the left yeah smaller or greater than anything to the left then i have to uh just uh traverse from uh from the start just got it got it ready this is how we have just uh observed that using a same algorithm we are basically solving four different types of yeah yes great greatest upgrade that is what i was just thinking to just ask you that this is how you can just use that code to solve the three or four different problems uh even what can be the uh time complexity and space complexity so the space complexity uh will be big big o of n because in the worst case uh i will be pushing all the elements in the stack and uh my time complexity uh will be actual time complexity will be we go of uh 2 into man i will be traversing my array uh two times in the worst case one for this for loop and ah one in this while loop so i will be traversing into two into man but uh in bigger terms i can say we go fine so your time complexity is often for this algorithm yes and space is also too cool fine fine great great so that is what i was also also expecting realism that is uh today for this interview and yeah we have discussed some three problems and you cannot unseal your screen it's okay okay yes yeah so now the time for the feedback session so yeah all the three problems which we have discussed uh uh you you have basically told me the most efficient to me which i was also expecting for example in the first problem it was based on binary search and you have got it in the first attempt the second problem was uh quite uh i was thinking that you will maybe you will be confused about that and in the first time that you will just i didn't really forget about that prefix something in the first iron you have made yeah but yeah at the last year made it to a right observation that how we have to solve it and basically there are multiple logics present in that problem that like first you have to just travels and for arrival time you have to increase and for departure time you have to decrease that first observation you have to meet the second observation and this is the first observation was to take a number line timeline yes the second observation was how we have to increase for arrival time however decrease for departure time the third observation was to prefix some logic that is i think the most difficult one because if you will not take the quickest one you're going to traverse strongly arrival time to departure time and that will take off and square or pull off and something like that yes yeah that that was a great observation made by you and then obviously that's a fine in the max of that value that array that was also a great thing and the third the third problem was a classic problem from stack and you have just recorded that how we can solve it and all the other uh the other problems are just similar to that for example the next later next is smaller last maybe last year they are just basically something of the same family problems so yeah you have got it uh also the way you have explained the things uh the way you are just doing it it is quite good how you are just writing the pseudo code and you are just taking the uh the variables that was good that you have taken low high mid and that is something off just finally such things and uh the thing how you have just implemented that prefix some array and that is a good thing what what you have done and that that is a positive thing for today uh just a small free feedback just just when you are just thinking of a problem okay and while thinking maybe sometimes you take some break but in your case that was not a very big break but yeah when you are thinking of as a problem uh just try to explain each and every point to the interview means each and every point okay if you are maybe maybe if you are thinking the wrong wrong approach maybe you are thinking something else but you have to just implement this thing and before doing the drawing dry run always try to explain your logic to the interview before doing any dialogue before writing a program just for example in the last one you just got to the program instead the program maybe you have first down the dryer and you use a stack and then write the program so it is easy for us to uh you know understand yeah but but uh overall that was a great and the video explainer the way you write the code it was good okay so it's up so how was which was your good question for today was your favorite one and how was your experience uh i think uh my favorite one was the second one uh the train problem uh overlapping problem and uh that the interview was great i loved it okay great it's up great all the best and okay guys so okay this up okay thank you thank you for that okay guys so this is all for for this interview if you also wanted to be to be the part of this life mock dsa interviews you can fill the form given in description and you can also get a chance to be the part of these live mock dsc interviews okay guys thank you for joining thank you you