Live Mock Data Structures and Algorithms

Key Takeaways

so guys very good afternoon this is few channel and i welcome you all to your own channel which is geeks for geeks and today we have we are here for the mock interview and we have mr chetan with us so we will be uh taking the interview of caitanya right so without wasting much time if you can tell me right if you can tell me if i'm clearly audible and acknowledge if you can acknowledge me that if i'm clearly audible to you just put hi hello in the comment box if i'm audible so that i can oh okay thank you thank you very much let me call chetan here and okay so very good afternoon chetan how's you good good afternoon sir i am fine how are you sir i'm good i'm good dear okay so chetan i got your resume right but didn't get time to go through it it would be great if you can tell me some technical side of yours okay so so my name is jatin i am a pre-final year student at jc bose university of science and technology pursuing my b tech in computer engineering and coming to my technical skills i find myself more inclined towards web development and my most recent project in the web development is named as service fair which is a platform to connect uh clients and professionals so here the clients can come connect to professionals and avail services from professionals and we have different different categories uh uh depending upon which we have professionals in uh each of the categories and from there the client can select the category and pick up the professionals based on their previous uh work like which they have done based on their previous ratings and all so from there he can choose the best professional for his work okay okay that was great and what technology you have been what technology stack you have used for develop this so for this i have used uh man stack uh so um here okay so like have you heard of mvc architecture what is it yeah i i have actually implemented the mvc architecture in it so it is basically consisting of three components the model view and the controller and uh the model is responsible for the connecting with the database and getting the data from the database and then with the help of the controller it passes that data to the views and the views uh are actually what is passed to the browser which are rendered to the clients so this is about the architecture okay okay so there is one concept right mvp have you heard of it mvp okay and rest apis yeah yeah i'm familiar with rest apis so rest api is a stands for representational state transfer so it basically is an architectural design which allows us to like which allows us to create websites so that uh data that uh uh is sent from our website uh when someone some user visits our apis is represented in a useful format or meaningful format like the various formats that are used are like json and xml so these are some of the formats in which the data is represented and uh this is about the rest devices so what in what form you transfer the data from with from your rest apis right what format did you use so yeah so i used a json object to transfer the data from my server to the client side so this is how the data is okay why jason why jason why not xml so uh xml is a little difficult to pass as compared to json and that is why i i just used json to pass the data because xml is a little it takes a little more time as compared to json to pass so that is why i used json okay so tell me right how much you are comfortable in data such as if i ask you to rate yourself on a scale of one to ten right where one is the least and ten is maximum how much would you rate yourself sir i would rate myself for somewhere between 7.5 to 8 in dsa 7.5 that is good not bad 7.5 to 8 okay so tell me uh can you share your screen so that may i know right uh you i want you to write certain piece of code would you be comfortable with that yeah i i can share the screenshot say is my screen visible yes it would be right okay so you can open up the editor of your choice right okay so so i am opening my online id okay yeah sir is my screen visible yes it is it is so so you would be using java you would be using javascript okay that's fine so my question is right you are given an array right and you need to find whether that array contains a duplicate element or not what would be what would be your approach let's see the approach first then we'll see the sir like the brute force approach would be to use two nested loops and the outer loop will iterate from the n minus 1 numbers and the inner loop will check the frequency of every number and so if a number is repeated uh then its frequency will be greater than one and we could find that uh element okay so for like the yeah if what the complexity of this yeah so time complexity for this would be big o for n square where n is the size of the array and the space complexity for this would be uh like if we want to find all the duplicate numbers then it would be taking the space equal to the number of duplicate numbers if we want to return the number of numbers that are duplicate then the space complexity would be equal to the numbers that that are equal to duplicate that duplicate okay i like my question was i need to know whether the array contains duplicate elements or not right for this the space complexity will be constant okay uh better approach than this so we could uh use a hashtag or a dictionary to keep track of whether an element is previously and seen or not so if an element is previously seen it means that that element is a duplicate in the array so we could find it in a linear scan only so the time complexity for that would be uh big o of n and the space complexity would also be big o of n okay so what you'll do you will use a hash table yeah we can use a hash table where we can store the frequency of every element okay and you told me that the complexity is going to be so we will actually be requiring only a linear scan of the array so the time complexity is going to be linear and space complexity uh this space complexity is also going to be big of an in the worst case uh if all the elements are distinct in the array then you would be ending up entering all the elements into the hash table so this phase complexity is going to be linear okay if i don't if i give you one more condition right that suppose the size of array is n right and all the elements in that array is going to be less than the size of a right from 1 to less than size of array right so i'm giving you the space also the range also from which you the array will have the elements right right so in that case can you do better sir in that case so like uh what we could do is so like uh is there only i would like to ask one question like is there only a single element that is going to be repeated or there can be multiple elements that are going to be repeated there could be multiple like there could be multiple elements that could be required okay so in that case uh what we could do is we could uh use the indices of of the array as a way of mapping the elements to their uh to the indices like what i mean to say is like if we have for the elements like one two three and they are like present at different locations so i'm assuming one based indexing so what i'm mean to say here is that the three i would place all these elements to their correct positions and i would uh what is the correct position it is actually the index of the array so at the first index i am going to place one and at the second index i am going to place two and at the third index i am going to place three and after after doing this i i actually have placed all the elements uh at their correct positions now whichever uh element is like whichever element is not present at its correct position uh that element is actually repeated for example let's take another example like three two one and two and and three so the element would be placed like this so now this last three is not at its correct position uh so that is how we would be knowing like this element is repeated and they are contained duplicates can you write the code for like first you tell me what is going to be the complexity of it so for this the complexity is going to be linear only because we are going to place the elements in the array and this space complexity is also constant in this case okay can you write the write the code for this yeah i i can write the code so i'm actually making a function that is going to return a boolean value whether a actual challenge whether there is a duplicate in the array or not so here they would be given an array and and it will denote the size of the array so like what i have to do here is uh i can take a pointer which will scan the entire array so i initialize it with zero and while i end up scanning the entire array what i'm going to do is i'm going to check if the current index if the element at the current index is equal to ai or not so if it is not equal then i am going to place it at its correct position like here uh 3 is not at its correct position so i know uh what is its correct position so whatever element is present at that position i am going to place it over here and uh then i am going to place this element at its correct position okay let let let me just uh think about it so if y plus one and is me hold this in a thumb here and then pi would be equal to a of tam minus one and the a of them minus one would be equal to thumb let me just uh see if it is working fine i zero and one is not equal to three so what we did but in the temp we stored we stored three and whatever uh element is present at the second index we placed it at the first position and we have two and then at the temp minus one we place three yeah so after this uh what we are going to do is uh now the element is placed at its correct position and here we are actually not going to increment a pointer because uh we might encounter the same element again okay like three and three again so for that we also need to keep track because we might end up in an infinite loop let me see about you think about it but if it is like equal to this then we are going to increment i and it will be tell me one thing tell me one thing over here if the elements are already at correct position right they are i'm giving you already in sorted order one two three four five what you will do in that case so that is what i need to try that is what i need to handle in the line number 13 whether i would have to implement i or not so what i can do here is if if a i is now equal to i plus 1 so then i would increment i it means that the elements are already present at their correct position so i would increment the pointer to point to next value okay and when would you declare that it contains duplicate so for that i actually need to do a linear scan again [Music] for this like i would have to uh i can reinitialize that and then i could do and if there is some uh element that is not equal to a then it means that this element is repeated then from there i can return that it contains duplicates and otherwise if i plus 1 is not equals to a i it means that there is a duplicate so because i already placed all the elements that were equal to a at their correct position in the previous while loop so here i am checking if there is any element that is not equal to that index then it means that this element is repeated in the array actually let me uh do a dry run with it then it would be more clear so let's take like the array uh p2 1 3 so initially i is 0 and 1 is not equal to 3 so what we did we hold this value 3 in the temporary variable and after this whatever it was present at the second position we placed it over here so now our a0 becomes 1 and a 2 becomes 3 so now the array becomes 3 sorry 1 2 3 and 3 and so now i also check this condition if a i a is equal to i plus 1 right so here the a1 a0 is equal to 1 that is this one is equal to this index so i incremented i so now i is pointing at the second index that is at the first index and the second position so now this element is actually at its correct position so i i came in the else part and i incremented i so i my i now points to a second index so i again check this condition if i plus 1 is equal to a i not equal to but again this is equal so we came in the else part so that is how we implemented the index to point to the third position so now it is not equal and so we entered in the if if case and in here we in the tamp we have three and uh and but whatever is there at the ith index that is also equal to 3 so a of 3 is also equal to 3 and again what it is doing is it is updating a of 2 to equal to 3 and i have actually checked that condition if a i is equal to i plus 1 which is there uh actually i yeah i think a a3 is equal to actually i i have to check this condition if a of tamp minus 1 is equal to tam because that is what is repeated here i think temp minus 1 equals to 10 won't work okay let me let me just think about it you're going right right you were going right but one condition is missing still missing yeah so at the line number 13 i think the condition is wrong so here i think we need to check it somehow if the position at which we with which we are replacing it if that is equal to this then we do not actually need to swipe it okay yeah i think the value at t of damp minus 1 i think we can actually test it earlier also in the beginning if that is equal to a in then we can simply skip this part and we can implement it like if like in this case like at the third index if the value uh what is the value of the third index this is three and this is also matching with its correct its correct position where it should be present so that is why we we will implement i and now i will be pointing to the end of the array and we will come out of this while loop so is that fine sir okay let me check well in what case can you can you drive run it for like one two three four five right here how it will work it will always go to elsewhere yeah it will always go to elsewhere and will increment i and in that case uh uh we will simply since all the elements are at their correct position so we will simply come out of this while loop and we will check here okay tell me one thing tell me one thing do i really need the second loop traversal for telling that whether array contains duplicate or not when i was doing this swapping thing right when i was checking this thing can i make sure at this time only that error continues to click it sir i think why do i need why do i need this second loop the second traversal so actually in this second traversal what i'm doing is i'm i'm checking if any element is not present at its correct position that means it is duplicated why can't why can't this be done in the first loop only when you are placing all the elements their respective position if that element the same element you are again founding it right yeah yeah we i think we can do it at line number 11 if uh the element is like already if like whatever element is present if they are present at their correct position then we would we can say that we have found a duplicate element in the array and from there only we can return false i think from here exactly right we don't need the second loop to tell yeah yeah absolutely sir i hope you got the idea right yeah yeah from there itself we can written false and otherwise uh like i can comment it uh from there itself we can written true because we found a duplicate and otherwise we we can return false if the arrow doesn't contain any duplicates right so can we do this once right for one example suppose you are given a number one array one two three one two three how will you do it for that one will this work for you yes yes one two three one two three okay so for this let me just mark the indices four five six so firstly uh we will check if i plus one is ai so since it is equal to ai so we will come to the next point we will increment our pointer and now our pointer is at second position since it is also equal so now we are at third position and now when we are at fourth position i plus one is not equal to ai so in the temporary variable we have a which is one and actually at a of temp minus 1 which is 1 minus 1 here we have the same value that is 1 so that is why we can simply return from here itself that we have a duplicate element in the array so that is why uh we will return from from here only okay okay yeah so basically it is uh checking whether uh the position at which this element should be present if any uh if an element is already present at this position it means that we have encountered a duplicate exactly so this will give so what would be the complexity of this now so the complexity is uh big o of n only and the space complexity is constant so if i tell you that array contains only one duplicate and again the same condition array size the array elements will be less than the size of array what will we do in that case say in that case also this will work fine but if you want me to come up with a different approach then i can [Music] yeah so i know this will work fine right if we could find out some easier solution because we are increa we are given one more condition right it contains exactly one duplicate okay so in that case so what we could do uh we could use this or operator so since we know that the zoro of same quantities is equal to zero so what i can do is i can do a quick linear scan of all the numbers from 1 to n and i can store that in some variable by doing so of all the variables from 1 to n okay and after that i will do the jaw with the elements of the array and whatever element i have whatever is the result of this or value after scanning the array this will tell me the repeated element okay so what will you do you will do the zoro all the all the elements and draw of one to n yeah yeah so what how this will work is like all the elements that are present one time in the array they are actually now present even number of times in in both the operations after doing both the operations so they will actually uh reduce this or to zero okay so like if phase or two similar quantities then their resultant is zero right so and if we do anything with if we do the jaw of any other number with zero then that gives us that number so this is the idea that it's used and okay like whichever whichever element is repeated it is present odd number of times so that is how we will find it okay okay good great let's move to next question right okay so you are given a number a and i want to convert this to number b right so i'm giving you two numbers okay suppose i'm giving you 10 and b is 20 so i want to convert 10 to 20 how can i do that so like uh we can check if for the whatever is the like we can add some number to that or subtract some number two from that like if the number is greater than the number which we want to make then we can add uh whatever is the difference between the two numbers and now if i need to tell you how many bits minimum bits needs to be toggled changed right to convert a to b okay can you tell me this so the binary of tan is like from a to b so okay let me think so i think we can find the binary representations and can check if we could do something like whatever is the bits that we need to change okay it means like the binary of 10 is 1 0 1 0 and a binary of 20 years this is 4 8 16 yeah so this is a binary of 20 so from here i can check like at the corresponding positions if the bits are same then i don't need to change them if if they are different then i need to change them so from there here so from there we can know like how many bits we actually need to change am i audible yes yes you are audible so how what will you do like how will you do it in program so uh i will actually find the binary representation of both the numbers that is a and b and after finding the binary representation i i can check like if at the corresponding positions if the bits are same then i would not count it otherwise if the bits are different then i could uh i i actually have to change uh one bit so i could find okay so you will you will convert the number into binary first right yeah yeah but numbers are already represented in binary right why do i need to convert them yeah yeah they are already represented or represented but i was saying that we would get this representation somehow okay what will be the complexity of the solution what will be the complexity of the solution according to you so uh the complexity is going to be uh they go of the login where n is this number and actually it will be equal to the size of bits that that are actually used to represent that number like if it is an integer then it will be 30 how many bits how many bits are needed to represent the number like how do you what like if it is an integer then 32 bits are required to represent that number like in java it is 32 bits are you sure are you sure how many bits are needed to represent 10 so for like i am talking about the like the maximum number so for that we required 32 bits for 10 we only require four four bits so your complexity will depend on the number of binary bits representation yeah yeah that will be actually equal to the number of bits in the maximum number of bits in the binary representation of any of the numbers okay and yeah so what will be what is the maximum number of bits how how we figure out the maximum number of bits you represent a number in binary so that is uh given by log log n base 2 plus 1 i guess the seal value of log in so that is going to be the complexity right yeah yeah that is what i i i yes so the complexity of your solution will be so it is big of login base two okay and then you would be now traversing this you need one traversal also right yeah we need one traversal to find if the corresponding bits are same or not okay any better solution than this i want to do it in bigger one okay okay let me think so so here like for 10 and 20 what i can do is i can i think what i can do is uh i can do this or operation so whichever bits are same uh the zero of them will be zero and whichever bits are different the zero of them will be one and then i can count the number of set bits in the resultant of these two numbers like the resultants are of these two numbers okay let's write the code for this first yes also so [Music] i'm making a function and it will written as the number of different bits in two numbers and uh we can do a sort of these two numbers and then i just need to count how many bits are set in both the numbers so i am initializing a counter which is initialized with zero and then uh so actually there's an algorithm like which checks this in how many bits are set in the big o of the number of set bits in both the num in the number so what it does what is the name of that algorithm so the name is actually i'm not familiar with the name like but how it works is like it removes the least significant sad bit from its corresponding position so what we do is we yeah let me show it in the code itself so while the zor is you write the you write the code for it right yes yeah so while the jar is greater than zero uh we will implement a counter and we do this or uh we update this or with the bitwise end of zor and zor minus one and finally we return the count like whatever is the count so what this is actually doing is like if i have to talk about this example so the bitwise end of uh zor and zar minus one so this is actually removing the last set bit so this is what it is doing so okay tell me one thing i got the idea i got the idea right tell me one thing you have put the brackets around like zor minus one right if i remove them will the solution work again or not see actually uh that depends upon the priority so uh i think the solution will work because bitwise and is having uh less priority as computer subtraction minus operator so first of all this first of all this uh subtraction is performed and after this the bitwise end is going to be performed are you sure like uh i'm not 100 sure but i think like i i think uh like the minus is having more priority as compared to bitwise end okay but i'm not 100 sure i i need to actually check a computer should also think the same right the compiler should also think the same what you think then only it will work yeah that is why i placed a bracket to increase its uh like i just wanted to know whether you know the precedence or not right yeah okay so yeah so this will change the precedence of like this bracket operation will be performed first and then we will do a bitwise m50 that's fine okay this will work right yeah this this should work okay so we still have right 20 minutes more right well what we can do is i can ask you one more question so would you like a dsa question or some question from your projects so as as your wish i think we can you can ask me a dsa question that will be great because projects i have copied right no no no they are not copied okay one project that you have made is algorithm visualizer right so sorting visualizer sorting visually sorting visualizer right so i've seen so many sorting visualizers how your sorting visualizer is different from the ones who are present in uh the online the people have developed so actually this project was uh made to learn the uh react.js concepts and the animations in reactions so that is why i built it and the okay you built it on your own can i see can i see how is it working uh yeah i can show you like i have to actually open my resume first so sir like if we want to generate a new array we we can generate that and like if i click on the merge sort so this will start merging the array like initially the left half is merged then the right half and then finally it will give us the sorted array so if you want like quick sort so it i have actually chosen the last element as you see all the visualization i want to stop here right because all the visualizers i've seen they do it this way only right i wanted some i wanted to see something different right where you are telling that how the steps are working how the code is working where the piece of like by seeing this visualization how can i figure out right how can i figure out how the algorithm is working so you click the button it sorted on its own and i see the after results right i see the the data is sorted how it is helping me to learn the algorithms how it is helping me to determine the difference between the organs so actually as i mentioned like it was just to learn the concepts of react.js and the frame react framer animations so that is why i built it i i did not break it for for the purpose of like allowing anyone to learn it like so but do it right do it do it chetan right let it modify it in a way you need to modify it in a way so that it helps others your project should not be for the localhost deployment only i have done it i have learned and it's done you should be building a project so that it can be used it can be of some use for others as well yeah right sure so do it in that way like i it's my suggestion for you modify it so that it can help others to learn sorting algorithms it is a simple uh sorting visualizer as like hundreds present already present on github's right it is same as that so i can also show you like the other project which i made recently so okay okay let let me talk something about it right can you see this okay so you have implemented merge sort quick sort selection sort insertion sort right yes which sorting algorithms are stable sorting algorithms among these so actually the mud sort and this mud sort is a stable one quick sort is not a stable one so but we can like make the unstable as stable ones also by doing some modifications but so heapsort is also it's an unstable algorithm and the selection sort is a stable algorithm and if you talk about insertion sort so here we compare the element with the previous element so it is like in the case of equality if two elements are equal then they are not swept like whichever element is happening earlier it is there in the it is present first so it is also a stable algorithm so you told me insertion sort is stable you told me my sort is stable so because when the elements in the left side left up are same so we actually copy it from the left half only and we increment the left pointer to to point to the next position that is why it is stable great that's fine that's fine okay so that's all from my side chetan right now i think it's done right any questions you have for me so like uh i have like only i ever only like to ask like if if you could suggest some improvements that which i can do and like the feedback so i have few feedbacks right i have a few feedback that i would love to share right okay and this is the best part where you should be noticing noting those points right absolutely okay so uh let me move this right first thing is but you are very calm right you were not so nervous you were answering the questions very politely right and i really loved the way that you were handling the questions answering the queries you were stuck at certain points still like i couldn't see those lines at your forehead right so that was the best part i i loved the way you like this whole session was conducted that was a so i love the interaction of yours right so that was the first part after that when i see you might have also realized this thing the questions are not very difficult right i asked you the basic questions but keep on changing those questions as you were trying you were uh able to answer them right so why i did that because i wanted to know right because there are certain times when we know the the solutions for some situations right but if the situation is changed at the time how you are going to respond that right i know the solution for one problem right but if that problem is not presented in that way it is presented in some other way so if that i've crammed that solution if i have just do the tretification then it would not be possible for me to give the answer for those molded questions right so that's why i asked one question keep on molding the same question with that with that you can actually verify the the genuine learning of the person right and you were truly like you you stand uh to that mark which i was expecting okay so because you were because that shows that you have good concept conceptual knowledge that's why you are able to answer the changed question or the molded question right that was that was the good part of yours right and tell me honestly right from where did you get that zor xorvala idea uh when i i was asking you this bit questions right so you read the chats no no no no actually was so i i didn't write the chats actually uh i i just uh applied the property only like i thought it in some way like zoro operation does this so we can use that property so you thought it on your own yeah actually i was also having a different approach of finding the sum of of n elements because we know the sum of first 10 natural numbers and then subtracting that's subtracting that sum from the array elements so somehow i i was not i'm not talking about the array question right i was talking i'm talking about uh converting a to b first you were saying that i will be doing the binary representation you were stuck with that yeah you were saying that i will be doing that but suddenly you realize that i can do zor xor as well so how did you get the idea so i actually observed it from the 10 and 20 pattern like the example that you gave me so i actually observed that pattern like if we can do that do this or and the same bits will be off and the different bits will be on so if we can count the number of different bits so that's high that's how i got the idea and i just told you that okay that's fine that's fine so why i wanted to know that because you were stuck to the point right i will do the binary conversion i will then count the bits but suddenly you need the solution right that i will do xor when i told you that i have to do we have to do it in big one right so i thought at that point that you you read the chat so you got idea from somewhere right but still when you are able to see it does not make any difference to me whether you because when you are working in the company it is not possible for you to know the every solution but if you can google the solution and can code them right correctly so if i can look for the solution okay and what i know i i need to write the code if so for me if you have read the chats got the idea from the set but you implemented that that that's enough for me right that is what i wanted to know whether you can implement the idea or the suggestion correctly or not okay okay that's fine so like it it was a good interview from my side right if i would have been the real interviewer definitely i would have moved you to the next round and with that i wish you all the luck and okay so guys meanwhile before finishing this let me tell you that if you want to appear for these mock interviews description is in the link i hope you loved today's session you got some idea right how you can also how you you you can also be benefited from these sessions okay can you please type we love gfg if you really love the session right can you type we love gfg i love gfg so that me i know that you love the session okay meanwhile chetan it was nice interacting with you thank you so much sir i i actually learned a lot from it it was a nice experience to to get interviewed on gfc okay and i wish you luck also chetan for your future future interviews that you appear and definitely you will crack a good company you have good knowledge wish you luck thank you so much so guys let's finish up the session with okay okay i'm getting a lot of response right we love gfc yes we all love gfg if gmg is helping you and if you love this session right okay akshay madhya is saying i love gfg and practicing more and will surely apply for mock interview in future we are wait we will wait for you right we will wait for you definitely will help you okay okay we love gfg and a battle is a type of dj we love gfg and i'll finish up the session hello guys hurry up and we'll come up with more and more sessions for you everyone everyone thank you thank you nan i'm not getting your full name but okay thank you yash thank you very much thank you guys okay so sir i want to ask some questions some questions don't ask some question you can ask one question right i would love to answer them best moments right okay can we hit 50 likes before this live stream ends can you tell sir as a beginner how to practice gfg dsa so bharath bhushan have you have you enrolled in this course yes 30 years code manager and give us 50 likes okay cherry technics is saying make these problems available surely so generally what happens sherry and let me tell you uh these questions are not planned question right we don't know what to ask right uh so it happens like we interact with the students and we come up with the question at the moment that's why but definitely we'll try we'll try so that we can have the links so that you can also solve it please remove that login pop-up okay i'll ask the technical team for that akash don't worry your point will be considered right so akash bigger point so that the technical team would be when watching this session they will definitely yes yes i got it i got it don't spam i i got it and i'm showing this message over here as well okay okay thank you thank you and keep this love alive for gfg and definitely will come up with better and yes please login yes we'll do it mr robot will do okay guys thank you thank you very much and we will join you in the next session thank you guys