Live Mock DSA

hi and welcome to geek stories today we will be having live mock bsa round with coda quota digital now before i talk more about myself let yes sir good evening sir i am this is i'm currently pursuing vtech second year in computer science i'm i'm a competitive programmer i'm more interested in competitive programming i'm a specialist in core forces that means i'm roughly around six to seven percent coldest among top six to seven percent among all indians in gold courses and also i participate in coding competitions like code john kickstart and also recently i secured all india rank 397 in google cortana 2022 and also i did an internship in a startup called goyana where i worked as a full-stack developer i worked on a website i worked on a food delivery website where i built a login system for both user side and admin site i worked on javascript frameworks like leo.js and node.js see yeah sorry like mostly in competitive programming we see the range of end and range of based on that we calculate we we approach the solution but that's not the case in dsu so okay so can you just wait for a second i need to just check on the previous three look because this is okay so for the people who have already joined please give a quick question so now how to deal with suppose you are constantly giving contest each and every day you are not missing any of the contest online coding but still you are not getting a positive rating how could these become like even if you are not able to get positive rating today we will get on some other day but it's like we should uh keep efforts rather than keeping concentration on outcomes so okay yeah that is fine but still how to think that how to take it positively what do you think that yes this should be done if if today i would not able to solve uh three problems in a contest i should practice those three problems after the contest so that i will get i will gain some confidence and in next contest i might perform better okay so yeah so suppose i'm sorry you told about observing but still what do you think that what does the contribution in growth in computer programming which is done throughout it how much of solving hits like if you are not able to if you are able to solve a b problems we should absolve c and d problems and also if if a contestant we are not able to do we can we might able to do after the contest because there won't be any pressure after the contest so let's start now okay so all the guests so now the scenarios will be sent but i will be giving you two questions and then i would be helping you if you're not able to get hints or something suppose we are completely blank for the next one minute or 30 seconds i would keep giving you hands okay and then we will proceed accordingly okay so can you share this is perfectly visible and it is advised that you keep your notifications off so that we have your let's move forward with this so now i will be telling you the question and you can write the question in the form of comments in brief so okay we are given a value form and we need to find the number of ways to make change for concepts suppose we have a value of each s value since we yeah so i'm telling you so suppose we have given a value n okay total value and then we are also given coins with them like in india there are points with one rupee clear points with two rupees there are coins with five people okay in the same way you need to find the number of ways we can use those points to make the sum as m okay if we have an infinite supply of every form okay okay should we okay should we yeah so i will i would ask you a question after she is done with the question yeah you can just continue i'm just replying okay so i would so there are three values one two and three okay now there are four possible ways like we can use all one to build up the four we can use one one and then two to build up the four then we can use two and two to build up the four then we can use one and three to build up the four okay okay okay well if you want i can give you what this this is i said can you do any other test case yeah absolutely okay suppose n is equal to 10 and then m is equals the value of the coins are two five three and six okay because now you can just write this combination so that you would have a better view of this so the first combination can be that we have two five times so you can just write two into five so that we will know that this is the combination okay then we have two two times and three two times so 2 multiplied by 2 plus 3 multiplied by 2 okay then we have the third combination as 2 multiplied by 2 plus 6. then we have two three and five then we have five after a long time yeah after a long time gfg was not giving me no absolutely not they gave me a lot of opportunities but was busy that's another one so the first approach i'm getting is to check all the possibilities like first i will take one two and then first i will take one two and uh i will increment i or else i will take two twos and increment or else i will take three twos four twos and phi twos till uh some x into two is less than or equal to ten i will take uh that many number of twos and then i will proceed for every x i will proceed with i plus 1 and then first i will take 1 2 after that i will remain with eight after that i will take uh one five i will remain with three of i will remain with three after that i will take one three i will remind with zero so this is one possible case after that i will take zero twos so i will remain with 10 and then i will take one if i like that i will say all possibilities so that's the one approach next approach can be we can do dynamic programming with this okay so let me just ask you a few questions about this so suppose we want to have all the possibilities then we would check what all possibilities lead to the solution which is this is what we are talking about sf absolutely now in this possibilities we are given that we have an infinite supply of each coin okay so how would you deal with that suppose i took four so suppose we have two five three six suppose i took the first two and used it so in the next iteration what we would do first i will take two so after that i can take two or five or three or six anything i can take in the next step also i can take two or five or three or six anything like that until the number is less than z less than less than until the number is greater than zero we can do that okay well so let us first implement the root for solution because what are you willing to do you are willing to minimize this recursive solution or you would write the dp table what do you want to do i can do d piece here you can directly write this what do you think is fine if anything is fine then i think that let us first write the group source approach and then we optimize it so that everyone would have a better understanding how we went from this to this i think so okay okay okay okay so i will just provide you a function you don't need to write everything so i would just provide you a function in the private chat yeah private chat okay [Music] okay so everyone can try this question if i want to so i'm sending send the link in the chat are you talking about this culture or any convention no no no no i am not talking about this please i will take your name i'm just replying the church itself so how many of you are there in the chat itself can i have a quick plus one from everyone because i can see a lot of people but i can see very less people talking so at least the one in the chat so that i know that how many of you are recording or at all listening or just opened it by mistake okay there okay so let's see how many we finish there okay one more unit okay one more letters so what about others comment down your state or your city name anything it will be funny okay so we have wikipedia from usa we have it from karnataka okay great okay seems like i'm blessed okay let us know saying something in his language i don't know that language in gujarat okay okay people are going to do okay let's see it's not my language it's just yeah you've taken [Music] you yeah absolutely right so you are telling can you just maximize the text of your code [Music] yeah now it's fine so if you have used all the coins then only you are going down so if n is equals to zero that means you are now now able to get the complete n the sum we are returning one i think i missed the case okay what is the case itself when we don't take uh any of the index at all yeah absolutely okay so we have a month also from under produce okay yeah so we have the number itself if the number is greater than or equal to so if the number is less than then there is no possibility we can't take that if the sum is more then we would take it okay and then we would decrement this amount at the end we would just split them okay so i'm just sending you the code okay so yeah so what is the time complexity of this solution yeah what do you think is the company login base minimum element of the array minimum element okay so this is an equation so just see so this is the recursion so we have a thinking that yes the it might be the time complexity might be exponential might be exponential so how many decisions are we making just try to visualize the recursion flow just try to visualize recursion tree or decision tree whatever people call just try to see how many how many decisions are you decisions either we are taking either we are taking it or else we are not taking them okay so basically but we are taking multiple times we are taking it multiple times see suppose so we have the number of m suppose we have five so we are taking one one one one we are taking till the number itself suppose we we have two options so we first have the option that we are taking to decision the next option is that the value is very large enough that is why suppose even even one is given so we would subtract one again and again and again so it depends on two condition the first one is a decision second one is the given value because we are using an unlimited unlimited value so now whichever is greater that would be the time complexity itself but as we would have discussed this to a very large extent but as we need to do one more question and the optimization of this question is still so can you move forward with the optimization [Music] how about the opportunities i will optimize with the dynamic pro programming sir the state of the dynamic programming would be the remaining money left and the present index which we are in okay so how you how did you decide that this would be the first one what would be will you be array be required will 3d already be required how did you decide like that can see from the recursion itself the the things which are changing in the arguments are i and the end so that we can conclude that n and i would be the states of the tv so you are just calculating the range till which it can go and then you are having the maximum range and then you are making the arrow itself this is what you are doing yes yeah absolutely is tell me your approach so let's have a quick q a in the in the chat section tell me a topic which you think the idea the idea of the next question will be revolving around that data structure algorithm okay you can just send me your solution in whatsapp live so can we see the code yeah so let me just say so when you are going down if the value is not calculated then you are returned so if the value is already calculated we are returning that if the value is not calculated we are going down so this is the first condition itself if we have the time scholarly so if we are coming at the next part we can do that long answer number of ways you wrote a very elegant thing by the way your way of writing code is very attentive if you see the way of writing of mine it's very up into yourself so okay let's just move forward without wasting any more time because the next question is very interesting so let me just remove the dynamics and okay so i will start with taking the question so we are given a shorted dictionary of suppose uh yeah are you able to hear me listen now i can hear you okay yeah so we're going to okay so you are given a sorted dictionary for an alien language okay sorted dictionary of alien okay okay and there are n words and there are n words in the dictionary itself and then there are k starting alphabets of the standard division and k is starting alphabets of this standard dictionary like suppose we have a b c d so if k is equal to 2 then the value would be just a and b ok we won't have the whole word rather we would just have the first k alpha x okay now we need to find the order of characters in the indian language can give you any test case yeah absolutely absolutely so suppose we have five five uh words and then we are given the first four okay okay we need to find the first four letters so we are given as baa the first word is baa the next word is abcd the next word is a b c a the next word is c a b the next word is c a d e c a d cat and dog cat under c a d c a d okay let me just recheck the values so d a a a b c d v a a b c b a b c a okay we have a c a then we have c a b and c a b we have to find first four letters right there yeah how to find the first four numbers you need to find the first four levels so the ordering of the course four letters would be b d a and c the first alphabet would be b the next alphabet will be b the third alphabet would be a and the fourth alphabet would be c itself okay tell me the okay everyone start guessing the algorithm to solve this everyone stop guessing the algorithms so by seeing first two words we can say is we can say b is less than a b will be in front position than a in the order [Music] and then by saying second two words we can say d will be in the first fourth position then a by c third and fourth words we can say that a will be in the friend position then c and by seeing four and five we can say b will be in the friend position than b like the first different we have to check the first different character yeah [Music] and then we need i somehow feel like this is a trap problem like the directed graph b is directed to a and b is directed to a and again c is that a is directed to c and then b is directed to d so we have to find some harder okay okay word and second word we will find the first different letter and for those two letters we will make a directed edge and for every two adjacent words we will make a directed edge like that for that graph we will do a topological chart so let us first build the graph and then we will talk about how would you build a technology [Music] yeah absolutely right sorry yeah i have something what is her fourth courses profile quota what is your code courses username people for the person who heard it what do you think i also wanted to give mock interview yeah absolutely location mock interview what is the procedure from the scene you can just find the google chrome link attached in this video you can fill up the form underneath and the gigs for greek would be the leadership yeah so what do you think should i go bar should i have short hair should i have long rules oh this is looking good what do you think so we have and thanks a lot okay just click on the both arrows the text would automatically be maximum just click on the left pane the arrow that is given just on the left hand side of 20 just from the left hand side of line number 20 see the line number 20 go to line is when this yeah this yeah this is so just maximize the text size yeah absolutely this is absolutely perfect just go down a bit it is not equal to the first position when it is not equal to you are saying that yes this would come after me this is what you are trying to do okay so her approach of building the graph is suppose we have a b and the next letter is a c so we have a equal so we can't have a graph over this we can't have a dependency over this so we can see that we can the first two characters are ignored then we have b and c so we can say that b would come so c would come after b this is what she is doing because she is finding the first point where this is unequal so that she can move forward with the dependency now she has only used a size of 26 because it is already mentioned in the question that we would have only lower case english letters so she would just use the ascii code subtract the value of a where suppose even if the a has value 1000 then that b would have 1001 so we would just subtract the value where a would be having the value 0 we would be having the value 1. this is how she is building the graphics fair enough let's move forward so what is your approach to do topological sorting over this what is the algorithm i can do a dfs and at the end of the dfs function i can push the current element into the stack after completing of the dfs we will be having topological sort of the graph in the stack okay let's move forward with this okay so shall i code that for convenience i will keep this vector in global yeah keep them but you don't need to pass it again so by the way keeping that in global means that you see there is a term known as scope of a variable so let us understand what is scope of a variable scope of a variable seems that suppose i am a very nerd person i only know what is inside the home okay and if a person outside my home calls that is what happens with the variables and variables in c plus plus 2 if a variable is declared within the function then that variable would be available within the function that is if we are using 4 and i is equal to 0 then that i would be accessible only inside the formula okay so now keeping that in global means that it would be accessible in all the function so that we don't need to pass that same variable again and against the parameters okay so if you are having that call thing again and again if you are copying that so what you can do is you can just have a global and if you are using the range then a global variable of errors has a default value as zero but if it is within a function of something if it is not global or local then it would have that it might have or it would have garbage values this is what was the meaning of global variation so now what she has done is she has implemented a difference function so as dfs is a traversal technique so the return type would be boy now she is using a for each loop to iterate on all the neighbors of the current okay all the neighbors of the current alphabet now after doing all of those okay after doing all of those so it's not pushing the character itself okay in a step why in a stack to have the reverse okay said is it fine can you show me the code again yeah do your first thing i think it would make a little bit different so i think you have forgot something this is not a g problem i have to pop the k elements okay so you need the first thing is you need to return the sling you need to pop the k elements and add it to a string this is what you are saying but just see the topological ordering of it just review it once now or else what you can do is so work or else what you can do is you can move forward with the insertion string pop key elements inserted to a string then i would give you a test case and then you would get to know what wasn't okay so just pop the k elements and insert it i have to call dfs also sir okay after afterwards i have to find the first non-matching character thanks bro for providing this type of interview you know this type of interview is not provided for me please understand this this type of interview is provided by geek students and i'm just an interviewer and an intern as he so you should thank the team and some complete circuits [Music] okay not stealing the credits either [Music] okay okay so i will just give you the link just submit this so link is given in the private chat link is also given in the comments link is also given in comments link is also giving you a lecture you can access the link from both the places by the way you can do a screen share of the new tab that you have open so isn't it now no it is not sure you have only shared one tab i think so i think [Music] yeah so yeah nowadays yes so what do you think that kota is still missing what do you think or she is not missing anything she has quoted a perfectly correct solution what do you think or she's absolutely correct so can you kill me a hint like where is the error is that in the function of calculating graph or calculating the topological sort topology just try to think what is the difference between a graph and a tree how is dfs traversal different in grass community a better than you as this is directed graph we now need to check parent yes so can you tell the camera absolutely yeah whatever is comfortable yeah so the bfs function so it is visiting the same node again again so if you have a visited array and it would only visit the unvisited nodes then it would start the purpose you understood yeah you don't need to go that much yeah absolutely fine that's that's a small mistake he understood what i'm trying to convey i forgot i would visit it yeah it's absolutely fine it happens okay okay so now let me just remove the banner itself so you can just turn on this removing your screen you can just unshare the screen of yours okay fair enough so we have some comments for you okay so let's have the comment from lalit so yeah lalit has asked something in your language yeah so there's one more question from siddhi and after the contest i think there is a small mistake here on constructively suppose we are not able to solve the problem then what we do then we can see the editorial seeing attitude is totally fine but by seeing some editorials we can get idea for another problems which we can do later by practicing only so talking let's talk about so first let us talk about the first problem itself the first problem you are very you are very easily able to crack the logic itself so you can start so just your way of presentation so see you have a perfect understanding you have a perfect way of writing your code you have a flawless style of coding you have very very weightless syntactical errors because you have a competitive program and computer equipment tends to have less comparatively less than technical images as we all know but moving forward you can instead of pop into the most optimal solution you can start off with the brute force approach then you can explain the approach then if the interviewer is trying to have the optimization then you can call the optimization it is a kind of process you can't just show him two ways directly okay you need to go in a procedure if it doesn't procedure so it seems yeah you are first thinking about the brute force approach then optimizing to the next level then optimizing to the next level now the third problem you have not talking about the second problem the second problem your intuition the way you got the intuition the way you started building up the graph it was absolutely very relevant congratulations for that you have a kind of a flawless preparation okay so moving forward with that you will be able to track it but this is not a competitive programming that if you submit the solution one minute after you would be having less points than the other day yeah we i know we have we may have done that so i have been also creating programming we think that yes let us implement it first so that we would have more point to truth yeah i know that we have that but when you are giving an interview you can just calm your mind and then just implement slowly slowly and just rechecking what you are like and then what you can do is you can explain what you are writing so that the interviewer is not bored you can keep it in keep him engaged you can just tell him why you are writing this why you are initializing this variable what is the significance of this variables okay i can think so now the next thing which you can or might not change both is fine but from my point of view you can doing is you can have a more desperate descriptive variable with like left over like these are things you can use underscore to have them and then just recheck what you are just telling everything was fine but while implementing it first you just forgot the visited thing so you cracked the whole question but small things you are not able to get the ac okay so that was it from my side you are talking about the things which were which were noticeable and i think everyone has noticed you have a flawless preparation okay just keep up with that process trust the process you would be doing absolutely very good i can beg you to okay so now you have anything to ask me or from the audience itself anyone wants to ask anything so any questions for me quota [Music] so we will just wait for the next 30 seconds if we don't get anything so now everyone can just ask any one of us if you want to ask anything or else we would end this screen at 7 15 6. okay just a 30 minutes waiting time of the day [Music] okay well so that's it for today thank you and have a nice day thank you so much kota it was very lovely to interact with you i had a great time all the best for your channel thank you