Live Mock DSA | GeeksforGeeks

Key Takeaways

foreign are you sure this course is just for two four nine nine yes and you know this is the only course with this expertise across the world no way yes way [Music] don't delay enroll now Geeks learning together [Music] hi hi are you sure you can prepare for product based companies through this course yes sitting at home no way yes way don't delay enroll now Jake's learning together yes hey uh what do you mean by a self-paced course well the course material is available in the form of video lectures and there are multiple practice problems that come along as well so you can access all of it anywhere anytime and they are available to you for Lifetime no way oh yes way don't delay and enroll now Geeks learning together yeah hi uh very good evening everyone welcome to this life of DSA interview session and I am very pleased to see you all here so let me quickly introduce myself my name is suniti and I have a mentor at Geeks for geeks and uh this is one of our next wonderful Series where we conduct interview sessions right so um today our guest is human dhavan so let us welcome him and yeah here is foreign yes I am doing great how are you I'm great all right so uh can we just start with a quick introduction of yours yes uh sure so my name is himan davan and I am working as a uh I was engineer in payment us and I have experience of five years and uh um I am responsible for a single product in payments which is creating a framework for the payments and uh I have experience in flutter also and I have good command on that also so okay that's really very nice so uh today we are going to conduct a TSA interview session so I will quickly explain you the procedure so what are you going to do is uh I have shared a talk link with you so in that door click I will share the questions with you so first of all you can explain the approach that you will be using and then once we are clear on that part we will be doing the coding thing on the gfg portal all right thank you sir all right also can you please share your screen and open the dog file that I have been shared with you just wait a second uh um am I Audible yes yes uh I'm unlocking the Google Chrome screen sharing feature so wait a second yes is it visible is it visible now hello all right foreign hello all right uh this is an audible uh now the screen is straight now you are audible can you share the driving yeah okay Clan uh anyone please confirm if his screen is clearly visible and if my voice is Audible and his voice as well okay yeah now your screen is right yes so great sorry so the first question is giving an array of size edit and and foreign true very very divided K2 plus such that each side is the face okay are you writing anything on uh Google doc because I can't see anything okay so this this one is equal to six true because line three we keep makeup five seven all right so see uh the question statement here is uh am I audible to you human yes yes okay so uh the question statement here is you are given an array all right of size n and an integer K is given to you you have to return true if the entire error like entire area of the size n if you can divide it into the number of pairs such that each pair is divisible by K all right so in total there will be n by two pairs correct because we are wearing the elements so for example in test case work if you have nine five seven three and the case given to you listed so you will be returning true because uh we can add nine and three whose sum is 12 and 12 is divisible by 6 then we can add 5 and 7 whose sum is 12 again and 12 is divisible by 6 so that's why we are returning true because it is possible to divide the array so uh is the question statement clear yes it is clear all right so uh let me just write a bit of paper that we want from you like let us say you have to return a bowl and you have to check if you can pair it and a vector is given to you say array and any case give it your life you need to complete this function so first of all we can start with your approach and the pseudo code and then maybe we can move to the 4D version okay uh I have few questions like we uh don't have to have print uh any pair and just return true if any pair is there in this array right yes exactly for example whenever we find 9 3 and just we can skip uh the iteration to find the next one and we can return true exactly but you need to cover all the elements all the elements of the array must be covered uh if any any if there is a single pair then we have to return true right you have to check like let us see if your array is like this say if it is if it has been 9 5 7 2 all right in uh this case you can tell seven and five for twelve but you can't wear nine and two right because it will give you an 11 and 11 is not divisible right so that's why you will be returning false in that case so that is the thing you have to divide the entire array okay means uh if every pair in in the array that we can make and that is unique and that should be divisible by 6 and suppose if it contains one and we are uh uh like we have an pair of nine three five seven but we are left with one so this will in this case we will return false right exactly exactly okay and uh is there any limit on uh the PSI is of the array or the size of the integer anything like that uh like you can take it as you know or that raised to the power 5 the maximum value of n at the maximum value of array elements as well it will not exceed that okay uh I would like to First consider the edge cases here because we are supposed to find the pairs only and I think if uh the length of an array is odd uh inch uh there can be any pairs which is completing the array as well as divisible by our value key okay got it so can I write it in in Swift language Swift all right okay foreign so um can you help us with what are you thinking right now yes uh firstly I am thinking of using a brute force uh approach uh to uh solve the questions like we can uh think of all the unique pairs that can be made uh in an array and once we have the pairs and then uh we will uh we will we will add those pairs in an array and then we can get the count of those arrays and if it is equals to the count of the original one then we will return true and else we will return false and once we have considered uh that number for pairing we will not consider it for our next pairing approach Okay so how will you do it like you know uh iterating through all the elements and then checking for the valid pairs like you know you get pair nine with three as well and nine can be paired with nine as well right so we'll you'll have to check for that that whether you are going to pair it with 3 or pair it with nine so you will have to make a decision on that basis foreign just like a little bit of you know I would just like to give you a little bit of it okay so just tell me when you are dividing six with nine what will be the remainder it will be three okay okay when you are dividing six with five what will be the remainder one C or when you have divided six with nine the remainder was three and when you have uh when you are dividing six with three the remainder will again be three right so what is the sum of the remainders of nine and three uh nine and uh three like for the nine we have with six we have remainder of three and three six and with three what is the remainder that we have with six right with six we have remainder three all right okay okay so this is one pair now tell me uh what will be the remainder if you are dividing six with five and seven when we divide six with five the remainder will be one and we divide six with seven then remainder will be one when you divide six with five the remainder will be one remainder will be 5 right dividing six with five yes yes sorry exactly so is there any pattern that you can notice in the pairs yes its remainder is uh present in the array foreign [Music] foreign ERS of nine and three because they consist of pair and in the remainder of five and seven like what is the sum of the remainders of nine and three yeah it sums up to six and uh for for five and seven it also sums up to six all right and let us say if we had another pair say eight and four let us say so what is the sum of reminders for eight and four two and four exactly so what is their sub six exactly so any pattern that you can see here is the sum of the remainders of the pair are summing up to six to the value okay exactly so maybe we can use this approach that let us you know like you can maybe think over this that how you can now check for that like if some of the remainders are getting added up to K so you can think over this oh what what happened [Music] [Laughter] so we will iterate over this array and we will find the pair whose sum is six let us just keep track of the remainders that we have right say for example if you are having four as a remainder then you must have two as a remainder only then a pair can be formed is this part clear like if you are having a number which is giving 4 then there must exist a number which is given to otherwise the pair will not be formed right so yeah exactly so let us say if you are having a number which is giving a remainder one so there must be a number which will give you the remainder 5. right so uh how can you proceed with this to check the frequency if the frequency of free vendors are matching or not uh why we go this way because we can uh find the pairs like if we if we go from uh picking up this element and uh then add it and then find out that it's its remainder is zero then it can be in o n square is it is it uh resolving is it is it minimizing the complexity no like uh we can do it in linear time as well like just focusing on the remainders that we have because in this way we are first uh keeping the remainder and then finding out that is there any any other element in the array whose sum is equal to like we are just checking if the frequency like if suppose 4 the remainder 4 is occurring for two times then we will check that if remainder 2 is occurring two times as well or not so which data structures you can use you know to store the frequency and then check for it if the frequencies are same or not is there any data structure that can help you with this we can use hash map or dictionaries exactly you are perfectly right we will use hashback so you know or maybe in the hashmap you can store the counter frequencies right and then you can again Traverse in the array right and then you can check if the desired thing is there or not so that may help you are you comfortable in C plus plus or Java or anything like that all right no issues so I'm a little bit confused with the approach you are telling me uh I'm not able to get it okay uh like you were not able to get the approach yes how we can uh store the frequency and then we can okay so uh what I was saying is that you know what you can do is you can Traverse through the array and or then you can uh update the frequency map according to the remainder we have three at one index we have five five you can do this you know five plus plus the update that we do okay like you know in a hashmap what we do we update the frequencies right so we can do frequency of three plus plus then we can do frequency at five plus plus so frequency of 3 will be 1 frequency of 5 will be one and frequency of seven will be one and again frequency of 3 will be 2. right because we are getting this remainder again so uh you can update the frequency map in this way you just need to you know store the frequency of remainders just a normal hash map where you have to store the frequency of remainders foreign [Music] the array in which the element is there no not index like uh you can update it for the remainders like at frequency at 3 we have say two if remainder 3 is occurring for two times like that at frequency of 4 we should have a four window four is okay four times so like that you have to update it so there we can have the frequencies of like three has a frequency of 2 and 5 will have a frequency of one and uh one will have a frequency of four exactly okay just wait a second all right uh do you want to try on this question or do you want me to move to the next question yes we can move on to the next question all right so uh here's the next question that we have and I will quickly write it down so the question is you are given an array right and then it's external the number of possible triangles that can be fought from the edge of this cake so the best case one is let us say if we have our array as [Music] um seven and eight six four nine seventy three okay so uh the number of triangles that we can have here is 10 so what are those triangles um we can have six four nine then we can have six seven eight and then we can have cookies we can have six eight nine we can have six four seven like that or there can be total of ten crackers right so what you have to do is let us say uh so yeah what you have to do is array is given to you right or consisting of n elements and you have to return the number of total triangles that can be formed from this array right so uh yeah that is the question if there is any doubt 649 678 so these are all this these values must be unique uh or it can repeat no it can be same as well they can be distinct do any constraints on that you have to check if you know if you can form any triangles your the answer may be zero there is not a compression that there always be a triangle formed so first Edge case will be if the number of count is less than uh three then then there cannot be any triangle so that's it is equals to 3 then this one triangle that will be covered in uh in the approach so uh in order to find uh all the possible three elements that can be present in uh the array we can uh uh make use of for Loop and we can iterate over the array with one Cube complexity and find all the possibilities that we can have of a triangle like my first we can uh pick up uh six and four and then six nine six seven six four nine six four seven six four eight and then we can increase the G and then we can find the other possibilities with three for loops okay all right uh how will you check for the possibility if these three elements are consisting of a triangle sites or not how will you cut from that uh triangle sides you mean by this uh is it is there some equal to something else or like uh if you are taking c649 that it means that we have a triangle whose one side length is six one side is four and one side is nine so so that tree Loop idea was correct like you will you know just uh check for six four let us say you have just taken a six and then you will check uh for four and then you will keep on iterating for nine seven eight then you will a six is that that you will iterate for nine seven eight then seven eight right so that is there but how will you confirm that if we are making a side of a triangle using uh the Pythagoras Theorem that we used to have in maths okay so a Pythagorean theorem the Pythagoras term sorry uh I guess that helps us with right angle triangle but uh here the dragons need not to be right angle triangle all right uh so uh if you can help me with just what a basic property of a triangle is the angle must be uh 180 what is the property of the triangle depending on the sides uh it is sum of a plus b whole Square greater than c i I don't remember that uh foreign B is greater than C something like that exactly exactly so that is what we have that sum of two sides is always greater than the third side third side right exactly okay so you can use this property to check if these three sites are going to you know consist of a triangle or not is this clear yes yes yeah so maybe you can start doing brute force and then we will move to the optimized solution but first of all let us do this group hosting okay I'm just using this syntax of Swift language sorry language and maybe just you can explain it a little bit because I just don't have much idea about this actually it is in enumeration we will get the index and the value of uh the the iteration in our array so here we will get like 0 and the first value 1 and the second value okay okay so you are writing these three Loops right all right I get it foreign [Music] okay all right very good that we don't get the overlapping of the elements each time we get the unique pair and okay two side some value 1 plus value to it should be greater than okay foreign we get the values in six four and nine percent ratio because firstly we will get 666 that will not be supported because index 1 cannot be this index here due to this clause and then we will finally get this value 649 and we'll check six plus four is greater than 3 and then it can form triangle if it is greater than value X which is tight right all right value three oh well great so okay uh the district that you're doing you are not checking that if indexes are overlapping then maybe you can you know keep the index value of 6 constant and maybe you can start index two from four only is that is possible in Swift yes we can uh do it using five uh while loop and then we can start from the next one that can be easily done all right so yeah I mean this is also fair enough like if you are just checking if you are not overlapping okay so uh This Is The Brute Force approach and how much time will this take o n Cube and Cube exactly so what we have done here is we are just checking that if two side the sum of two side is greater than the third side or not and if every type this condition is getting satisfied we are incrementing the counter right yes so any optimized approach any optimized approach that is can we give you a bite oh yes if if we sort this array suppose after sorting uh we get four six seven eight nine and then and we will use uh we will first lock this and okay so after sorting what are you going to check I will um I will check for uh with four that which triangles can be done and if we are picking six and I am cooking from uh the last one first picking from the front one then picking from the last one and if four plus six is greater than 9 and then it will uh form the triangle and if it is less than 9 then ah I will decrement from 9 to 8 that whether it will form triangle or not or if it is less than 9 then I will increment from the left one to the seven one so that uh the greater number can be added and we can check if it is greater than the desired one exactly that's the profit solution so uh can you just write a pseudocode for this yes sure yeah [Music] [Music] thank you okay uh can you just help me with why locked is less that array dot count thank you okay that is the fixed or all right that is the first index value that you are considering that I am fixing then I will pick six and foreign it is less than then we will make front to go further understanding okay yes so if we find out uh that it is greater than our current then we will increase the counter that we are checking initially which is equals to 1 then we will also uh go through the other possibilities that 6 plus 4 can be greater than 7. so in that case we will decrease the count we will decrease the bank exactly exactly very correct we will decrease the back and in this case we will increase the front and when all this is done we will uh increase the logged one okay correct wait like are you done with this yes all right so let us just do a quick go through what you have done here is if you could just scroll up a little bit yes okay so uh can you just please explain what you have done yes in between so that we can have all the code at one page all that that is two pages okay just continue never mind so yeah yes what I have done is first uh let me write down the case four six seven eight first we logged uh fourth and then uh we will use this while loop and this logged count is less than one then another uh while loop we will come across and back is greater than front because I think from the back pointer uh contains uh five elements and we will check four uh plus six and nine if it is greater than 1 then obviously our counter is increased and our back goes to 8. we will check the another possibility of a possible triangle so 4 plus 6 10 which is greater than 8 so again we will increase the counter and go to the seventh one and four plus six uh greater than seven so there can be a one uh also one use case because it it's the largest element and the elements are decreasing if we can count how many elements are there we can direct exactly exactly directly increase the counter exactly means once you have once it is getting greater than eight then obviously it will be greater than 7 or 6 or any number which is lesser than that so uh you may can you can update your counter as directly maybe due to differences of the indexes that we have at front and back yes right so you can do it that way so yeah anyways that is not uh I would asymptotically TC is going to remain safe but yeah it's great you figured out the logic all right so okay that is what your code is doing and if the value is coming lesser than area at back then you are incrementing the front keeping the log constant okay great so uh what will be the type complexity of this code uh it will be less than 1 square because here will be like we are iterating and it's using one but it is not using uh o n it's less than one yeah but asymptotically we can say that it will take a n Square time complexity that's uh yeah anyways it is for Loop over two for Loops we are using so and uh you are using this sorting thing as well so what will be the type complexity for that uh I think uh it depends upon uh sorting if we are using uh any quick sort and much sort then we will like on square plus anything then it will remain when scare exactly okay like and the time complexity of any sorting algorithm which we standardly use what is the time complexity for that n log n correct great so okay you solve this question correctly so let us now cut to the feedback section just a secure all right humans so uh based on the interview like uh how uh how much would you rate yourself on the basis of this interview declare was not able to solve the first problem so uh five out of 10 because that was a simple one I don't know why I have not I was not able to get it uh my yeah I was uh thinking about something different and uh then the approach uh you said was quite different and I was not able to think about it and that's why I'm writing myself less all right so okay see what happened in the first question is exactly it was actually a completely logical question right so the thing there was that if you are not able to get that logic the exact logic that was being used then you know there was a very little chance that the question can be solved so uh what exactly was needed here is we were about to keep the track of the remainders that we have right we like you could have created a frequency map storing the remainder all right and then you can check that whether for every remainder are there is K minus r or not where K is the given integer right so for every uh value inside the map that checking could have been done okay so that was the main idea that I will strive to deliver so anyways you were not able to do it but all right you tried it right so okay that's fine and uh yeah the best thing about you is that you know you were able to consider the edge cases like uh you know when we when I gave you the first question so the first thing you did was you focused on the edge test case right so that is the important thing we must focus on the edge test cases because you know sometimes we just get wrong answers because for that so that was a strong point that we were having and the next thing is that uh you know even if we were not able to solve the question still you welcome you were confident right you just said that you want to switch to the next question so that is the nice thing about you so in the interviews like rather than uh you know just uh doing a question like we just get this intuition right that if we will be able to do the question or not right I mean that inclusion comes to us so in the interview if you are able to understand that uh you know I may be I will not solve this question or maybe I can't do it right at this moment so you can ask the interviewer to jump to the next question so that was a very good thing about you you just didn't keep you know wasting your time around that you were very clear about it that what you want and still you will come you were confident you were you were not nervous so that was the plus part about you right uh so moving to the second question that we have uh can you just open the doc file please yeah so moving on to the second question that we have yeah in that second question as well uh you were able to you know starting from the Brute Force approach or you were able to come to the most optimized approach so that was a good thing about you you were able to figure out everything so yeah that's the nice thing and this question you did pretty well right so you know 10 or 10 for this question everything went well with this question so there is no any complaints on this and also as I said you took care of the edge test case here as well as you mentioned that if the size is less than three so there will be no any triangle so you know so that's the plus point you were taking care of that stressed cases so 10 on 10 for this and maybe we can have five or six for the previous question because you know we were not able to reach to a final solution so that's how the session was and yeah you did really well I would say maybe just a little brush up of logic is required right your concepts are clear uh you are here on the part of data structures and your algorithm point is clear so that is a good thing and then you know maybe just we can brush up our logic a little bit and then you know we are good to go so that was my reviews of your interview so anything from your side uh it was great uh it was great interacting with you and uh uh yes under pressure and under someone's observation solving a question is uh something new and when you are alone so you are able to uh solve the questions and that environment is different so it was a very good environment for me to practice and it was a very good session and a very good feedback that uh you didn't demoralize uh the first question that I was not able to solve and you picked up all the pretty good things that I have done in that and with that uh uh it it's been a very good session actually sometimes happens you know this environment is new definitely you know just uh getting broadcasted and then you know getting interviewed in that way is like you know is definitely a different feeling but the best thing is that it was never reflected on your face that whether you are nervous or you are stressed or whatever it was it was never reflected on your face you just maintain your calmness throughout the session so that was a very good thing you were able to solve the question second question you just completely solved it in first question maybe you know there was just some logic that was missing so that's not the case so that was a pretty good session uh you know thanks for uh doing this session with us uh we hope you had a great experience and yeah uh anything else from your side uh no it's it was fine great so uh thanks Hemet for connecting with us and yeah we wish you all the best thank you thank you so uh yes guys here he was we had human with us and it was a great interview session I mean he was not able to solve the first question but uh because he was not able to get the logic as he said he was just trying to do something else and I was telling him to do something else so maybe right at that moment he was not able to grasp the concept but second question he did it completely so you know that was fair enough so uh any reviews anything from your side just as we saw he did well and also he was the best thing about he was that you know he was very calm and he was confident and as he said that he was nervous but still that was not reflected on his face so that's a great thing about him that he showed anything else from your side and um if any of you is interested to take part in these interview sessions then a form link has been provided in the description section and make sure you guys just do fill out that form and then you know you all will be getting chance to feature with us right we all will be interviewing you as well and we would love to do that so just please make sure that you are filling out the form if you just want to uh get featured in these interview sessions so it was yes of course working professionals are also eligible the candidate we had today is a working professional he's having a five years of experience and he's a great iOS Developer as well so you know anyone with just who just loves to code who just want to get interviewed for DSA is definitely eligible for these interview sessions so yeah uh I hope you all learned something from the good things that human shows human showed sorry right and uh also uh we just uh you you all just you know should keep practicing because sometimes it may happens that um easy question right brought you might not be able to solve at the moment if the Logics are not clear so for that just uh you know keep on practicing the questions keep on doing revisions so that will be of great help and thanks for connecting with us today we will see you soon in our next sessions and we wish you all the best keep up with the hard work bye everyone