Live Mock DSA | GeeksforGeeks

Key Takeaways

[Music] [Applause] [Music] um hi everyone welcome back to geeksforgeeks uh this is me yes devi so today we have another dsa mock interview our guest for today is jagrit so we'll be interviewing him for this dsa round i'll be asking him two or three questions in a span of 45 minutes to one hour so all of you can just quickly give me a plus one in the chat and hit the like button if my voice is clearly audible to all of you so that we can get started with the video so just quickly hit the like button guys and give me a plus one if my voice is clearly audible and there is no problem with that so that i can call our guest for today is it fine great so now let me call jagrit for the interview hi jagrit can you please introduce yourself uh hello everyone my name is jagged rasgupta i'm currently in my final year b tech at i am kolkata so i've been doing competitive recording for a while now and i'm rated five strong code shift as well as qualified for icbs regionals as last last year but recently i moved on to android and back-end development so yeah that's about myself okay so uh are you excited for this interview yeah definitely uh how much you rate yourself uh on a scale of 10 in dsa it's about eight okay so uh one second in the private chat i will share with you a google doc link just give me a second okay so you can see in the private chat uh i have just pasted a google doc link with you uh can you just open it quickly and share your screen at the same time sure [Music] uh you will find uh you will find the link like you will find the share option here fine is it visible uh yeah perfect it's visible okay i hope that it's visible to the audience as well so let us start with the first problem itself so uh the first problem says that you will be you like can you just uh like there's some uh there's some background right so can you just close the windows if it is possible uh which one okay okay uh he will be joining in some time there was some noise issues so that's why he's trying to join the deal uh till then all of you can tell me how much excited you are for this interview guys okay uh yeah degree can you share your screen so uh the first problem that we'll be doing uh so i'll give you an array okay i'll give you an array uh which will be an integer array it will consist of n different elements and the ith element will denote the number of number of characters in one word okay so i yet element of the array like every like every element of the array will denote the length of the world okay so ith element will denote the length of the ith word and i will give you a limit k okay the limit k will be the number of characters that you can put in one line the limit k is the number of characters that you can put in one line so like you must like have you ever heard about word break have you yeah i have heard what happens with what happens with word break is if let's say you are typing something on let's say something like google docs or let's say something like microsoft word so if you type something and that uh if the spaces that that are there if the number of characters are located for that particular line if you exceed it so it does not happen that uh you write some of the like a particular word is there a larger word is there so you do not write some characters on the upper and the sub-characters on the next line you do not do that okay uh the complete word comes in the next line right you must have observed this thing so this is what i'm saying that if i allocate k character so every the it is important to notice that every uh character that like every word that will be given to you it will be of unless its length will be less than equal to k only okay there will be no one whose length is greater than k because i want to accommodate each of the words okay so what what your task is to your task is to minimize the cost like assume like uh you have to assume that the length of each word is smaller than the line wind line width so when the line breaks uh are inserted so if if let's say you place a particular ith word okay if let's say you place an a word which is of length three so after that you must be having some spaces okay so after you place it so you will take one space correct you will take one space and then you will try to place the next one so what you have to tell us like let's let me give you an example for this let's say uh can you just scroll down a bit where i'm writing the example yeah so what i'm saying is let's let's say i give you k is equal to six okay so this means that i will give you six spaces right six blank spaces like uh if uh if you will see here so i will give you six spaces let's say okay so one two three four five and six okay i'll give you six spaces and what i will give you is i will give you the words so let's say uh i give you a word of length three then i give you like let's see the example example for that case once again uh if i give you the words like three two two and five okay g two two and five so first of all i'll give you a word of length three then i'll give you another word which is of length two then i'll give you another word which is of length two then i'll give you another word like uh first of all length of word three then two then two and then five so k is equal to six so notice every in every line there are six words six spaces so let's say the first word was let's say gfg okay so there are six spaces in this line so initially let's say you put gfg here okay if you if you put d f and d here okay suppose the md was there and you have put gfg after that you still have how many spaces remaining three three spaces are remaining okay so can you put the next word let's say the next word is of length two so can you put the next word yeah we can just like you can right you you can right if let's say it was cp or something so you can or maybe if you want you don't so if you don't put let's say you don't put let's say you put next word let's say cp or something in the next line uh so in that case three spaces are wasted okay three services are wasted so the cost for that would be nine okay you're getting this one uh nine sorry let me just uh so basically the number of uh can you like uh formalize the cost is calculated again uh i'm saying that if if you waste some of the uh some of the uh words some of these spaces in the previous line if you have waste like if you put cp in the next line that means you have wasted some of these spaces in that case it would be three three okay okay so basically the square of the number of spaces tested yes so if you see if you see for this word let's say if i wrote tp here only so yes will you write will you write cp and decent to gfg no no you will take one space yes or no otherwise you will not be able to differentiate between the words so that means total six suppose i asked you for six spaces so one space you will take more why because you want to keep a gap between the characters then you will have cp okay now is there any space left in this line no no because three characters you have used there one space and then two characters for c and then p so yeah i can say that no space is left so zero into zero will be nothing but zero here okay this can be the case let's say the next word two is it so what i could do with 2 is let's say if it was 2 so let's say it was something like uh let's say if it was go something like go okay so i can choose like if i put go so now i i'll have four more spaces so if i have four more spaces so can i put the word coder down there no no why no because though because so i just have four spaces remaining so i cannot put it okay basically i have i can see four spaces but actually the number of working spaces for me are nothing but three now i'll take one more space as well okay yeah so that means suppose that if i waste this uh thing so how much will the cost be can you tell me 16. uh four into four right so we are also calculating the space which we wanted to take into the number of spaces right no no like here if you if i'll see on the upper side so if you take a space uh to differentiate between two connections we're not including that you're not including that okay okay got it uh then if you see uh let's say if i put coder okay so you will see that okay one space is left after coder yeah right because the five the word with the length five was codal so if if there is if there is still a space remaining okay if there is still a space remaining [Music] so i think we are going to take uh like there's a lot of noise from your end sorry i'm not sure whether you have closed the windows or not is it fine now yeah seems fine now okay so uh you see uh after this if i have the word coder okay so you will say that okay now one into one will be there cost uh no because we are not wasting any spaces since that space would be like if this is the last word then you are not wasting any space so the after placing the last word uh you will have three rows into zero cos no matter how many spaces are left in the last line okay so for this i can see that the cos that i'm paying is 16 but they can be a better combination for that okay the better combination is that uh one like if i will tell you about the better combination so what i could have did done is there can be many combinations that i can have but suppose what i could have done is let's say i have a space here space here space here okay so that would be three into three correct if i do not miss the word with length 2 there let's say i put cp here and then i take one space more and after that let us say that i put the word go okay which is of length 2 after that one more space so that means total one space is just wasted in this line yes or no right it will be one into one so after that i will place quarter and the moment i place quarters so one space is left but for the last line knows like after placing the last word i will not count the number of spaces left because my words are place okay so actually there will be no spaces so zero into zero so the total cost comes out to be about 10. correct yeah okay and this is the minimum for this for they can be many permutations and combinations right you can understand either you keep it in the same line or next time they can be many so what you have to do is you have to minimize the cost understood the question got it so one thing can we rearrange the words no you have to like no you cannot rearrange the words you have to take the words in their order only in the order in which they are given in the array so basically you will not be given the words as well i have just taken the words for your ex for explaining you you will just be given the length of the words okay got it uh so is there any time constraint uh given in the question you can you can think of any approach for now then we can try to optimize it okay all right if the audience is also clear then they can hit the like button and they can give us a quick plus one in the chat yeah go ahead so i'm writing down here uh so let's say we have some words like abc and a word a b and over abc so and let's say we have uh the space length of five let's see so we can uh put abcd here for one and one space will be left so can we do like this can we omit the entire line like this and move on to the next line itself although that won't be optimal can we do that you you can do that but that's that doesn't seem to be optimal you can if you want you can do i'm just exploring options okay got it so another thing we can do is we have to put abcd since that would be the most optimal approach and there's one space left so we put a b in the next line now i don't think this space would be counted in the cost because we have to use one space anyways but but don't you think you have you have left one space right for that particular line uh this will be counted yeah that will also be counted also if i had another word something like this a b here then it won't be counted no it won't be counted so uh mid space would only be counted if it has a word after that right mid space if if there are two correct two different words and you want to differentiate them so you are taking one space so that will not be considered but after placing after after placing if you move to the next line then whatever spaces are left in the previous line they will be counted for sure okay so basically we can put one space and say that this space would be counted in the cost only if there is a word after that in the current line we can uh formulate this and if there is no word after that then we don't count the spaces so the most brute force approach would be to like first place the the first word in the first line like abcd here and then we have to check we can can we put the next word here or not if we can then we put or we don't okay so let's say here it was five but let's say we have something like six okay so we make a choice here we either place abcd here the a b here or we don't there are two conditions you don't then you are wasting three spaces and that's fine then we move on to the next condition now here our counter is here now we put abc here and since the word is complete there is only one space there is no space wasted here and if we put abcd here in the next uh example sorry then there are three spaces listed so the most optimal approach would be this so we basically explore all the options like putting the word either after putting each word we check if we can place the next word or not if we can then we put the next word or move on to the next line now if there is a suppose abcd here you can put the next word right a b now if we can put the next word with uh like move it in two different directions in one case we put a b here in one case we don't and then we'll recursively uh put the search it again using the next word so that's the most work for solution uh so you're thinking about a greedy solution uh no the greedy would be that if we can put the next word then we will put but in this case i am exploring all the options even if we can put the next word i am going to uh like explore a case where we don't put this uh a b here for example here we can put a b right in greedy what would you do in greedy we would put a b and move on to the next slide but here we would uh one case we would put a b and one case we won't put any like this got it so this approach doesn't seem to be the most optimal one so what we can do is we can use dynamic program to uh like optimize this for example if we have a sub problem like suppose we begin a word a b here doesn't matter example here suppose we have you can take the example that i have taken gfg cpu suppose in the third line i don't know what does upper two lens have but suppose in the third line we go with cp okay cp and then the first one we have to put a cp then so uh no i'm not cp suppose we have go here okay suppose the first word we put in the third line is go and let's say second line and first line we don't know what it is for now go now the number of spaces remaining is space space space is remaining and suppose we explore this condition sorry oh so four spaces right four spaces so this is one uh like suppose there's a situation we come across and we explode this okay now what are the two upper two cases that can be we can either put cp here and go for two four spaces here and we can put gfg on the top and have three spaces this is one condition but you can also put cp down here and entirely skip the second line both these conditions will result in this sub problem right so we are seeing we are having a optimal uh approach where we can like use this sub problem again to compute this so we don't have to like again and again compute this third line where we put go in the first the word so that way we can optimize the approach using dynamic programming okay so would you like to write the code for it uh sure okay one second so what i will do is give me a second if you will look at the private chat so i've just shared the problem link can you open the editor for the problem link you can quickly sign in so this is you can do the full screen before that maybe you can set the id as dark so that everyone can pos uh clearly see that so you can send it to uh set it to dracula into dragula so that no one has any complaints regarding the visibility uh themes you can go to the themes part yeah and just just mark it as dracula so that it's visible to others again should i increase the font size so it's more visible no you can just uh do the full screen okay just let me just check the examples once uh got it okay so we are given an integer of numbers and uh a vector of integers and decay like you will be given the length of the integers like a length of every uh word not the exact word uh the words we are taking just for example okay so let's give you the number of characters that you can place in a particular line yeah go ahead so let's define one variable that's word index and it would uh there's some echo coming can you fix that oh there's no echo from my side but still a new person yeah it's fine now so let's say the first index is zero so let's take an example here let's so right now suppose we have the index here for index let's get into wr so we're going to increment this one by one and check for each word and we're also going to keep a count of the line number which you're currently on line number and that's also currently zero so let's say we have a function like calculate so we pass in the current order which you want to input and the line number and also the current like uh which character current is so let's say it's k and then let's say it's at character number uh yeah let's say it's at a character c c index at the index zero so initially it's at the first of the line and we're not also going to pass it here index and also deposit nums and k and this this will uh return us the optimal approach which we want for this answer question let's store it an answer and we can just return this now let's write this calculate function uh okay so basically what you have done is you have uh you have the starting you are starting from the zeroth word correct so there is no echo problem right i hope that you are starting from the zeroth word as we said you have to take this sequence according to which the words are given the first of all the first word second word and like that you have to place them like that then uh you are also on the line number uh i don't know why you have taken this maybe your line number is currently the current yeah but do you think that's important for you um let's say if it feels redundant i'll remove that later okay but now i just like for clarity i've taken it and you have the c end is you have taken for ah the character it currently is on the current line so for for now it's on the first character right so now it moves suppose we have it in the include a word which is of catalan three so it will move on to zero plus three three like that okay so the first variable is word index let's read this line number guys meanwhile jagrit is coding so all of you can hit the like button okay make sure to hit the like button if you like the question and you can tell us like your approaches as well i'm looking at the comments some people have suggested a few things uh like vivek is whatever we make has suggested that is also good and congratulations to ankit as well but make sure to hit the like button guys okay so let's say we do a possibly recursive function correct yeah yeah so it doesn't matter like uh one thing i forgot to clarify like even if you achieve the minimal cost using suppose hundred lines like it would be considered minimal if we even write it uh suppose we have a solution which uses 100 lines but generates a cost of let's say 5 and we have a solution which has 50 lines but generates a cost of 10 so in this case we consider this first one right okay uh i'm asking like uh is it the right approach like uh suppose we have uh two solutions based on this current let's say the first solution uses hundred lines and has a cost of five okay and the second solution has 50 lines and has a cost of 10. so we would include the first uh answer right you have to minimize the cost basically you have to minimize the cost got it got it so then we don't need the line number since the line number is relevant for us so right now we are going to check so if like currently we are we are going to pass c index is the first index from which we can start inputting the word so if we are including a word and then passing on to the next recursive function then we are also including the cnd plus one because we are also including the space for that so let's say the current index we can write is c index right we're going to check the current length of the word is norms of word index and the possible ending point of this index would be and end point would be c index plus length let me just make sure this is correct so let's say we have already included zero one two first three and we are writing three is the space and it's starting at four index let's say the word length is three then include four five and six so it would be ending at six now we have to make sure that 6 is less than equals to k so we check if k is less than equals to end point that means we can write this line here yes yes that's right so if we can include this then we also check like uh is it just make sure okay okay got it let's also include a cost for like currently zero but it will denote the number of spaces we have wasted or currently the number of like wasted you have done the cost we actually are including in this current iteration so let's say it's less than end point then the cost would be zero since we are not including anything and let's say the minimal cost for the recursive function is for now let's say minus one so we include minimal cost equals to minimum of minimum cost comma calculate the word index would be we'd increase by one and the c index would be currently at length and len plus one since we're including one space and plus one since we're uh inputting on the next length so it will be length plus 2 and weight passing nums so we can make this constant since we're not modifying this by passing k so this would be if we include this current word now okay exclusion doesn't uh have any condition since we can include no matter how many times and this should then we're gonna again minimize this against minimum cost calculate now since in this case we are not including this word we are going to pass in the same word again but since uh for some reason we are not including then we uh pass in c index as zero since we're moving on to the next line zero and for here we are going to uh so here the cost uh incurred in this current line would be zero since we are not uh minimizing any spaces but for in this case we calculate the number of spaces currently wasted and what would be that let's say we are currently on this index let's say zero one two three suppose you are going to be writing on the fourth index and we don't decide to write for some reason you move on to the next line so we are currently wasting suppose this index is three and the total length of k is suppose six so then investing six three spaces that is k minus s index so the cost would be if you don't include would be a minus c index and here we just add it to this current cost because it cost now we find the current main cost here and then are you sure that you are calculating the cost correctly uh when you are leaving sorry if suppose three spaces were left right yeah so here you are adding three to the cost uh the cost is currently k minus the index so three spaces were left right right so we're moving on to the next line that means the all the number of spaces which we are currently like uh present in this current line would all be oh sorry this would be into cost yeah so basically cost is where like the number of spaces in this number of services will be the cost for that particular line when you are leaving that much support yeah this is constant cost so yeah this looks good so this is the brute force approach now can i run the code to make sure if this is you can split it okay got it let's see if okay so okay that time exception segmentation i think uh okay i'm not including the base condition word index is we're going to check if this is more than equal to n then they were going running into the base connection and then we'll return zero since no how can you ever do more than ah we don't but uh okay fine i'll take it zero so okay would it be zero this here let me check let's work in this current line and three spaces are remaining but we run out of words so this spaces would not be included yeah so this is zero okay let's see okay we are again running into the segmentation fault fine so this this guys all of you can make sure to hit the like button okay because i can see the number of people watching and the number of likes or less uh can you think about it like where you might have made some mistakes yes segmentation default means i'm wrongly indexing indexing the current array so the only idea here is vector nums the only time indexing it is here yeah this looks like so word index cannot be less than n it is code so i can i print some debug statements if you want you can okay uh but one mistake that you're making i think is that uh in the min cost uh after the if statement you have not passed the board index plus one i think because if you have processed the particular word then you are moving to the next line yes i have put in a ford index plus one here uh in the next part main cost ah here i'm not including this current okay so it's going running into a infinite loop got it got it understood yeah so it's basically checking the same condition again and again yeah somehow [Music] so we're only going to check this mean cost if c index is not already zero like if it's already zero we're just keeping a line [Music] more than zero then only we can make this statement let's see now okay so it's got it let me just remove this it's minus one maximum minimizing this yeah okay so it's not considering any values fine ah main main costs maybe you could have thought a little bit more before uh writing the code yeah okay so it's going to the first condition okay so it's not considering any other checks things in terms of basics right uh for every ayat word that you are at okay so you don't know exactly the word right you don't know the characters right but it does not matter you know the length of this word so you have choices right okay so yeah for this so this is um what have you done like you have written okay so let's say if you are remaining in the same line then from where you start are you taking the spaces that are required to take uh yes um like suppose let me just minimize this okay i cannot check this out ah what index is plus one length is plus two so it's currently on part four okay so it's not including any words for it so end point is index plus len is numbs.length the first word length is 3 and 3 plus your end point is basically this index is past three okay so this condition should be triggered but for some reason it's not getting triggered put end point as less so for the first index the end point is less than this okay so this condition is getting triggered but word index is not increasing okay we're not including any x plus one okay so i don't think i need to put it in here uh so basically why do you think that it's failing you have any idea like why do you think that you're getting a lesser output compared to the expected i think it's not calculating this current spaces correctly for some reason just make sure that every condition is being checked once or twice ah three comma zero three comma zero okay so it's uh what index what is it correct okay so first it's zero then it moves on to the next skips uh maybe we can try it on later if we have time but since we are falling short of time so can you quickly move to the docks okay uh let's move to the next question uh so you just open the docks again yeah yeah this is the google docs yeah try to scroll down a bit just uh yeah right this one so let's quickly have a look at this one so it says that uh i'll give you an array okay let me change the right ones so basically the problem is that i'll give an array of words okay again i'll give you an array of words so here it will continue consists of words actually so i'll give you a vector or a list that will consist of some strings so you have to find what you have to find all the shortest unique prefixes to represent each word in the given array okay what you have to do is you have to find all the shortest unique prefixes to repeat uh to represent each word in the given array assume that no no word is prefix of another so let's say if i talk about a word like zebra okay can you see the word zebra there yeah i can see you can see that right so if i see with just z if i take uh if the smallest prefix like i that i can take prefix is the starting part of the string right so from the zeroth index so if i see if i can i represent zebra with z is z contained in any other string no so i can represent zebra with z correct now if i see dog so can i represent dog with d what do you think you're saying no no dog if i represent dog with d then duck also starts with d and dove also starts with d so can i represent dog with d o ah no double also starts with d why because if was uh dog with d.o then dove also starts with deo so there will be a conflict there will be a consume confusion for me right so it will not be unique anymore uh can i represent a dog with dog definitely yes okay so the shortest unique prefix that i can take for dog is dog only if i talk about duck so can i represent duck with d ah duck quit no no you cannot right you can possibly cannot but can i represent why because three three different strings are there dog duck and duff which starts with d so there will be a conflict for me but can i represent uniquely the duck with the prefix uh yeah i can uh can i represent the uh like is my voice audible yeah you're also soluble you can represent duck with d u yeah right because it is not like d u is not the starting of any prefix right any other any other string now if i talk about dove so can i represent duck with dove with d no no can i represent it with d o uh with no why because dog is the same d u comes in dog as well uh so there will be a conflict so it's not not unique so i can represent the with dov correct right getting this example got it so you for every word that i have given in the string you have to represent it using a unique shortest like shortest unique prefix you have to print you have to return in a vector or a list you have to return for every word you have to return the shortest unique prefix for that particular word that is what you you have to do if the audience has understood this question they can write a plus one in the chat or clear in the chat and hit the like button and agree you have understood this question also yeah uh so what do you think what can you apply here uh so the first thing that comes to my mind is using a try to like represent this all the strings initially and then keep being a counter of the number of words that are currently existing under the current node and we could just after the build the try we could traverse the words again one by one again through each character and in each node we're going to find if the number of words currently existing beneath that node is one or not like if it is more than one then more than one words are existing so we go down by one level and as soon as we reach one we return the current string which you just formed as the longest prefix the shortest prefix sir okay so you are saying that you will use the tried data structure for this yeah uh can you try to write the code for it sure can you like once again okay [Music] you can see the private chat i've just provided you to link i hope that it works so first i'll quote the try uh you can also uh keep telling me about like tries what are tries and why they are used uh should i explain what it tries again while you're writing the code for it you can just explain like what are tries and while you're in writing so you can explain that okay why you are taking this in this got it so try first of all uh holds each note of try holds the current number of like basically tree which uh holds the current number of the suffixes uh after this current node which are formed so it basically keeps a track of all the current uh characters which is explode till now so that would be next 26 is that 26 oh one thing i forgot to make sure these are only going to consist of lowercase uh characters right right yes you got it and you're also going to keep a boolean uf which denotes the end of string [Applause] initially we point all the pointers of this next array null here is also false i'm going to have a function word city os can you tell me some uses of price in real life surprise the store like to store strings in an efficient manner such that lookup time is uh linear uh but the spaces let's say let's say when i ask you that can you tell me a real-life implementation of data structure like stacks so can you tell me that uh it's used like stood like for example we are storing dishes on top of one another like that's an example of a stack we choose the first dish first like real life coded example where we use coded example uh stack for example when you're writing a code and we need to delete the last written character we use the backspace uses stack to remove the last written character okay so let's say if i have to talk let's say about uh this thing when i talk about graphs so can you tell me in real life there are graphs used or some algorithms of graph they're used in real applications right gps right like like a company like uber or other they use the shortest path thing right amazon and others in various ways right yes or no so like uh you also have the tree so why do you use tree so because uh in the uh your memory uh the folders and everything like it is kind of a tree based structure right many many times right right so i'm asking what is the real life use case of try have you ever heard about it any anyone use cases audience can also uh keep on guessing in the chat audience can if anyone in the audience knows they can also tell us i'm just i think it says in a dictionary okay or like some or like in code editors there is autocomplete thing so when you write the first string it displays all the current uh completion section there correct auto suggest using try [Music] [Music] okay so you can keep on explaining while you are writing the code so basically what next does is checks if the current next character exists in the current node and if it doesn't it returns a false and here we're going to basically retrieve the okay we can take references here i think let's set us this is going to be false we are not going to set it false anyways also we are going to make everything public [Applause] what you get next does is is basically fetches if there is a current if the current node has this character if it doesn't have this character it first creates this node so let's say c minus e so basically the insertion operation yeah okay next no it kind of if there's the node doesn't exist then it inserts or else it returns the node which is already existing from this function you're writing for inserting each and every word now yeah but you'll also use it to get the words one by one so i don't have to write an external function for that i can accomplish both this is suppose let's call the root and this will be a dummy node and we're also going to have a head right through each string one by one i'm going to check if add i'm not going to think we're just going to get the next whose head dot get next guys he is efficiently coding price almost so you can hit the like button for him and let's see what happens in the next 10 minutes so what are you trying to do first of all i think you are trying to insert all the i'm inserting each character one by one into the try each character okay yeah of a particular string yeah yeah and after the string has ended i'm just going to set this as s it's basically the end of word uh i've written this i think this is indicating that okay at this particular string the word is ending okay this is the basic tri structure now als i want to also keep count of the number of strings that are currently under a node so i'm going to include that in a variable let's say count initially count is zero and whenever we have creating a new node that means a new word is being inserted then we increase the current count unless no just to make sure we can include it outside only so [Music] include head of count firstly head equals to root and then we are going to include increment the count variable by one since we are including one word and each time a new node is processed we're also on also in implement this by what okay yeah looks good now this is the recession part basically when you are building the try so what you are doing is for a particular node you are saying that how many words are having that particular word right how many words are crossing that in the path yeah yeah yeah and if it has just uh like when will you add when you say that okay you can add it let's say for z let's say for z what will happen let's say for z when you're having zebra so you're trying let's suppose you're trying to build so you are saying that uh when your tries built so when you will have zebra and said okay first check has next if it has already said or not if it already has z then it will just uh return the next node it won't create a next node but if it doesn't has a z then it returns like creates a new node and returns that and the count function is basically doing here as soon as we like encounter a new node new node in the sense like as uh like in a new word a new character is being inserted so in that case we're going to increment the current nodes value by one okay so the n is this okay got it uh okay let's see the current string which you're going to insert okay go ahead and just push back this we're doing the same thing let me check okay okay let's head again and it goes root retrieve the first head okay this would be uh error operators instead operating with pointers so we get next okay next and we add this current character to this string and then we check if head dot count is equals to equals to one yeah then basically break break out of this and you've got a current node and they push this in this back okay and at the end we just returned the answer can you tell us what happened with zebra let's say your tri was built what happened with then uh i'll just uh run you through this again if it's the compilation errors first typo here 49 buttons problem okay this class 11 okay let's see if this is running or not compilation 3. so i think it's doing this problem with referencing just copy the strings here [Music] okay so this version of c plus plus still doesn't support forage loops i think okay this is not an array so i have to manually index through it okay [Music] so [Music] okay looks like it's working so do you want me to try it on this uh for zebra uh you can try to submit it if it's working we have less time okay if it's working for the samples okay perfect perfect oh yeah you can just quickly explain in two or three minutes what you did okay great so for this zebra let's say we have taking zebra uh so i think it would be better to like draw in a example explain can i draw this because try needs we have a we have a constraint of time so i'll explain on behalf of you so basically what he's trying to do is he has built that data structure uh now for this the prerequisite is that you should know the try now what he has said you are using counter right so what he has done is like let's say let's say dog was there so if inside the try like for the dog for the node d that is from the root there is a node d so that will be updated three times it's its counter will be three times right you are doing this now yeah yeah it's out of for you will be three so he's trying to iterate so when he iterates d so dog when he goes for dogs so he sees that okay d is having three frequencies so it is common with three words three different words so he cannot use it then he goes to o o is having the frequency is two so he cannot use it then he goes to g okay for dog he goes to the next uh character so for g when it when he goes to g then uh the character frequency i think is one right so in that case you are updating your string to dog okay after that uh let's say he has zebra so for he goes to z then z has the frequency as one itself so he immediately stores it because he says that okay if that is one so that z is just common with one string so it's unique so you will simply store it if you talk about dove so he goes to d the frequency is three so that's why what he's doing is if the frequency is three so he'll say no he cannot do it if he goes to o uh then i think o is having the frequency is two so o is having the frequency o is common in two words that is dog and duff so he'll not use it he like so he has up till now he has stored d o in the answer i think then he goes down and he goes to v so v is having the frequency as one only so he stores d o v this is what you're doing yeah okay so this was the code uh so now like it was a great session uh like can you share the experience with us like how was it then i'll share my feedback if you want how was the experience so it was a great experience like uh normally i though what chorus do is uh they don't have this habit of like coding and explaining the lines they're writing so that also happened with me so the mind has to be in two places like one you have to explain the code that you're writing and also like you have to write the code that is correct so that kind of like it's distracting so at some point but uh that's what interview is about so this mock interview really helped me like uh come to that issue like uh that's really helpful for that okay and one more thing i think that you could have implemented the word wrap you were able to think about dpn taking not taking things like that it's very very similar to the knapsack basic parent problem yeah so i think you could have implemented it there were some some issues i think uh basically you were uh not thinking much before writing the code sometimes so that is why overall your flow was not that good but uh overall like if i'll share my feedback so you were really good your implementation skills are also good and like since you said that your final year i think has just started so you will be getting very good placements going forward that's for sure all the best for that i i really liked interviewing you that's why i've taken two heart problems so you almost solved two hard problems in an hour so you just had like i i think initially it was tough uh solving it online in front of 200 people watching you so it you have that peer pressure but you'd still manage it almost word wrap i think you almost did it i know that you could have done it you just needed five four minutes for it to figure out so that was really great and thank you jagrit for taking your time and uh being there for the mock interview thank you for volunteering and i hope that you like the experience of taking this mock into vxdft definitely definitely okay so thank you and we'll see you some other time maybe for some other mock interview if you will like sure uh so thank you so bye so now uh so hi everyone uh so thank you everyone for joining in i hope that you liked this particular mock interview uh bihar so i tried to ask him some good questions two hard questions and he almost coded them up so make sure to hit the like button before we go make sure to hit the like button and if you did like this session so make sure to hit uh give us a plus one in the chat okay i'm just here for 30 seconds smoke so all of you can just give a plus one in chat if you like today's session uh the questions that we took like both were hard level questions asked in some good product based companies that we aspire for and they were not the generic question that we usually do so a quick plus one in the chat and hit the like button guys uh i'm just waiting here for 30 seconds more then i'll end this history okay i hope that you liked today's session jagri was really good in terms of coding he i hope that you learned that okay when you get stuck even then you can come back and do the second question right so these things you can learn from these kind of mock interviews uh the questions as you know were disclosed to him right now only so thank you everyone for joining joining in and make sure to hit the in case after this video is over so make sure to comment down uh helpful or something if you found this to be useful then you can write a comment useful after this particular stream is over and if you want to give the mock interview so you can fill the form that's given down in the comment description of this video thank you everyone for joining and i'll see you in the next mock interview till then take care good bye and happy coding