Live Mock DSA

hi and welcome to geeksforgives today we will be having a live mock interview with himanshu agarwal where i would be interviewing him but it seems like we have eventually audible okay okay so can someone tell me if i am audible or he is not or he is not ever able to listen just check first is [Music] so let's start by the day so we will be starting off where i will be interviewing you this would be a dslr okay so can we have a bit about yourself yeah sure uh so talking about myself uh myself in manchester broward i am currently passing my b tech from government college of engineering and currently i am doing internship with gravity as a software developer intel and uh the main domain that i am working with is data engineering and talking about programming languages that i know uh cc java and uh talking about web development uh the i'm working in client watch front-end web development and i've made a couple of my small projects and the projects also into that domain and one of our projects is uh chrome extension it's a coding body uh and it shows programming languages it contains that are happening on platforms and um along with that uh talking about my achievements uh i have been into acme cpc results and uh i love deleting books so that's how i follow okay what is your favorite book though uh yes uh the atomic habits are it's my gem is clear yeah i ended and i loved it okay so that was great by the way your home extension i i have also used it once that's that's a great thing yeah so let's start with the easy question okay yeah sure so so by the way the flow of the interview would be like this but whenever you want hints you can just ask me him and i would be helping you throughout the interview okay yeah so all the best for you thank you all let's start okay so can you just have a editor or something you can just show your screen now okay uh online editor offline yeah sure so so now your question is you can write it in the form of comments okay the question okay okay okay okay okay so you would be given a bag okay that would be having n items okay and each bag each item in that bag will have a weight and a value associated with okay you would be given an arrow both of sizer w and run okay w would be telling you the weight of each item and the value will tell you the value associated with the height okay i hope i am clear to this point uh just uh can you just repeat the second sentence yeah see i'm telling you we would you would be given a bag and you would be given you would be given n items and each item would have a weight and a value associated with it okay you don't need you can just write the summary of it no you know okay now moving forward you would be given the capacity of that particular event and you can start filling up that in such a way that it would have the maximum value at the end okay uh so just to summarize uh there is a bag and i need i also have n items and uh each item has associated with a value and a weight and i need to fill that back so in such a way that uh there are maximum value of that element uh should be there in the in that type yeah absolutely is that correct but there is yes there is one more condition in this you can use a particular item multiple number of times okay multiple number multiple number of times means if i put one item into that back then i'll also i have option to pick that element uh again into that bank yeah yeah absolutely am i clear with this question yes yes yes so uh for the input part uh uh what uh items okay suppose n is equals to two suppose enhance where n number of items was two and the weight capacity of the bag is three okay okay now let's talk about the value associated the value would be one and one okay okay now the weight associated are two and one okay uh two and one okay now what you can do in this is you can pick up the first item thrice okay you can pick up the first item okay not sorry you can pick the second item twice and then it would be having a weight three and the value associated would be three so the maxi this is the maximum value that you would be able to achieve yes okay here here the maximum uh value uh that i can associate uh is that uh it will be three yes yeah by using the second item yes second item three times so the weight will be three and the value will be three yeah okay so uh just uh just summarize um i am having a bag which can contains a weight till w equal to three and i have items and items basically two items and both items have value and weight associated to them and first item has value one and with weight two second item value one and with okay okay so um so i will um as a as i can see uh here the there are many possible combinations means uh if uh if i can uh choose the sec two-weight element and one weight element so there is a possibility and i can choose two element only so that uh i don't choose one bit element and so the there can be many possibilities so uh talking about the approach that i will be using to solve this uh uh i'm currently thinking of a recursive approach because we have to develop a lot of possibilities here okay so now how would you take hold of all the possibilities uh yes so uh talking about possibilities uh uh i'm i will uh iterate uh through um every element uh and i will check once uh i will uh just i have two options for that element uh to pick that element or not to pick that element so uh to carry that element into my bag or not so i will uh recursively call two times for that particular element and um i will uh first uh if i if i add that element into back into my bag i will also add my uh add that value associated to that element and then when i will not pick for that element i will subtract that a value which i added before so uh this is my approach currently i'm thinking of okay can you just start implementing it and don't take the inputs and all the weight array and the value vary and suppose they are all given in the global space okay uh okay okay global space uh so my output will be integer which will give me the maximum value that i can i can get from that picking that element so uh the question in the function and along with that um all the all the inputs are in global space so i don't need to take an input and uh just to summarize uh there will be a uh there will be a value array and uh just just so can you just yeah do that do that i think it would be in full screen or something oh yes no starting okay so um so there will be a value array and also there will be um a weight array for every element and there will be two variables uh and which will show me uh total number of uh total number of elements and w is the maximum capacity that is uh that i can find so uh i will just uh solve because this is like okay uh let me just close the door itself and i will just return from here the answer and i will recursively call the solve the function and and it will give me output see you can just skip this val and the weight thing why because that is already given in the global space you can directly access it from there only okay okay sure sure so uh so let me see one time okay so and yeah i'm not we met again yes no nothing nothing okay okay so um i will just check if uh is that my uh current uh weight is equal to zero or not because if the weight of that is zero then i can put any elements into that and uh along with that uh also if if the if i have no elements to put into the back so i will just uh that is return i will just return here i will just um call so whenever i have no elements or to put into that oh yes so in that case uh in this case i will just return zero because i don't have any elements to put and so the current maximum will be the maximum and and uh talking about the first peak big part uh so in this case uh i will um i will solve recursively uh for uh when i will be picking that element if i have to check that can i can i uh consider that current uh current element into my network or not so uh so for this uh for this uh my weight uh total weight will be greater than or equal to my uh weight of current element so beta of i should be greater than three yes keep going then only i can put my that element into my bag and i will iterate uh to the next element and my weight will reduce to um weight will reduce to total weight minus weight of the current element so um and this is this will be the uh my big case and for the non big case uh uh non pk so i will uh just uh on i will just do uh all recursively for the next element and and i don't need i don't i will not uh consider the current element because i i might get another best possibility afterwards so i will not also update my total weight and uh whatever the um i get i will get uh some uh i will get some value from fake side and some value from non big selected so i will choose one of them which has which will give me the uh which will be the which will give me the best uh possible value so i will just uh return the maximum of peak and non-pick will wait and then uh when my base case is uh when w it will be zero or i will be one uh i will be and means the last element of that area so i will just return zero um and uh do i need down here um the the pattern which uh are aligning that yes so the base and i will first get that the current element can i pick that element if yes then i will show the peak and find the next maximum possible value from the uh i plus one elements and if i'm not able uh if i'm not able to pick i have only one option that i should not take so can you please read the problem statement that is given this again and then again check your solution i got my problem uh that there there can be duplicates also means a duplicate so i can again take that current element uh duplicate is possible uh so for this for this then when i pick the current element um if if i pick the current element uh i can again pick that current element so when when i am doing the big part uh i don't need to go to the next part because i i might found again the best option from the current element only so uh i can do here only plus uh only i and for non thicker if if i can't pick that element then i need to go on to the next element so here the i plus one will be there so so basically just explaining the audience too suppose i pick the element so i have a probability of taking it again but when i'm not picking it now i won't be picking it that is the main agenda so now can you can you optimize this so what will be what would be the time complexity of this study can you tell me uh yes currently as i am moving towards all the possibilities that i can pick and not take so for every element i have two possibilities that i can pick or not take so uh it will obviously go to the total bar and because i have two two options for all the elements and it will two cross two cross two and it will two to four and then complexity and space complexity uh will be one means uh if you ignore the recursive uh stack of stack size uh yeah talking about optimization um what the work i am doing repeatedly here is uh i'm going to uh i'm going to every element and checking that can i pick that element and can i not pick that element and again when i go to the next element i am checking that um is that can i pick that element and not pick the other element so okay so just before moving forward can you do a drive for the sample test case yeah sure so the sample space is here and i will just do try and once again so yes so uh now currently the value of n is 2 and weight is 3 and value is 1 1 and weight is 2 so um the my current uh uh the next function will call a solid recursively function and it will first pass zero uh as the ith index uh first index so zero will be the percentage and total weight will be w and uh and it will check first uh that uh are they r is w is equal to zero or i equal to one which is not uh this case so it will just go to this part and uh it will check for that the uh my current which is to uh is it uh is it um is it less than or equal to uh the current uh size of my bag so as we can see uh we can pick this because w is three and yes yeah so so if we have the capacity to accommodate okay if we have the capacity to accommodate what are we returning in that case let me just say your solution yes also what is the return path return is the max of pick and nontake because see just read the problem statement do solve do the dry land for just one element itself just one moment okay okay and see your solution will go in the right direction or it won't will it give the desired value or it will just save yes yes so our value is currently one and the weight is three uh so three is greater than or equal to yeah it is perfect and so it will be uh the whatever the function will do that it will again call for uh the current element and with the with the weight uh as as much i need to here and do the current weight uh w so my next total weight will be 1 so now when i uh when i go here again i see that i can't uh the current weight is true and now the blue will be w will be open here so um i kind of found it so i will go to next non-peak and i will check with i plus one which will return zero so in this case uh both are zero uh both are zero so i need to first of all here take at 0 because in this case it will show us that it is not defined so uh i will just initiate this uh 0 um and um i yeah sure so uh talking about the second one um when i will here so the weight is three and the current weight is two so i will just um do the peak suppose yes there is only one one element where the value is four and the capacitor is also four and the capacity is also 4 and the weight of the element is also 4. now tell me the output in terms of in terms of your solution weight is 4 value is also 4 and capacitor is also called weight capacity value everything is 4 now tell me the solution of this according to so as the current element is only one and i'm going for zero right um when i will go here the base case it will not do the big part is zero and now the big five uh big fighter will be solid casually with current element which is 0 and total weight will be 4 minus 2 0 so um it will again call for one um your 26th line okay 26th line is it correct you are going recursively but are you really checking all the possible sub problems and then returning something out of it just think about it yeah so when i will what is the return party what is the report just tell me that uh return part uh it will be uh because i'm uh giving from uh i'm getting some response on text side and some pipe from non peak side so i should return uh addition of both the parts okay so as 26 so as 26 minutes is already consumed so let's go a little bit fast so see so basically keep the solution and open a new tab okay keep the solution open a new tab i would explain yeah okay yeah you can open it in the different type diagonally that's absolutely fine notepad now no this is fine just open that link only just keep that solution i would explain why you are going wrong at the end yeah this means that that's absolutely fine yeah thanks a lot okay now now i'm telling you the question okay try to see try to listen very carefully okay yeah well just listen very carefully you are given an array which would denote the time okay an array which will denote the time now the timings are the time taken by the ith bus to complete one train okay suppose there are suppose there are three bus okay it's reverse and the time taken to complete the trip of the first bus is suppose one two and three suppose yes okay now what is given is you would now you would need to complete so you would be given so suppose there is there is one bus bus one there is two and bus three and you would be provided with the number of trips that you need to do okay uh so first person suppose he takes one minute to take out water from the well and supply it to his home the next person takes takes two minutes to take water from the well and supply to the home the third person takes three minutes to take water from the well and supply it to the home okay am i fine with this yeah yeah okay now tell me now you will be given that yes i want this many jars or this many number of water to be taken suppose every person suppose the first person can bring one jar of water in one minute next person in two minutes same goes for three hours okay okay now i would be telling you that yes this is the number of jars i want to fill with waters okay okay and you need to tell me what is the minimum time required to do that now there is one more thing that needs to be understood okay the thing that needs to be understood is the first each person can go parallel suppose the first person is suppose the first person is going in one minute and the next person is going in two minutes so in the time frame of two minutes the first person would go and come the next person would go and come till the next person is coming and going as the speed of first person is 2x of the second person then he would be able to bring two jars up here so am i clear with this thing yeah means uh all the uh all the uh let's do with the bus says yeah they are disconnected no one is dependent on each other okay so uh okay uh and what is my end goal um so i have to minimize the time many months the time required to bring the number of charts that is desired okay so i am having more target so suppose target is equal to 5 suppose target is equals to 5 yeah okay target is to five so in the time one after time one after the first hour the first person would be able to complete one trip so one jar is complete one jar is fed up then at the second hour the second person would also be able to bring one jar so the first person is bringing two jars in time frame of two hours and the second person is able to bring only one jar so till now we have three jars filled up at the end of the second hour okay yes now at the third hour we can see that the last person is also able to bring the number of charts so now we have the first person bringing three jobs three jars by now the next person bringing one jar by now and the third person bringing one jar by one so that is basically five now there is one more thing that needs to be understood suppose i want five jobs okay suppose i want five jars of water it doesn't mean that i can't exceed it okay okay i can also have six dollars or eight jars yeah this is the threshold point you can cross that okay you can cross that button okay am i clear with this yeah sure so yes um so the uh the drugs uh that they um that it can bring uh either are they sorted or unsorted they are unsorted okay unsorted so um think about this yes so i need to bring five jobs and in every uh array in which i bring all the elements means in one time i can go for one and then i can go for two and three so there can be an element and i need to find what is the minimum time uh in that time i can uh uh in that type all the jobs will be fulfilled by the target and it may cross the uh target also so on so can i do this linearly because i will just i will check for one four two four three and then uh i and then for just let's suppose i am doing for one so for one i will check how many uh for in time one how many are bringing me back this jockey jokes so i will just divide all of them by one and whoever is uh and i will take the integer part only only of that because um i need only the tips that they made so um so for for one i will divide all of them by one and i will get that uh only first one is giving me one so total chunks are one and for the two i will divide all of them um by two and then i will get that uh first one is doing made two tips second one is only one and third one is no no tips so i will just add up all of them and the output will be three so according to this approach um i will just uh linearly uh go through uh one two three and the time that i will require and i will i will check for every say time that how many number of uh jugs they are bringing to me and if it crosses the threshold part of our problem uh then i will just stop and i will return that current time that uh i was on so um this uh this approach will work uh i guess yes okay let me start can you tell me your approach in summary yesterday because you were thinking yes yes so the approach that i'm currently thinking of is uh i will uh linearly go from time one till uh till i make the threshold so for every time uh that i'm counting uh i will i will suppose i'm counting for time equal to one so for time equal to one i will check how many number of jugs ah i'm getting so i will divide all of them by one and i will take uh whoever is giving me greater than uh value one uh so i will just take the integer part of that so suppose uh i will divide one by one two by one three by one so um uh one so one by one uh one by two or one by three and then um i will only get one so my at time equal to one i'm only getting one uh job for two i'm getting three jobs because one one by one uh two by one and two by two or two by two and two by three so i'm getting three jobs so when i when i will get a job equal to target or greater than target i will just stop and return the current time that i am standing up so this this will work yeah can you start complementation uh yes also okay can you tell me the time complexity of the solution yes so for this other time complex today each time i am dividing the whole uh array elements means or by that current time and checking that sum is uh equal or not um so um so um the time part will be uh so let's uh off often will be the dividing part and for every time i am doing that so it will nearly go around um not of n square but uh it will greater than o of n but not of n square because i am just going uh to time one time two and time three here so um so it makes uh right so try to think in terms of changing yes yes so at max i'm going till uh the element which is the maximum of that uh maximum of that array because after that uh i am not bringing many uh after that i am not bringing any more so the max element i need to go to the max element and uh for the maximum i am going uh to every element so the max into of the max of elements into of n where n is total number of elements so suppose suppose the range of the range of a of i is 10 to the power 9 okay so um in that case it will actually all throw uh so so for that um for that uh i need to it will be um into for every element um i am going to the time one time too so till how many time i am doing this so atomic so if there is if they are 10 to the power 9 so i need to do for 1 2 2 9 um [Music] so the time complexity will be the maximum of maximum possible uh maximum possible element into the maximum possible range of that element into total number of elements uh yes yeah so it would be big o of n into 10 to the power 9 so if you try to generalize right this would be very this won't be visible yes so uh talking about the better approach for this what the what the reputative work i'm doing here is i'm going to every element and i am checking that can this bring me to the target and again i will i'm going to the next uh time and checking that is that ring with target so um here the minimum minimum time that i will be doing is one because below that i can't do uh some anything so my low limit will be one always the limit of the answer will be always one because i can't do minimum of that so i'm talking about the maximum limit of my current answer uh will be um uh will be uh if if i do if uh if i take all the if i take time as 10 to the power nine seconds and uh i will divide all all of them by 10 to the 1i uh so in that case my answer uh answer will um surely uh lies um surely uh the maximum limit of time is 10 to 1 9 so um as as i can see the answers are in the range of 1 to 10 to 1 9 so instead of instead of doing this linear approach we can apply the binary search on the answer parts so uh as uh as i am going from one two three four till counterbalance so i can just do binary search and whenever uh the midpoint that i am getting i will just take for that midpoint uh what is the current value of the target uh the current value of the sum of all the elements when i'm dividing that by the current mid element and i will check with target if the target is uh greater then i need to find the smaller smaller part of time when it when i'm writing that schedule so i will just reduce the higher limit okay i understand this can you tell me what would be the upper limit of your range yes so upper limit for here here the maximum element can be 10 to the power 9 and also uh the what will be the range of uh the number of elements in that element total elements range of the elements is still 10 to the power okay so um for that basically first i have to take all all as long because all some part will be executing so i will take long as data type and the maximum maximum range that i am thinking of because if if the current element is also 019 and the maximum elements are also 10 to the power 9 so for sure let's to be sure uh the maximum um maximum range the higher limit will be 10 to the power 18 in this case and the lower limit will be one okay yes um can you start implementation of this yeah sure so uh all things will be given in the global space you would be given an array you would be given the size of the array so basically it would be n so basically just remove it can you remove it yeah just yeah just remove it by two yeah so you would be given three just right through yeah that's absolutely yeah three a white space yeah just two then suppose it is five five yeah go down and one two and three yes and this would be the number of jars you need to fill basically and this is the number of jars that i am bringing now time taken by each person to fill one job yes time taking time taken each just right and taking each yeah great thanks a lot [Music] yes uh so here the n is total there are three uh time there are three elements and i need to find the maximum five as a target so um for this i will just do um next mean time taken uh so here i will uh initialize my current um me and low as uh one and end highest highest or 10 to the power um 18 so yes so for that i just it will look long long so let's just to avoid all the overflows so um while uh i will do while uh while my maximum the while the sum of the current element that i am dividing is will reach to the particular element so i will function and if it is possible it will return me to that yes i can do the threshold part so i will just store into my uh answer part that yes yes i can do this at that at the current time so uh i will just uh initialize it currently minus one and uh i will update every time when it is possible to find the uh answer with the current time so i will always update and whenever it is updating uh answer it surely it uh make sure that that current time at that current time it is possible to make that target then what i will do is i will uh update my higher limit to the mid minus one because i need to find the minimum so i will check for the minimum part uh so my higher limit uh will goes to mid minus one um and uh if if in uh if is in if in case uh while um sorry um while uh less than equal to higher uh uh if if it is if it is possible um if it is possible to do that i will just update my answer and uh the ipad because i need to find the minimum one so and if in case it is not possible to make the from the current time uh i will check for the low limit by increasing uh till uh high to the mid plus one five and whenever i will just uh whenever i will uh found that my low is greater than high uh i will just return my answer uh so uh what on the i need to implement this is possible function also so for this if possible function uh i'm uh first i have to find the mid so for the mid part uh uh it will be uh low plus uh uh high minus low by 2 and it's possible we'll get a mid um from here and i will divide all of the elements by mid and uh if that mid element if that sum of that all the elements is greater than the target i am returned to uh if it's not i will return false so that's a okay implementation okay so yeah just a bit of information so this is absolutely fine so what is the time complexity of this solution yes uh so the time complexity is that uh the range that i am currently holding is from 1 to 10 to power 18 so um so and i'm doing binary search on that uh on that uh length so my total time complexity will uh go um till uh uh search page uh search space uh of n log n and also i'm for uh every part i'm doing that it's possible function and that is possible function will take off n times as there are n elements so uh and into search space uh and log off search page uh the search space is from 1 to 10 over 18 so approximately 10 to 14 so this will be the time complexity what would be the time complexity can you repeat again yes uh so the time complexity will be uh total number of elements into the search space and on into log of search space behind the search space here is from 1 to 10 to 418 so the value of such space is 10 18. so let's so n multiplied with log of the sub space this is what you are telling sorry sorry that not the outer part only the login and into total number of elements okay so that's it suppose yes i will be explaining you well can you open the last step that you have with them yeah so by the way can you go back and you go back to the solution that you have just implemented can you optimize over this high thing uh optimization of a high yeah uh so talking about the optimization here um uh wanna reduce the search space yes either you can go with the low either you can optimize the low either you can optimize the height okay so um let's uh go to the as my target uh as my range of this number value of that element can be 10 to power 9 and number of elements also can be 10 to one line so um if if the if the let's suppose if the current element if if i want some element as 10 to the 1 9 and the total number of elements are also 2019 so in that case uh my maximum possible time that i will take will that be ever will that ever be 10 to 18 um or not um because okay okay so let me do it for you because we are out of time okay so let me just change the download so yeah go back to the solution first question that you implemented yes yeah so here you were confident enough okay you seem pretty good you explained pretty good yeah but a small mistake what you did was when you are selecting a particular weight you need to add that value to the answer so in line number 26 you need to add that value so can you rectify the value this value of 5 will be added to this part because i'm selecting that current element okay now you've got your issue yeah yeah definitely sorry now let's go back to the binary search thing yes yes see this was a great problem to be honest and binary search is my favorite topic yeah but what you can do is the worst time complexity would remain the same but if you talk about the average time complexity then you would come to the conclusion that see whenever we have the minimum time complexity eight percent come time the complete concept we can finish that job yes uh definitely we can do that so what we can do is we can do that the number of jars we need to fill multiplied with the minimum elements that we know am which i want to talk about see you're very confident enough okay it seemed pretty good but suppose what you think is you tell us you narrate the thing that you are trying to implement but what i want what i what i suggest is not want what i suggest is at post you can think that this this is gonna work or this is not gonna work why because see words from your mouth we can't backtrack it backtracking is not an option so when you think that yes i'm going to do this think about it for a second analyze if i'm going correct or not then speak okay because you got backtracking for some movements okay it shows that you are a little bit confused yes some parts are not clear that much but uh i am preparing that to complete that part that's absolutely fine i'm just suggesting okay now the next thing what i want you to do is you're very good with brute force you started off the good points about your performance you started off with group force you gave time to think you introduced yourself with the projects too i didn't need to ask you about projects that was absolutely great okay but you seem a little bit in a hurry you don't need to worry give yourself time take your time start the implementation and the next thing what you can do is just write declare the variables enough more explanation in explanatory manner yeah okay just a more explanatory you can use underscores or something okay not like this targets and all you can do else apart from all this you were absolutely great okay you were absolutely great with the implementation you don't make a mistake okay you are good with indentation okay and the function callings and all yeah you do functional programming a lot that's absolutely yes okay whatever you are doing is great just keep up with the practice and things about think about and literally what you can do is i ask the problems which were kind of generalized yes yes yeah so what i want is is to focus a little bit on the problem solving part two yes i am focusing that's absolutely fine so see if you talk about dynamic programming it has a beauty so it has a beauty to detect it like if you want all possible then there are approx 50 to 60 states then you can talk about it then what the next thing suppose it is a monotonous function when you find out that it is a monotonous function we want to do that that lower boundary if it is a modern assumption we can do that we can do this okay that's great okay this solution okay so that's it for today that's it for today thank you all the best me thank you for interviewing me and also the extension part that you said that you are using i'm happy for that and i i don't know that you are using that part yes and uh thank you for that yes and thank you for gfg also for and this opportunity and i recommend all everyone that are watching that stream is the best platform i i consider the gfg as a bible for every part of my coding journey so yes that's it so i if you talk about me i do learn from gfg now i am working from gmt i tell you that whenever i want to suppose i i don't remember the stm i don't remember it to be honest so i just write the thing stack and then write g of t i mean yes link will be always dfd link so it is the l over there okay okay that's great all the best again okay thank you yeah sure