Live Mock DSA | GeeksforGeeks

Key Takeaways

[Music] [Music] hi hi are you sure this course is just for two for nine nights yes and you know this is the only course with this expertise across the world no way yes way [Music] don't delay enroll now geeks learning together hi everyone welcome back to geeksforgeeks my name is yashdivedi i'm working as a mentor at geeksforgeeks i'm a candidate master on coach shift code forces anna five star on courtship besides this i have also some other uh i have also some other achievements in cp so today we'll be interviewing our guest that is tanmay he is from iit so all of you can just quickly give me a plus one in the chat if my voice is clearly audible and everything seems to be working fine so that we can invite invite our guest for today smog interview uh all of you can quickly give us a plus one guys if my voice is clearly audible okay so i'll invite hi how are you hi hi hi i'm i'm fine uh so can you please quickly introduce yourself to the audience so hello hello people uh i'm fan messing i'm currently personally take from my db issue i'm in my fourth year uh i've been doing cp from last uh two to three years uh i've done quite a bit of web development also one two projects on that also and i've explored a little bit of machine learning but not to that extent so that's from my side can you explain us about any of your projects that you have made any so the first project which i did in my second uh year was basically one of my startup idea which i had with one of my colleagues so the idea was to actually uh build a platform where doctors can actually make a centralized platform for their different appointment working because it's quite difficult like you go to a doctor or a clinic and you had a like you have to uh book appointment it's quite tedious like first of all there's a lot of delay you have to wait up a lot of time so our idea was to uh people can facilitate there are other companies who are also doing that thing that practo is also doing but our idea was to we would build an algorithm which actually will actually find a particular uh period where that particular uh appointment is free for everyone and so in that particular period uh you can book your appointment so that was the whole thing which we try to build uh uh in my second in in third year in the things it doesn't go uh as as planned so we dropped that idea but the site that i built for the whole thing was still there so i used it as my project in my resume uh great so as you know today i'll be interviewing and i'll be asking you at least two dsa questions in span of 45 minutes to one hour so are you excited for this interview or you're nervous yeah yeah yeah i'm totally excited no i'm nervous also okay so uh can you share your screen quickly okay uh down there you will find the screen sharing okay so your screen is visible uh if you will look uh yeah uh yes it's visible if you look in the private chat so i've shared a question yeah can you quickly open that up okay great so you can quickly log in great so let us start with the question so the first question that i am giving you uh in this question you have to count the total number of set bits so what do you know like do you know what is a set bit yeah yeah yeah the number of ones know basically uh if a bit uh like either a bit can be zero or one so if it is one then it is known as a segment yeah uh so what i'll be giving you is i'll be giving you a number okay that is in it i'll be giving it giving you an integer number and what you have to do is you have to count the total number of set bits from one till that number in are you clear with this okay if i give you let's say three so in that case you have to count the number of set bits in one you have to count the number of set bits in two then you have to count the number of set bits in three and overall you have to return the final total so is the question clear to you because uh if you will see so in one there is only one set bit in two there is only one set bit in three there is two set bits because three is represented as one one so total there will be how many set bits four set bits so the answer for n is equal to three will be four so what uh you have to do is you have to tell me uh like i'll be giving you the n value and you have to tell me like how you will count the number of set bits from one to n okay so the first part which comes to my mind is to actually iterate over one to n and count each and every uh set bits like uh total do a bitmaster thing and count all the set bits uh you can iterate from one to n and for each uh integer you can count it so that's a first operation that comes to my mind uh the accurate complexity is saying log of n so to think that approach that how we can do it in log n of n is an interesting thing uh okay so you can you can do one thing you can remain on this screen only there's like there's no issue but what i'm asking is like you are saying that what you will do is you will iterate for every number and you will count the number of segments in that number so uh that that is very basic approach and even the audience will understand that but uh one thing that i'm asking you is what will the time complexity of that approach can you tell us about that so basically uh if uh i have to count that each every two and login would be the time complexity of it because uh if uh each of number will be counted for log and so correct so can you think of optimizing this approach uh so what can optimizer push for that [Music] like uh if i'm taking a number n so whatever you are thinking you can uh keep on sharing your thoughts like you can think out loud so that we understand like uh what is your thought process okay question okay so first of all if i uh write number n so uh can i do where i can do a work like i can do it here also you can you can do it here only you can do it here only no problem okay okay so what i can do is that if i represent an into uh one one thing you can do you can click on the setting option and you can increase the font size a little bit okay uh you can you can click right there there is a setting option you can click escape first of all uh there's a setting option yeah uh you can increase the phone to let's say 16 16 16 will be fine great okay now you can tell us so the first of which it will be one particle one double one so every number uh which is less than n uh will like let's say two and let's say one will be less than three so what are the bits going to change the first thing is that the first bit uh will the first little bit will change or the next bit like let's say take a bigger number i would say it's a lot better so let's see if a number like uh it is going to be let's say 16 let's say 16 is good so the representation of it is like i think it's this are you sure yeah sorry so let's say 16 so i think you need 1 0 4 16 okay yeah so every number which is less than 16 uh will what will be the like first thing if i remove the first bit of it like one uh if i make it to zero then all the numbers which are less than that i can find it like if i make it the first bit is 0 let's say 15 then the representation of it will be 1 1 so if i remove the first bit of it then other numbers which i can get uh uh will be the total uh count of it likes uh so what we can do is that first we will find out what's the and a panel representation of the largest number n so what we can do is we can either flip this particular index or this particular index and this particular index okay so once we uh do it like if we flip this particular index and then this particular index and this particular index so every time we will flip each of the bit uh then uh and if i uh remove the first bit of it as it is zero then all of them will be less than uh less than n so let's try to implement okay first of all uh am i going right in the right direction like uh you can you can just tell us about a bit more like first of all you're saying that you will have the my representation that is fine i know that you can get the binary presentation uh and then this after getting the second thing which binary prediction i'm saying that uh for each of the binary representation each of the index of that particular binary representation of the number i'm gonna flip each of its bit so flipping its bit means that if the left most bit is one first of all we gonna make that one zero so that every number which we are going to flip in above that number is going to be less than n because that's our priority because n has to be less than uh and all the number we have to take is less should be less than n uh so but you have to configure that as well and as well so for that we can do it i think it's uh it's kind of a db mask thing i uh what i can think of uh let's let's try to let's try to write a function of it for it uh i think it's a deliberate mark uh but i don't think unlock in the interest is login if you if you had to do let's say something like dp only then uh instead of that for every number would have been better yeah yeah okay because so see order of order of n log n approach is when uh when you are hydrating for every number correct but if we want a smaller complexity so obviously the smaller complexity will be in terms of logarithmic only so uh if you have to think log so what does it mean by log log means that when you are basically iterating through the bits of a number right in with respect to this question logarithmic complexity you will get only when you are thinking something about the bit representation so uh can you think a little bit more you can be on the same screen here yeah so what i can do in this is for each of the n i have to find the number of set bits like uh okay so first thing yeah let's take any number uh so uh any number let's say 16 so the last bit uh it's going to defer after each of the one step like if i take one then it's going to one one zero one one so the last bit is going to uh iterate over let's say if i take 16 let's say if i take 16 so if you want you can do smaller numbers as well if one is going to eliminate 2 is going to be 1 0 and 3 is going to be uh 1 1 so this last digit is going to be alternatingly uh changing it like first is going to be 1 then it's going to be 0 then it's going to be 1. so for odd number of times it's going to be so the last number will be n by uh n on n by two plus one and for like let's say four uh four four is four but for even number for odd the number of uh last bit is going to be n by two and for even but even it's going to be 1 by 2 so this is the first observation i can see uh from this question so if i take the second last bit uh how it's going to change like if i take the second last bit then uh okay let's do one thing let's write it till four let's write it till four and let's see what uh you can observe and what you can do is you can write uh one as zero one so that we are more clear with it okay so okay if i'm saying it to be a glass it is different after each of time and the second last bit is actually are differing okay okay let me see let me see okay okay what we can do is uh for each of the bit we can find out how many times 2 is going to come like okay let's say if our number is n and i'm taking each of its bit low so let's say it's going to be two and this is going to be one and one and it's gonna be zero one um you can think out loud so that we also understand what is your thought process okay and sanskar uh you are saying that you are not clear with the question so basically what i'll be giving you is in this question i'll be giving you a number n and you have to count all the set bits from one to n like one has one set bit then two will be having one set but then three will be having two set bits so you have to count the total number of separates from one to n that is what you have to do in this question okay so that is foreign [Music] let's say for this uh so far and i can do is let's first take each of the bit and each of the bit has is flipping for 10 position after one times and for let's say for the second position it's going to flip 0 1 1 0 and 7 for 8 is okay so it's going to flip like for two times okay it's going to flip and similarly uh this position is flipping for zero zero zero and then for four times and so you're saying that for the third position you're counting the number of uh set bits yeah so if the for the third time it's going to flip by okay so what it's actually uh by seeing the pattern i can see that uh the last bit is flipping by one the second last bit is flipping by two and the third luggage is driven by four so uh to look at the pattern i think that uh for the second last bit in the nf bit and it's a can you explain this a little bit more why you are saying this what you are saying i understand but can you explain this a little bit more you are saying that the last bit is flipping by one what do you what do you mean by that uh what i mean by that is that if i take it from one so after one becomes two so the last bit is going to be uh is uh changes by one and then then again it comes three so last bit again flipped by uh one so each of the time it's alternatingly uh changing itself after one step uh if i look at the n minus two with bit then after two step it's changing itself like for one it's going to be zero but for two it's one one and after that four and five it's again one one and if we continue that pattern i think it will follow it so far so n minor and one alternatively alternating alternate on alternate basis it is getting set and unset you are saying this thing yeah yeah yeah for n minus 1 it's getting us changed by 4 so basically it's changing back to the top of 2 to the power of what i can say to the power of n minus 1 so n minus ah it's actually changing with the power of n minus uh since it's one minute so n minus i it's changing back to the power of i so hawaii changing of that separation uh but for this question i can use this fact i can use this fact to solve this question so if it's changing by the two so after each of the bit i have to find that how many times it has come um so for four and similarly we can do it for n minus three r okay minus three triple three we can do it for n minus three but also so it will change it by eight okay so now what we can do is if it's flipping each of the letters flipping after um yeah so let's say if i'm at one and if it's at vertical zero do you think that uh it's uh this particular observation is right like uh we can use this uh for solving this question or there is some more observation which we can make so what i can say uh what i can say is i i am impressed by the way that you are thinking the pattern that in which you are thinking it's it's almost you are almost there but you need to see like you are saying that you are saying that the bits are flipping and all that stuff right you are you can again move back to the coding screen only yeah so what you are what you are telling me you are telling me that how what is the behavior of the flipping of the bits but let's come back to the question what do you want you want to count the number of set bits correct that is what you want to count so just just just keep this observation only maybe you can keep this observation maybe but just think about every position every for every position think about how many set bits are there just think about that and then okay there is an observation in this question you have you have cracked the question correctly that maybe there is some observation that i have to do but what you need to think is let's say that you are thinking about the last like for every position try to count the number of set bits there and then tell me what is the number of set bits for the last position here for n is equal to eight what is the number of uh set bits for n is equals to eight okay so basically i'm saying that for for n is equal to eight uh what is the total number of set bits for the last position okay okay you can quickly count it starting from one till eight what is the number of set bits for the last position one two four four one five five uh when i say last question so basically i mean the right most bit okay okay okay because you were counting from there only now four four four yeah this is the observation i actually meant that for the last question if it's even then it's going to be n by two if it's odd then it's going to be m2 n by two plus one uh uh okay but uh let's let's count it for the second position as well okay okay okay i got this question i think i got this question so basically what i have to do is for and as you can first of all tell us what you have observed yeah so for the second last position uh we can say for if i have to count that one one two two four so it's going to be four so i if i make observation then for this if i this is for n minus one position if this obvious observation is for an exposition sorry if this observation is for next position uh basically the last two is the last position you cannot n by 2 by looking at it 1 by 4 sorry and by 4 now if i look at the third position then it's it's looking at 1 1 uh what's going to the third position it's four it's also four okay so you are saying that for the second position also that is from the for the second position from the right also straightforward so if i actually look at this whole thing why have you for n minus one like for the say uh okay great uh why have you written n by four uh in the upwards actually i was thinking that it's following a pattern from for n it is going to be n by 2 n minus 1 is going to be n by 4 but i i don't think it's following that pattern it's it's 4 bit 4 bit okay uh can you uh tell me for the third position from the right uh how many bits are set for uh for the third position it's four but four four bit more bits are set i think correct correct yeah so with respect to the value of n what is four so obviously four is one by two and by four uh there are total four positions i can see right uh because there is since there is eight also so there is one more additional position that is the fourth position that i can see that is the left most position and can i say that the leftmost position in everybody is zero except for eight correct except for it yeah yeah so i can take it as an exception and i can maybe handle it yeah okay uh but does this uh like maybe you can see a pattern right yeah yeah okay but does it prevail for all the numbers that is the thing that you have to choose okay for one it's going to be um and for four if i'm asking for the fourth better but then it's actually changing for four and let's see if i take just that uh let's say you take it for n is equal to six so does this pattern prevail no uh that's only i'm saying that it doesn't work for that but uh why um what i'm thinking of for different for this question what i can say is that for one it's going to be one and for six we have to look at the number of times so what we can do is if for the second bit we are having um for this we can see that okay okay uh what i can think of now is like uh if let's say there are if i'm at third position it's so the number of bits it can flip on is one and one like let's say what can be possible zero and one so two into four so the four times it can if there are four combinations that are possible for okay what i can think of is that for uh each of the to the of x position we can find out the number because i think that's a following a particular thing and we can think that what's nearest to the end and what nearest to the power is n uh let's say okay you have to find for if let's say we have one okay why are you finding nearest power of two for a given value of n because i think that uh if uh we are able to find that uh the nearest to the power of four uh nearest to the power of two then uh there are for the nearest to the power of 2 we can find out and if we are able to find the pattern for the nearest to the power of 2 then we can use same pattern to find for for n so let's say for okay first we look for each for each number which is the power of two so let's say for two we are counting the number of segweights so if we are counting the number of set bits for two then its for two is going to be two total sum of the set bits the numbers which are less than two for four we can say that let's write here three uh zero one one so we can say one zero zero i can save uh seven seven two nine 9 9 3 12 12 and 13 okay if i look at the pattern for this the total count of it is uh initially you were thinking in the right direction now there is a little bit of problem with your thought process i think it's not working so for that particular process was i am i was making one zero zero and it's alternatingly changing for two for for the second bit it was changing for let's say it was two and after two position it was changing for this it was let's say let's start try to find out a little bit more one zero zero and one and it was one zero zero one so i think that pattern holds because like it altered alters after two okay so for n is equal to 10 for the right for the right most bit how many bits are set for the right mode split uh one two three four five five five that's five okay so that that's n by two you are saying yeah yeah that's that's that's i think that's good from the right side how many a four okay okay wait a second position i think i think uh the question uh answer would be four um for for the uh if i'm looking at the n minus one equation you're asking [Music] basically you should not say n minus one you should say the second second the second last second okay so for uh this last one is it's one last fix one it's uh and for the second last bit i can see the second four four uh four three seven third last bit is going to be seven uh are you sure wait a minute four last bit okay foreign so it's four so the pattern does not exist yeah the pattern does not exist but the pattern exists till 8 yeah and the unique thing about it is eight is the power of two yeah that's what that's what i was thinking that we need to think what uh that to the nearest to the power of and then we okay okay let's let's say let's say the pattern exists so for which kind of numbers does the pattern exist if you are able to see that the pattern is existing which are the power of two the numbers which are powerful so it is existing for the power of 2 so uh if i give you n is equal to 10 let's say so can i uh can i expect like let's say if i give you n is equal to 8 that is the power of 2 only so what will how will you count the number of set bits if the pattern is existing then what will be your approach or formula or something based on this party at least for a power of two what will be your formula so for the power of 2 if i have to just find the for the power of 2 then what what's going to be the formula so yeah the first thing which we can observe for the power of 2 is so what was the total bit of number was for eight i think i think if it was holding like it was four and then it was four and then the third set bit was four so it was total uh four was three done so and one was extra four and uh into three plus one was the pattern because last bit and the second last and third last was four 4 and the last the fourth bit was one here if we see for this also then it's for first for two then again it was two and then one was getting added at the last so for 4 the pattern was 2 into 2 plus 1 okay no no just tell me in terms of numbers now like in terms of value in terms of n what will the formula if you are able to observe it in terms of in terms of and what's going to be the formula so for in terms of n if i have to find the formula then for eight it was uh but let's say eight it was eight by two and that was accounting for n minus one so i think the formula for uh to the power four is going to be uh n by two if it's c obviously it's going to be even and into n minus one so let's say n is the power of two yeah so whatever you can say p p because for eight you have three positions in which you are having the same pattern yeah so for uh for uh to the power of 2 we can say that it's going to be p by 2. you should write it as n by 2 n by 2 into this thing okay i should write it n by 2 okay yeah n by 2 into uh into into minus 1 to the power 3 okay so maybe you are whatever extra bits are there you can count it correct but now uh just just do one thing have that nine and ten uh just put that nine and ten or close to eight only and now let's try and observe for the further cases okay uh just put that nine and ten now okay so for the for the power of two you are able to calculate okay now there is nine nine and ten also so how okay yeah so till where you have counted uh let's say let's say let's say you just count for let's say let's say there is a right most bit that is one in eight nine and ten there is a right post bit that is one correct yeah so maybe you will handle let's say you handle it later on somehow or the other or maybe through some pattern you'll handle it but till till where you have counted the bits can i say that you have counted it till eight till eight all the bits are counted except the last set uh the leftmost bit you have counted all the things right yeah then then if you observe so nine and ten is there uh one bit one c the leftmost bit in the leftmost bit in 8 9 and 10 is what you have not counted so that you maybe you will handle it somehow maybe you will handle it somehow we don't know as of now but if you will see so now which numbers are there which to have like if you ignore the left most bit that is one in eight nine and ten other than this which bits are not counted uh okay okay but uh one thing is that if we are going to the closest to the power of uh an n so the complexity is log of n so for other we can just uh uh count it like uh iteratively like uh we can do brute force for that it's going to factor okay because okay uh okay you write 11 as well let's write 11 as well so that we can observe something new yeah all right eleven one zero uh one one yeah okay uh now just uh just add it till 11 only we can see it 11 only uh now just do one thing just put them into place uh yeah eight nine ten and eleven just put them in one line so that we can observe something just put eight also with a space okay so if you will if you see till eight you have counted let's say you have not counted the right most bit okay let's say you have not counted the right most bit so how can you count con count the right most bit here any idea uh for the route right it's going to be easy because it's uh if any of the number like how many the nearest are so how many left most bits are like basically not right most left most so how many left left most bits are not counted uh for what uh for n is equal to eleven uh some left more renders are only not counted yeah yeah so for for the lesson uh what we can see is uh if you'll observe what is uh like basically uh if you will see four num four bits are there no for eight one bit is there nine ten eleven twelve okay what is the closest power of two uh for eleven is uh is going to be eight so is this some relation between n and the closest power of 2 that you can do so that you can find it [Music] okay n minus the closest power of 2 plus 1 n n minus 8 yeah n minus eight plus one what is n minus eight plus one plus one is going to be 11 minus eight is going to be three and three plus four so four bits you you can count the extra bits okay let's say you have also counted the extra bits now which bits are not counted so from 9 10 11 if you will observe so which bits are not counted 0 see in 9 0 zero one is not counted correct you have not considered zero zero one till for ten you have not considered zero one zero for eleven you have not considered zero one one zero one yeah so if you if you separately think it can i say that 0 0 1 is nothing but 1 can i say that 0 1 0 is nothing but 2 can i say that 0 1 1 in 11 the 0 1 1 portion is nothing but what three okay so again the question boils down to counting like okay what is three here what is three in n value is eleven what is the closest power of two eight so what is three three so basically uh eleven minus eight okay got it so for twelve is going to be so again what you will do is again you will count for n minus uh the closest power of two are you getting this yeah yeah you got it uh but uh you you could have like basically what you will do is now you will first of all find the whatever value of n is given you will find the closest power of two for that and then you can count the bits okay for the close close power of two then the left most bits that are there you can also count them then what is left is some bits uh some bits from uh here if i see till eight everything is counted and the extra bits in the left side for every number is counted till n now only the bits that are there that are left 0 0 1 is left 0 1 0 in 9 10 11 12 respectively respectively all these bits are or left and if you will see so that is nothing but n minus the closest power of 2 because if you give me 12 so from 9 till 12 i have to count the number of bits from 1 to 4 that is nothing but from 1 to 4 so again you have to recursively call the function yeah this is gonna take a difference and then again the uh we'll find we're just gonna take the difference to the nearest power of two and whatever the answer we will get we can again find the nearest power of two and then we're gonna take the difference and find it till we got to the last point uh what uh but one thing i'll say you were able to come up to this thing very very soon you set closest power of two very very soon but maybe somehow you lost in between because you were thinking about some permutation combination or something i am maybe you are thinking a little bit more mathematically but if you would have just kept uh given it a little bit more thought uh maybe you would have cracked it but no worries uh let's move to another question so i'll quickly move to another question so what i'll do here is uh if you will look at the private chat so i have shared a document with you can you open that okay so let's quickly see this question as well okay so let's uh quickly read the question you know about binary trees yeah uh basically left child and right child uh every route has two children right left and right yeah so what i'll be giving you is uh you can do one thing you can click on full like you can click on full screen if it is possible for you uh i think it's f11 or something great great yeah it's works fine okay so just scroll down a little bit uh so that i can show the problem statement to others as well or you can scroll down like yeah right perfect so see i'll be giving you by entry and what you have to do is in this particular given binary you have to split the given by entry into two different sub trees okay you have to split it maybe from the diagram you can see like there is a particular binary given and there is a colored edge so basically from that edge i am splitting the binary into two different halves okay so i don't know from where i'll be splitting i don't know but this some at some point of time i'll split okay so there is one edge that i'll remove so it will be uh it will be i'll get the pie tree in two different components correct basically two different parts it will split into two different parts and what my task is my task is to split the given binary into two different parts right by removing one of the edges basically will remove one h then it will split into two different parts so i have to split it into two different parts such that the product of the sum of the sub trees is maximum because if you will see if i split it from this orange edge then the first part is what 2 4 and 5 the sum of that particular part is 11 and the second part that i see is 1 3 and 6. some of that part is 10 so if i multiply that part so i'm getting 110 which is the maximum product that i i can get so basically what you need to do is you need to find the maximum cost of splitting a binary in which you can remove one edge and you can get the maximum cost are you clear with the problem statement as well yeah yeah if you will try to split it from any other edge then you will not get the maximum answer you can try that out as well uh can you move to the second example as well so that i can explain to you as well we can have a look at that okay so now if you see again a bi entry is given now uh you can try to split it from various ways but uh the orange edge that is given from where there it will split so you'll get the maximum answer because if you split it from there then the first component has the sum is six the second component has the sum of the nodes as 15. so the product will be 90 and you can try your combinations you will not get any product better than this so what comes to like is the i hope that the problem is very much clear to you so what intuition comes to your mind so first implementation that's coming to mind is that first of all i'm going to calculate what's uh going to the subtree uh for left and right what's going to the sum of the uh subtree for the left and separate for the right which we're gonna store in uh i one and zero form like for uh right is going to be one and four zero so for each node we wanna uh uh pre-compute it for uh what's going is the sum of left subtree and what's going to be the sum of right subtree uh so what we will do is uh first we're gonna do a dfs search and from the root we're gonna first go to the left subtree since we already know what's uh if we go to the left sub tree we will take the sum of the right separatory of that node from where we are going to the left subtree uh and the parent of it the sum of the parent of it we will also store it so that we are uh basically we are rerouting the node okay are you kidding me on which node we are going we are re-rooting that node one okay so for let's say i go for one uh for left subtree i'm gonna store the sum for the left subtree that is two plus four plus five and for uh uh right subtree i will store for three plus six which is nine for one similarly for so four uh before you move forward before you move forward uh you are saying that you will do this thing okay so it will not happen automatically you have to do this thing so what kind of traversal will you apply for it um for that i can uh see that uh is there any any specific name for the traversal that you are applying uh because i think uh for if i'm applying then uh i'm applying so i'm i'm playing forward like in order to reverse like uh because i'm first visiting the left node first i'm visiting the left node then i'm basically in the right node or i can do the reverse of it like for the right node also we can do it for then log in the left node so it's not in order traversal or the poster and pre-order traverses it can be both of them and both will work fine you know basically post order yeah post order okay uh either you can do left right or root or you can do right left or root but basically that's nothing but post order kind of thing okay then post order okay uh so basically we'll do this also uh so we'll store the left for part of it and right part of it uh similarly we will do for one similarly we'll do over three so once we are we have precomputated all the left subtree of a particular node and the right subtree of sum of uh left three of us a particular and right sub tree of a particular node so then again we will do a second traversal in which we are we have computed all the left subtree and the lagrange subtree sum uh then what we will do if we are going from one to three so what i need from one if let's say not it's not a great example let's say i'm at 2 so what i need from 2 i if i'm traversing to the left of it then i need the sum of right part of it this part of it and the parent that it had already as some of it and four already contains the left and the right of it so we're gonna sum and find so for each of the time we're gonna break this edge and we're gonna uh do a product of it so i should implement it like it's a little better if i implement it like uh you can quickly write the code so you can assume that i'll be giving you a function you will be doing it this thing okay yes is it right is it right i think this you are almost thinking in the right direction yeah but can you tell us a little bit more in this example how how you will identify this this orange edge or how you will break it from here like you like see you will always keep a track of the maximum but how will you get this particular sum as one one uh like multiplication as one one zero how will you get that so for r2 already i know that what's when is it is it it had the sum in the left and the right subtree so we're just gonna sum for it because we know that if we are breaking the edge we are breaking the parent of it okay so you are getting it from the current current uh so obviously the edge which is being broken i know the uh we have already pre-completed for one all this uh right subtree and we are uh saving that particular thing in our dfs function so we know that uh product and we just gonna multiply the sum of the left and subtree and right separate for the two and we want to find for each and every node we will uh each and every each and every edge we will visit uh but uh there is still one conflict now like for one uh you are not multiplying the left subtree product and the right sub recorder you are uh considering the root in the in the right path that you are breaking now okay what are you saying like uh um uh i'm saying that i'm saying that you are saying that you're saying that maybe you are breaking it somewhere from one correct you are saying that you are breaking it from one that is your current root is one then maybe you are breaking it so you are saying that you are multiplying what i am doing is i am not uh breaking the edge from one to two yeah i am at two then i am breaking the edge uh for the parent of it okay so already we have stored for the parent so we know the value of what we have already accomplished for the parent so if we are on note 2 then we are breaking the node from from the edge from two to one so we already have that particular parent the uh let me implement it like it will be better if i implement it it'll be much more clearer here uh i'm clear with it but i just wanted some clarity on the right and so what you can do is now you can just think of a function in which you will be given uh you will be returning an integer will be given yes you can write it here okay so let's say i'm you have to return the integer value and you will be given the root of the tree first i'm going to pre-compute all the things like if i say that i can do it for let's say you know an integer is n the number of you are going to apply dp here no not bp i just pre-computed so i can do it free also literally use uh for as a db so and then two so to represent the left zero represent the left node and one represent the right node okay so i let's say i put one more constraint on you uh let's say maybe you can do okay let's say that you can do this using taking uh by taking some extra space here right that is using this uh prefer like uh pre-computation you can do it but if i uh put an additional uh constraint on you that you cannot do it using this particular extra 2d array 2d matrix that you are taking then anything that you can think of okay let's say if i ask you that you have to do it using the traversal only somehow or the other using some traversal only okay okay okay i got it got it so if i have to do it uh using trouble and i know that you can do it um so what i'm going to do is uh first i'm going to find for each left i will know the number of uh other sums i will find okay let me find for it i'll write the code for it uh so if the audience is clear with the question so guys you can make sure to hit the like button and please comment on a plus one okay because the questions today asked were of good level so you can just quickly write a plus one in the chat so rude so what i'm gonna do is uh first of all i'm gonna find the sum for uh the left of it let's let's see if i find the sum for all the left uh subtree uh once i have the left separate i know that the this is the whole sum now we are going to get over the right of it so now we have the parent and we have the total num uh what i can say the total sum for it um okay and i'm going to put them troubles for this edge and if i break this edge okay so i have the sum for it and then i can troubles on it um again so um okay so yeah what we are going to do is uh let's say an answer is my post and let's let's see it contains the total sum of it so if i have to some of it then first i'm going to traverse for what i'm going to do first i will traverse for left then i'm going to for write then i can say that travels to the left part of it it will work for if we are if we don't do the competition then we the thing is that you you have a lot like in the first question also you are saying that you will do dp bitmask and the second question also you are saying that you will do some pre-computation but you need to just keep your mind away from those things and just think how you will traverse and have the access so see first thing is that you can can i say that you can have the outcome of the whole tree okay okay okay uh yeah that's the that's the point first we'll find the sum of the whole tree and then uh for each node we're gonna find for the left and right and we're gonna sum it and then we will subtract from this whole uh somewhere we have and then we will never take the port of it so that's the correct model yeah that's the thing that is what you will do see you will find the sum and then from whatever current node you are at you will try to break from it so you know the left sum of it you'll soon write some of it you know it's later so i was over pulling it yes like there was no use of uh like using that to the array and all those things so audience is clear with it basically what he will do what he's saying is he's saying that you can move to the first example now okay so what he's saying is he's saying that uh when he will be at two so he will like whatever like he will do a post-order reversal okay because post order traversal helps us to uh optimize in order of end time because if we know the left data we know the right data then we can do the calculations for the root so for every current node that he is at he is trying to break it so when he is at 2 then he's saying that for the left part of it he will uh calculate the sum first of all he'll call the in the left so he'll calculate the left side he'll calculate the right sum then the current root is also there suppose he has already calculated the whole sum of the tree by doing one traversal or something so what he's saying now is he's saying that now he knows that what is the current subtree sum rooted at a particular current root because he knows the left he knows the right so if he adds the current root data to it then he will get the whole subtree sum let's say he uh he knows that in for two in its left it is four for uh two in its right is it is five you can move back to the uh dock okay uh then what will happen uh after this basically he's saying that uh he will have the sum so sum will be what two plus four plus five that's some he will get and rest of the sums the rest of the somehow how we'll get so he was thinking to use some uh extra data uh like array or 2d matrix for it but you can do it by calculating the sum if you already know the sum then you do sum minus the all this data that the root data plus the left value plus uh plus the right value then you will get the other sum and every time you can keep on taking the product uh and whichever product is the maximum in that case you will you can return it correct that is what you are saying yeah yeah yeah okay so now uh you can stop sharing your screen so let's come to the part so after this mock interview like uh what do you think did you improve or did you learn something from the smok interview given the questions uh and the level uh the first important thing i learned was to actually do the question and to do in front of somebody's quadratic thing i generally used to do a question but i don't try to explain it to somebody so that's my first experience i'm explaining to somebody while doing my question and that's the tough part because uh to do also and to explain you need to maintain a communication also when you do uh you have to work on your brain also you have to think the problem also so that's a tough stuff you have to need to practice that i didn't practice a lot at all for that so yeah i was fumbling a little bit in in the middle of uh the whole interview so that's uh that's the thing that i need to improve i have to look upon it and i hope that you like the quality of the questions that question the question first question first question first question was pretty good question i think the first time i i i saw it i i thought that it can be done in use it can be done using db plus bitmaps but it was a greedy one it was a good ready one it was a great day it was observation based question it was asked the first question i was asked in amazon uh second one was asked in microsoft and adobe okay okay like yes sir the first question was from amazon okay second was uh second one was from microsoft and nano second one was easy that is why i have kept it in the end because i knew that you will be able to solve it uh now like but you have a lot of dp in mind every time so you can improve on that one don't think every question has dptp okay now another thing uh do you want a feedback from me yeah a little bit so see uh what i observed was that you were thinking in the right direction maybe sometimes you were just talking to yourself so don't do this like as you said like it's very difficult so whatever you were thinking just try it whatever you are thinking whatever you're thinking in your mind just put that uh put that like just think out loud nothing else and apart from this uh i know that your thinking capacity is good you were thinking dp but less bit mass maybe sometimes you were overthinking so don't do that as well try try to decompose if if c if you're going for a very big company let's say media.net or coordination or something then then that thought process is good but if you're going let's say for normal interviews only then don't over kill don't overthink the question don't do bit mask and don't think too much but that was great but you observed the pattern the first question that i liked in the second question also you were thinking good but as i put a constraint on you that you don't have to use the 2d matrix then you were a little bit uncomfortable but immediately you got to know that okay you can find the sound so overall it was a good interview and i hope that others also liked it it was a little bit on the harder harder side a little bit not much but it was like the first question was obviously it is not very easy when you get it for the first time so he was still a tanmay was still able to do it so thank you thank me for giving us your time and uh volunteering for this mock interview and i wish you all the best for the placement season uh so that was it for today everyone uh i hope that you like the level of the smock interview uh make sure to register for the mock interview you can find the link for it uh in the description of this video uh the google doc will be like the google form will be present and you can fill it if you want to give the mock interviews with us and another thing is make sure to like it if you uh if you found that this video was helpful thanks a lot everyone for joining and i'll see you in another mock interview uh until then it's good bye and take care everyone and make sure to hit the like button as well if you liked it bye everyone so it happens every week it happens two days somewhere so thank you everyone and bye take care