Live Mock DSA | GeeksforGeeks

Key Takeaways

[Music] uh hi everyone welcome back to geeksforgeeks today we have another dsa mock interview and our guest for today is saurabh jan so i'll be interviewing him i'll be asking him two or three questions in a span of 45 minutes to 1 hour so let us quickly call our guest for today hi how are you hi yes [Music] i'm also fine can you can you please quickly introduce yourself to the audience yeah so my name is saurabjan and i am currently pursuing my b-tech from mit university noida i am currently in the pre-final final year and i have done couple of projects in the full stack development using python django in the backend and html css and the javascript in the front end i have done 400 plus questions on the gig focus and also my hobbies are to playing badminton and listening music that's all okay uh how excited are you for this interview are you excited or nervous yeah i'm excited for this interview okay so if if the audience can hear me so they can give us a plus one they can give us a plus one in the chat and make sure to give the video a like so that we have a head start uh so sorry uh one second i'll in the private chat i will be sharing a google doc link with you can you quickly share your screen first of all just down there you will see a option for sharing your screen all of you can give us a plus one if my voice is clearly audible and everything is fine so you can share your screen is my screen visible yeah now it's visible so once again in the private chat i'll share you the link so i've shared the google doc link with you in the private chat can you please open it yeah okay so let us start with the first problem for today so okay so the uh like the first problem says that uh you will be give like a celebrity basically a celebrity is a person who is known to all but does not know anyone at a party okay so there is a party there are suppose n people are there okay so a celebrity among those n people are celebrities a person who is known among all right everyone knows that celebrity but that celebrity does not know anyone okay and if you are at the party of friend people so find if there is a celebrity exist uh celebrity inside the party or not okay uh so what you'll be given for this is you'll be given a square matrix uh like n cross n matrix you'll be given uh which will be named as m and using this which will be used to represent the people at the party such that uh suppose that if there is a row right uh like let us look at the test case for that matter so suppose there is a row i comma j okay suppose there is a row i comma j so for that what will happen is for that what will happen is uh if i comma j if the row i comma j is equal to one so that means that the ith person knows the jth person okay like for example if you will see this uh the sample test case first which is of size three cross three so in this test case what you will observe is you can observe that in in the in the in this like cell 0 comma 1 if you will see 0 comma 1 is equal to 1 right matrix 0 comma 1 is equal to 1 so you can basically observe that 0 knows the person one okay this is what it indicates and similarly other another thing that has been given as one is like uh you will observe that uh two comma one is also given as one right the cell two comma one is one as well so that means that the uh that the person uh two knows the person one okay right is it clear so basically the person one is known so in this example if you will observe so the person one is known by the zeroth person uh person zero as well as the first person right and if you will see for the first person so the first uh so the first person is uh like if you will see the row for the first person so for the first person the row is zero zero zero zero right you can under you can see that column like the column is zero okay so that means that the first person does not know anyone and and there are two other people than the first person right there's a person zero and there's a person two so person two and person zero both of them know one but one does not know anyone right because for the for the row one every one every every column is zero right so that is why one is a celebration clear with this part are you clear with the test case yeah yeah yes now talking about the second test case so the second test case is zero one and one zero so in this case the answer would be minus one uh why it would be minus one the the reason for it being minus one is because uh the two people at the party both know each other right [Music] yeah okay uh those those are nice on your side can you uh just change okay just a second yes uh so in the audience is the audience clear with this question please tell me guys is this a question clear to everyone in the audience okay so sorrow statement is clear uh how many of you are clear with with this problem statement in the audience please tell me is everyone clear all of you can give us a plus one in the chat if you are clear with the problem statement basically what will happen you will be given you will be given a celebrity you will be uh you you will be given n people and you'll be you'll be asked like you have to do what you have to check where out of these n peoples that whether there exist a celebrity or not so if the celebrity the condition for celebrity is that please explain some examples so you can look at the first test case for that matter okay so uh what do you think so how can you approach it so uh i have a question in this question like like can to celebrity be possible in one test cases like if i have two rows with zero zero zeros so that will be like possible test case or not like i think about it think about it if i can celebrities be possible for a problem [Music] okay so we have a square we have okay so we have three of three so zero person knows anyone and and one person is one okay there is only one celebrity yeah like uh if we have all three rows equal to zero in that grid particular okay there will be mi always be zero okay m i one okay so that will be like combination so uh what approach i am thinking of this like we have to just find zero zero zero in a row particular like there is no one in that like in the question is given that like we have to find a particular celebrity like which is not known to everyone like people are knowing to the celebrity but celebrity not knowing through that people like here in the first test cases zero and like first person no that not known that itself but first person know the second then starts from zero okay let's say indexing start from zero so zero people knows the first person okay so and also zero people does not know the second people but uh first people like not known to zero not on to itself and not known to the second people so this will be our celebrity so what i am thinking right now can we just uh find a row where we have the count of one is equals to zero like we iterate from the rows and we then counted that like yeah we have if we have count of one is equal to zero then it would be a like possibility that will be a celebrity uh so can you tell me can you tell me will there be just one celebrity in the uh in a given uh in a given relationship or uh they can be moved i think a celebrity [Music] like and there might be a possibility i think there will be like one more celebrity uh what will happen let's suppose uh we will take this test cases zero comma zero zero one and one zero okay so if i make all rows equals to zero okay let's just make i think let's suppose we make the first people and first people is also not known to the zero people so that we might be a case of two celebrity i think did you read the problem carefully what is the condition for being a celebrator um who is known to all but uh does not know anybody okay known to all okay that's i think i am missing means that question is not okay every person is not if every person is knowing to that okay so that might be not like not valid for this question i think so what approach i am thinking of this person okay so they might be like if we have count of one equals two people yeah if like we can do one thing here like we can traverse through like a column by column okay like from this zero zero and zero we can check if the count of 1 is like but n equals to n minus you have not answered me this thing uh that whether they can exist one or more more than one celebrity can exist or not [Music] here because if they're too celebrity like so that condition not faithful like the every person accept the celebrity known to that celebrity so i think their tools and celebrity might not be possible for this question uh basically they will be they'll be just one either there will be a one celebrity or there will be no celebrities at all okay how can you have how can you have two celebrities because if you if you have two celebrities though so that means there will be two rows that will be zero and that is not possible yeah yeah so for this question like i'm thinking zero zero and zero so like if we have like a no the first person is not knowing to everyone and also like this first version is not known to everyone but the last person known to first second and like this number so i think that will be not passing this question because there is a question condition like the uh all peoples are known to celebrate if i will assume this will be a celebrity but this first person didn't know the zeroth person so i think there will be only one celebrity there will be no valuability okay so this question is clear how would you approach it like can you think of some solution for it if you have to if you have been given this matrix how can you find the solution um the approach i am thinking of like i can traverse from the columns like g0 0 and 0 okay if i get the count of one is equals to n minus one um yeah n minus one then i will make sure that yeah this will be a celebrity okay but in this test case the count of one is equals to n minus one but there's also one thing okay so in that case there will be no solubility so i think from checking the column wise i can do that uh like uh but your solution like approach is not that clear okay let me just take it as case okay what i am thinking for approaching let's suppose we have this task is okay so in this test case n is equals to the three above the same test case so what i am doing i just uh using the uh like two loops okay first loop for i treating through all columns i will iterate from all columns and the second loop jj will iterate from like this zero zero and zero okay i'm iterating through column wise okay so what i will do i will count the number of one in the column okay let's suppose uh here the count of one is equals to zero okay so that will be not not possibility like this will be a celebrity okay so that this is clear that zeroth person is not a celebrity okay now comes to this column one zero and one okay so uh here the count of one is two which is equals to n minus 1 minus 1 so we can like have a possibility that this first person might have like might be a celebrity okay so now going to this last person second person so here again the count of one is equals to zero so we show that this will be a celebrity so this is i'm thinking okay so can you write the code for it um yeah so let's see one second in the private chat like in the chat i'll be sharing with you a link one second so in the chat i've shared with you a link so you can open it can you just zoom in a bit m so what i will do i will check in the columns okay so that's what we have um possibilities okay this one is so back to the false so if um equals to one minus one not flat um like if it exists then you have to return that person otherwise you have to written minus one okay i have to okay okay what is the time complexity of your code it will be like n square because i'm using two loops so this will use the time complexity of n and also this will give that long complexity of n so this will be n square that was okay like i think it will be taken from this thing so can i submit this code uh you can try to compile it okay try to convert it it is giving [Music] it fails okay can you think where your approach is failing because uh there are two concerns with your approach right first of all it's it's not correct yeah although it's order of pen square still it is not correct and the second thing is second thing is it's taking a lot of time it's taking order 10 square time yeah so for making correct water but um onto that celebrity [Music] also you can just move that okay so this is ongoing the person knocks to the both elements okay let's think i can do it like firstly i will find like there is any row of 0 0 and 0 okay so that i am here i am 0 0 0 so now then i will check the column okay so if the uh column count of one is equals to that like n minus one then we can declare that celebrity then this is a celebrity and how much time will that take um for a more count square for this and [Music] i think for searching this particular row like if we want to search that row is equals to count is equal to one is equals to zero i think that will be like m square again yeah we can try to implement it let's see what happens okay so for the improvement what we can i can see a lot of people are watching us so all of you can make uh sure to hit the like button guys and comment on a plus one okay for the optimization like i don't able to think that like what kind of optimization we can do to make it n square to n you can till now i think i'm able to like think of n square approach for this question okay we can get this zero zero zero no i am not able to think that any complexity okay so yeah so can you just implement this order from square if you can that you will see yeah yeah again all right so i have to just check that [Music] um it goes to one um this equals to n minus one then it will return i yeah it's accepting it is it is accepted but what is the time complexity of your approach like like if i include this amp dot com because it will take off and complexity and also this will takes off and complexity then it will be n square okay so so can you think of optimizing it can you think like how how there's some way that you can reduce this much number of comparisons because you are currently checking for every uh row in the brute force manner yeah yeah so um without checking like if what is the question that if no i i think aren't able to find that off and complexity for this question because like we have to find the zero zero and zero sequence no i think i am not able to like find the off and complexity uh i'll give you a hint like can you think like see they they can be uh various ways to optimize it uh but like can you think like what element like see they see ultimately what you want is you want to check whether there exists a cerebrality or not right so if you want to check for that yeah so i'll give you a hint that if you keep on comparing two people let's let's say what you have is let's say you have let's say you have zero like for the first test case let's say you have person zero one and two right so if you if you keep on comparing two people at a time let's say you come let's say you compare zero and one so if zero knows one okay so will zero be a celebrity if because it's known for that person okay and so in that case what you will do is maybe you will compare further one and two uh suppose uh suppose what happens is suppose one uh suppose one uh knows uh let's say one knows two then what will have like uh what will happen like suppose one does not know two so in that case what will you do so zero could not be a celebrity right okay okay that thing like uh you want to tell like we have to check only the end times like if zero knows to one okay we have to check only these indexes if zero knows to one then zero will not be like a celebrity okay then we have to check uh one nose to two or not if one doesn't know to might be a celebrity yeah because because they can be other scenarios as well so can you think now anything about it now okay let me just try [Music] [Music] um [Music] [Music] make it here uh i can think of that like we just uh like uh i trade through all the people it's like zero one and two and then we check uh if zero knows to one let's suppose if zero knows to one then zero might not be like zero not have solubility okay one might be a celebrity then we have to check one nose two zero like the reverse of that index one knows to zero if this both condition will be true then it will be clear that one and zero not a solubility okay so in that case like zero and one are not resellability but we have again just look back for that if you want to use like if you want to for two like zero nose two two or one nose two two for no i wouldn't able to get that simple thing but are you able to understand that using are you able to understand the process that by using this kind of a comparison you would be able to reduce the number of comparisons that you were earlier doing now yeah yeah we can reduce the number of comparison like we can just have to check some comparisons like zero one and one zero so we can reduce the number of comparison i think uh no problem uh what happened no problem like this from like maybe you're not able to come up with the optimized approach but let's move to the next problem because we are running out of time so can you just quickly scroll down [Music] yeah yeah just open it on the new page like one second yeah once again just here so now i think it must be visible to the audience as well right yeah so yeah uh let us do this one so you have some idea about trees right yeah yeah yes okay so let's quickly read this problem as well and see what it says so you have idea about binary trees what are binary trees okay yeah so and what is the binary search tree binary search tree is like a sorting thing like uh in like we have a parent and on the left side we always the smaller element than the parent and on the right side we have always greater element than the parent okay so let's read this problem up so the problem says that you will be you will be given what you will be given this uh you will be given uh you will be given a binary tree root okay so you'll be given a root of the binary tree and what you have to do is you have to return the maximum sum of all the keys of any subtree which is also which is also a binary search tree okay uh does it make some sense basically i'll give you the root of a piney tree and what you have to do is you have to return the sum of all the elements all the elements in a subtree which is a binary search tree yeah okay if you will see this here uh if i give you this example so the tree is like one four two four so can you see like uh can you see for this subtree that is rooted at four like four two and four four which is having a child two and another child four uh which is having the left child is two and right child is four so is it a minor surgery okay okay is it a buy search tree four i think four two and four no four two and four not because four is equals to four that right element because because the uh like what is the what is the condition is that if we have only like yeah the left condition will be like always smaller element and in the right we have always greater elements than the parent okay so you look at the you look at the subtree which is rooted at five so for five you have a left child is four and the right child is six correct yeah it is for the subtree rooted at five it is having the left child is four and right child is six so it is a by uh it is a binary search tree all of you can like in the audience also they can give us a plus one if they can see this okay now is there another like is there any other subtree yes so if you see for three so can i say that the subtree that is starting from three uh rooted at three it is also a binary search tree because every root satisfies that condition i think because if you see three four so if three is the pattern then its left shell is two which is less than it and its right child is five which is uh which is greater than it so fine with that and you can see what you can see for five for five you can see uh that five we have already seen right five is uh abiding by the conditions and the leaf will always be a bunny search tree here right uh individual leaves will always be so we can say that this particular component that is there right this particular component which is rooted at three so three two five four and six all these uh nodes all these leaf are in a component which is a final search tree correct finest industry yeah okay so so what you have to do in this problem is you you have to do what you have to like see you will be given a you will be given a tree okay and what what the constraint is that the constraint uh the thing is that when you are given this tree so which uh which is root which is rooted at a particular root we are given this minus h3 so your task is to find the maximum there can be many binary search trees inside this tree right so what you have to do is you have to return the sum of the maximum right you have to you have to return the sum of the maximum by search tree okay you have to take the sum of all the nodes of that by particular minus hp and out of those out of those answers you have to return the maximum sum so you will be taking the sum of the nodes which which are in which are part of binary search tree and after taking the sum whichever sum is possible for a particular binary search tree that you have to return any doubts in this question till now i think i have no doubts in the question okay can you move down to the second pesky system uh you can directly move down to the second diagram okay yeah this is scroll down oh yeah so let's see the sigma this one so is this a binary switch three like four four you have you have three right so that is fine uh if you are rooted at four suppose you suppose you check that okay at four the my search tree like the the left child is three which is lesser than it but for three is that the condition is the condition for my surgery uh complete no no because it's not a binary search yeah yeah like see four starting from four if the root is four then it is not a binary search tree if the root suppose if the root i say is three then also it is not a binary search tree correct yeah but but the leaf node individually can be said to be a binary surgery right because are you clear with this yeah yeah i'm clear with this i'm clear with this so the ind so the individual leaf node one is a binary search tree in itself and the individual node 2 is a binary search tree in itself so the maximum sum is what maximum summary is the two okay so these kind of cases you can encounter and they can be they can be many uh possible scenarios and combinations so are you clear with the question okay yeah i'm clear with the question so how would you approach it yeah okay i have a question like uh let's suppose we have a test case in that in this way so in the left we have like suppose this 546 is not a binary substring less for the case okay yeah like what do you think like what you are saying you are saying is what you are saying is that suppose the rooted at five uh it is not behaving like a binary search tree it is not behaving according to the property so will you will you will you count that segment uh will you consider that segment as a bst what do you think like if it is not a behaving like then i think that will not consider in that segment you will not consider it as a bst so it will not take itself yeah okay i think that i'm clear with this just a second so like uh any approach comes to your mind like how you can do it any brute force approach or any sort of approach that comes to your mind so like surely we use the recursion here and i will go like first one by one i will go for the left as well and the right as well okay let's suppose we go to the left part in this test case so i will go to that proper left to here okay i always consider to like always consider the leaf nodes okay or we can stop that uh like i can also traverse till this four and check like if two like i will take the maximum from the both like firstly i will uh check this bind this subtree is a binary tree or not okay if it is a binary tree like it is a binary the whole sum four plus four and like two okay if it is a binary search tree but uh let's suppose here it is given that uh this is not a binary search tree then what i will do i will just take out the maximum from here okay so the maximum from here like let's suppose this value will be four so i will take out this four and go to this root and then again traverse for this right part okay so now i will stop here at the five node then i will consider this five four and six then i will check this is a by bst or not if this if this is a bst then i will sum up and compare with this four okay that maximum i will store it in a sum variable so it will be sum is equals to four so i will take out the maximum so five plus six eleven and four fifteen so the maximum will be taken eleven okay then i will come to this three okay so uh then i will see okay this will be parent uh so we have to include that sum there okay but you will check for the bst condition right from will you check for the bst condition yeah yeah also for this con first i will check the bst that if it will be a bst then uh if it will be a bst [Music] like the concern is to check for the bst condition how will you keep on like how will you always keep a track that whether the current uh sum that you're considering is a bst or not like uh we can use this like a simple formula for checking the trees the bst or not for the maximum and the minimum volume defining like uh from here when i will go here i will define the uh like maximum value will be one okay and minimum value will be infinite okay so as i move down here so i will check that it is not a bst okay so i again like uh like redesign the condition of maximum and minimum i will make a uh like maximum value i can get in this tree will be four and the minimum will be infinite okay so like as if we can take this this like this tree so what i will do i will do here like maximum value i can get a three but in finite like minimum value i can get infinite for the left part okay so the two is lying in the both condition okay and for the right part what i will do i will take minimum value will be three and maximum value will be infinite so this 5 is also satisfying that max and min condition so this way we can check the bst part how much time will you check take to check for let's say every node or for checking the bst no no uh like while we traversing through the like through the substrate we will can we can we can check that condition side by side parallely okay so how much overall time will you take to check whether uh for like for every node you will try to check that it is a bst or not it is able to make a bs not rooted at that particular node so how much overall time would you take okay so it will be like the number of nodes in that tree okay three and three eight and six seven eight nine okay then we have nine notes so it will take like off that particular end okay so n will be the number of notes in the tree so that much time i think i will take two traverse through the each nodes and for the checking the bst i think so what condition would you write let's say you have to check you have to check whether like let's say you have to check whether one is a bst or not from rooted at one whether you are able to make a bs or not so what would you do okay so what i will do i will declare a max variable as a infinite okay and also i'm also a mean variable is equals to minus infinite okay so i will check this like then i will check this one lies in this condition or not if this will lie in these both condition like one is mean is like greater than max okay this is the condition we will check for the one okay now what we will do we will modify the volume for the left meaning much like the maximum value we can get in that particular bsc like let's suppose we maximum value here maximum value will be like infinite uh in this particular one node okay in if we have this bsc let's suppose this will be bst like here we have value for this particular first node will be four and here will be two and here three and one okay so in the particular bst in this particular sub tree bsd we can get maximum value to this four okay not equal to that four but less than this four okay and minimum value we can get like minus infinity okay so uh then we again check this node okay so we have this is equals to two so now we will again again like redesign the maximum condition and mean max minimum will be always infinite and maximum will be equals to 2 okay for the left part and for the right part minimum will be like two and mx term will be in finite for this so this is the particular like this is the simple condition for checking the bst if you want to check that particular tree is a bst or not yeah let's see let's like i'm not clear with this approach okay okay just how are you updating your minimum and maximum and everything i think you want to say something else okay just a second uh in the audience if you are i can see a 100 plus people are watching us so if you like the quality of the questions that we took today so all of you can give us a thumbs up like uh like plus one in the chat and you can like the video as well guys okay so that we can take such more mock interviews on gfg uh meantime is uh trying to come up with an approach you can give us a plus one in the chat and make sure to hit the like button guys uh this is a request you can hit the like button for the video if you have uh like the problems that we took today okay and like uh we have to take the sum only for the bst how are you keeping a track of this how are you keeping a track of the sum all these things you skipped yeah the sum of all those things uh yes yeah okay i was like thinking of like storing in a variable but this will create a problem for in the back training like if you want to check for this in another way you can like [Music] and if this is uh okay sort of uh almost time is out so i'll tell you the approach what would have been approached so basically see the first thing that you could have done in this problem is you could have said that starting from a particular node right starting from a particular node you could go down and keep on a check like you can check for every node whether it is it is forming a bst or not but if you check for every node so for one node you have to traverse the complete tree so it would take order of end time yeah or another node if you have to order fan time for that as well so if you do it for all the notes it would take all the time square time and you can keep on finding the sum but that would be inefficient because it would be order of n square right so the better approach for doing this kind of a problem is that what you can check is like if you if you want to check right so for that you need to keep a track of the max uh maximum element at the left and the minimum two at the right so if my maximum element at the left uh if the maximum element in the left is lesser than the value at the root okay suppose that the current rule if the maximum element in my left sub tree is lesser than me uh and the minimum element is greater than me then i'll say that it is performing a bst this is this is one optimization that you could have tried but i so like i have a question in that approach like we will uh check for this particular node five four and six okay yeah we can check that this particular five four six is a bst or not okay that but what will happen like if we come out to this three you if we want to check that three two five three five yeah yeah so see five five four and six is a bst you know that okay yeah and now now the answer depends on what now now the situation depends on three okay so in the left subtree of three which is the maximum value it is two which is lesser than it and in the right subtree of uh three which is the minimum value it is nothing but what minimum value is four which is greater than yeah it's greater than that's why it's a bst basically the concept is that first of all you'll hit the leaf nodes and from the while you are moving up they'll keep on building the answer one by one okay this was the approach but i think you were not able to come up with this approach but no issues for that and talking about the celebrity problem so you were able to tell about the brute force approach and you were able to code it as well but after some failures and i think you could have come up with the uh optimal approach for both the problems right uh so that was good like but i think i think that there is something you need to you need to build a bit of more logic for uh cracking the uh optimal approaches for the problem right although you have solved a lot of problems but maybe there is something that you are lagging because you were not able to maybe implement the brute force approach for the celebrity problem so i will say that some like some things are lagging so i hope that you learn something from it uh was it helpful for you yes okay like really helpful for like experience for me okay so uh thanks a lot saurabh for joining us for today i hope uh that you enjoyed a lot you learned a lot uh now i'll talk with the audience so thank you zoro uh so i hope that everyone each and every one of you liked the questions that we discussed the first problem was celebrity celebrity problem and the second one was uh largest largest sum bst in a binary tree so i hope if in case if you did like so all of you can make sure to hit the like button for this video and give us a plus one in the chat if you did like it i'm just uh here for 30 seconds more and then we'll end this stream so before we end all of you can give us a plus one in the chat if it was helpful or you can write helpful in the chat if this video was kind of helpful to you if this mock interview you think was helpful to you and uh apart from this uh what you can do is you can hit the like button as well so thanks a lot everyone and we'll see you in another another mock interview till then happy coding and take care