Live Mock DSA | GeeksforGeeks

Key Takeaways

[Music] okay hello everyone a very good evening to everyone present here so uh we will be having a mock live interview session so let's wait for a few minutes so that uh the audience can join and then we can start foreign [Music] this is yeah so good evening everyone so let us begin today so this is a mock live interview um so today we have uh Akash Chaudhary with us who will be interviewing and um yeah hello Google yeah welcome to the streaming yeah and let me introduce myself my name is gaurav Marshall and I am a mentor at Geeks for geeks and today I will be the interviewer Okay so let's start then and uh one more information that I would like to share is that if you are preparing for your interviews and placements uh for your internships and placements and you would like to have your mock interview scheduled with any of the mentors at Deeks for weeks you can fill up the form link that is in the description and also you can fill up your interview experiences as well okay so this is an extremely great opportunity for getting yourself prepared for the interviews okay mock interviews are very very important if you are trying to prepare prepare for your uh internships and placements okay so uh let me share the screen with Akash so hello Akash how are you hi I'm great yeah you're great okay so let us begin with the interview then uh would you like to please introduce yourself to me and the audience present here sure first of all good off good afternoon and good evening everyone I am Akash Chaudhary currently I am in my final year of at Allen City Bhopal pursuing b-tech in electronics and communication engineering my tactical like my technical part include full stack app development you can say and my tactical uh skills I use uh is mainly about the back-end development which is node.js Express and posters and I also have multiple internship experiences and some hackathon experiences you can say so yeah that's that was about me that's very well across it seems that you have a well-diversified CV so uh let us begin with our questions then would you like to please share your screen yeah sure I think it's fair already yeah you can open a dog file okay so as you can see I have shared a doc file with Akash and I will be posting the questions there and Akash will be typing out his approach okay so just a minute let me share the question sure can you see the question there yeah I can say let me leave it out for you so basically uh in this question it is asking that you have been given an array of size n which contains an integers and you have to find the contiguous summary containing at least one number which has the maximum sum and you have to return it sum okay so as you can see that uh in the example if the array size is 5 and the input is one two three minus two and five the output will be nine okay because the maximum sub array is 9 as 1 plus 2 plus 3 minus two plus nine okay so uh basically there are negative numbers in the RS so you have to be careful with this okay so you can start um I think what I can do here is I can have a variable let's say current sum and the max sum which we have to return so the current sum will iterate through the array right let me just go with the example yeah so according to the example we have again some is equals to zero and switches 0 initially so what we can do like current sum related to the error like in the when it's at zero the current sum will be one then it will be added then at the next step it will be three and at the next step it will be six and with minus 2 so it will be 4 okay in in the case when the current sum becomes less than zero we will re like we will make it again to zero I should say this might be the right approach in case because like we need the maximum sum in case current sum is minus in is in negative then it might have like let's say current sum is minus 11 then the next element next two elements might be one and two but still the like the sum will be -8 of like we need to restart from here we need to restart the current sum from here such that it starts from 0 then it counts one and two as a new array new sub array that way we can get the maximum sum so like it's mainly that cadan algorithm is the approach good enough yes your approach is good enough can you write a small pseudocode and do a dry run children with a new example not with the example given already sure let's take some minus four [Music] three five so let's take this example now otherwise [Music] so what we are going to do is Grant some that's equals hello hi and that's before let's make just in case all the array like all the elements in the array will be negative we need the maximum negative number I think I think that might that might be a case so what I can do is just equals this one [Music] and if and some [Music] less than zero it will make you can cluster that's the approach what is it yeah yeah your approach seems correct I I am giving an example in the dock can you do a diagram of that example sure see I have placed a value here minus 2 minus 3 4 minus 1 minus 2 1 5 and minus 3. do a dry run with your code that you have written just explain it to me the first few iterations and then you can proceed yeah so here the current sum will be -2 and the minus 2 will be stored in rest first of all like in this step current sum like minus 2 will be added to the current sum and the dress will be updated and since the current sum is less than zero current sum will be resetted to zero so like it will be again zero four minus 3 current sum will be minus 3 first of all then we will check it with the response again the current sum will be zero as it is less than zero in case of 4 the current sum will be 4 it will be up it will update the rest as it is will be Max of rest common current sum and in the next step will add -1 in it so it will become 3 the current will become 3. our rest won't be updated as it already stores the four in the next step it will the current sum will become 1. and in the next step it will become two set it to become five seven so seven will update the response address variable and yeah at the end the currency will be fourth so 7 will be the answer is this is the match element stored in the address yeah okay very good uh I'm pasting the um the problem link on the uh doc just submit that problem and see whether this code gives the issue or not sure sure just a minute hmm I think you can see the link yeah I got it foreign address okay foreign okay everything is fine submit okay yeah it worked yeah okay yes that's very good luck so uh let's proceed uh to the next question okay so Akash uh do you know uh what exactly does it mean by saying that there is a cycle in a graph um yes yes I like whenever the the same the same element comes twice like same element comes again there might be the cycle in the graph okay there might be a cycle in the graph so um just to describe how will you if I'm let's say I'm giving you a graph so what would your approach that how can you find detect a cycle in the graph okay it can Traverse through the graph using BFS or DFS uh and if it is fine and we can Traverse through the graph and whenever like um the next element is visited whenever the next element will be visited and it's not the previous element of the current element in that like in that case right like in in case we have um for one element for one let's say node we have multiple nodes connected to it and then for any of the node which is already visited and it's not the previous node like we'll have to keep the track of the previous node so it is not the previous node and it says visited then we will say there is a cycle in the graph so yeah okay so how will you find that we will keep track of the previous node and we'll have a visit first of all we will do a traversal like uh let's say we can use um DFS or BFS both is fine okay I think so I'll go with DFS okay uh I want you to do with the BFS can you do a iterative approach sure sure write a pseudo code in the dock itself first then we will proceed uh I have already put up a starter function so basically you have a integer value V which contains the number of nodes for the vertices and uh adjacency list representation of the graph is given to you now you can proceed foreign [Music] [Music] I forgot like first of all we're gonna add a few since it is a BFS and of note um no okay and that's fine and we need to have a track of the previous the previous node so in that case we're gonna have a queue let's say [Music] yes that's our size V [Music] m let's say we for every element we're gonna have some previous note this is the first element then the previous node is -1 so that's why I have initiated with a minus one let's say we like we need a visited [Music] what I think [Music] and positive foreign node obviously and yeah so hmm let's just do the BFS for all the elements [Music] Plus thank you the current element true and let's do the BFS call here yeah this is size three I could say first visited and I so in base this is true then we will return can you tell me what exactly is your function uh cycle helper is doing this is for BFS we can name it PFS okay okay this sounds better okay so uh basically uh you have declared a queue and uh what will you do can you describe the working of DFS sure so like how PFS works like um a breadth first first of all for every level it searches like if we have the current element and it will go for all its connected all its connected elements and add it into the queue and until the current level is traversed like until the current level is completely traversed it won't add the next level like it just put it into the queue and it won't Traverse through the next level so that's mainly about the queue and the current size of the queue will Define the current level so that's that is how PFS will work and yeah in that case the same the same thing as I told in BFS if the let's say if the connected element is not a previous element but it's visited in that case we're gonna return it is a cycle so yeah that's how PFS will work here this cycle BFF Will Will just like return in case we find a true I need to seconds I have started the coding I think it's well written there is a cycle in current like current connected component for the current connected component if there is a cycle so this this function will return true [Applause] foreign like in case we have a cycle in the current connected component it will go for all the connect like this for Loop will go through the this folder will go through all the connected components like four so if that product is going across all the connected components then why it should be that first you are checking that it is true or not if it is already visited then you should not using it right okay right right right if it's not visited yeah if the current resident is false sorry okay so then we will return yeah so this will be the approach and in case all the connected components are not a cycle then we will return a false so okay this function is the key com key function in this question so we are searching for cycle and current connected component so how we can do this is by like using the queue like just let's just make the current element current node as we should we should add it in the queue each note so we have added an the queue so let's start the while loop okay I should watch size zero or yeah all right so this while loop let go it will actually iterate through the queue and until the size like the size of Q is let's just get that top and I think here and and it was Q dot the front element because the front element will be something will go through it so that's a little pop the queue and I think that will go through all its connected components we are going through all its connected components and in case we find um something which is already visited and it's not the pattern [Music] so that's that's what we are trying to find more let's make it nothing okay okay I need some yeah for Auto current so what current will go so current will go through all the adjacent nodes of the that parent node which is which was in the front of the queue so that's that's what will the current will do and as I said the logic the main logic lies here like if if it is not visited first of all if the current [Music] method of current false and we will simply do the PFS thing that we used to do like adding like making the current visitor first of all that's true push it into the queue push the curtain and referrals set its parent like the previous the parent into the previous note like the parent of the current yes no thank you of that current will be the parent which we have stored as the front of the queue so this will be in case the current current element is not visited else if it is visited [Music] If the parents parent of the current node is not the parent I'm sorry parent previous node of the current is not equals to the current parent then we will find like we are going to consider that we have found this cycle yeah in case the whole component is is searched like when the while loop ends when the queue is empty then we can consider that whole like all the component all the connected component is scan like is traversed so we will return false in case we haven't found found any cycle so that's that's a thing yeah Yeahs okay so just a minute let me check with few things okay uh on an overview your code seems correct to me so uh can you explain it to me that uh why are you initially declaring uh the previous node with all the values as minus one because in case like the parent there is like this is the first note in case this is the first note uh the parent is not specified we we can also like we uh like some elements should be there so that's why I have selected minus one because in case the limit it depends on the concept zero also yeah yeah right right like it depends on the constraint too like in case 0 is um right zero can be any node so that's right minus okay yes zero can be any node so it's better to take a negative number okay um one more thing it was it was somewhere difficult to drive around this question so that's why I started with coding part yes yes yes I understand that okay yeah your code looks uh good to me so uh I am by pasting the link of the uh question on gfg Portal you can just submit the other code and search for this correctness sure [Music] yeah it's pasted [Music] [Music] [Music] [Music] [Music] [Applause] [Music] anybody [Music] just [Applause] [Music] [Music] hello Akash any issues yeah yeah this like the document was not working properly foreign cycle okay I said is your turn yeah see foreign should have been looking that [Music] we just thank you everything [Music] just a magnify the screen a bit so that I can see this possible may help yeah sure so what exactly is um like it's showing Declaration of adjacency as array of references while again okay no matching function called this cycle BFS YouTube check the parameter list and maybe you are missing something hmm yeah great status oh sorry sorry I final yeah this is working so K5 water to okay what can be the issue here in this case or four it's two for minus two okay it's showing that there is a cycle that there is not any cycle okay for one it's hmm I think we need to reset the visited every time does it work no [Music] no okay [Music] four two three like that editors in this phase like four four two is the connected component so 2 is marked as long visited but for one again it comes to another two and there it's returning a cycle [Music] thank you like why is your code outputting one it should be zero right right right it's showing that the cycle like I know there's a reason like for four the connected component is two and two is set as like two is made like visited true it just pushes in this else as the previous node of one is not equal to so basically uh yeah there is a mistake basically so you have to check means okay uh if if it is a visited node then you have to check whether it is the parent of the node I am not okay so small error okay if it is visited then it is images hey that's what I am doing here uh yes if the previous node is not equal to its parent node should return true [Music] yeah as you are doing that only uh can you please check with the indexes means uh I think in the question uh the nodes are given in a zero based indexing or one based indexing kindly check that and your uh yeah it is given zero based indexing okay then I don't think there should be any issue okay okay right and yeah it is can make a like we don't need a set here like we can add a set of parent notes but um I think this is the right solution I've yeah is there any changes you would suggest uh just a minute yeah I would like to you to suggest that uh what you can do here is uh do not maintain a previous new kind of vector just uh uh just put the parent for example let's say uh whenever you are going across any particular node just keep from where that node has come okay if the node number two is coming from one it means I just told the uh in the queue itself okay so maybe that type the concept will both be same but the chances of error decreases when you do it in that way Okay so Android thank you okay let me do something else yeah yeah right right so here I lost the oh okay yes let's submit breathing okay yeah so here this was yeah yeah it worked yeah okay that's very well yeah so uh we have uh almost uh come to an end of the interview and now I will be sharing my feedback and it's for akasana all the uh audiences who have joined with us so why exactly was there an error at the last point keep the dog shared keep the dog shared right okay yeah sure [Music] so like it was mainly due to lack of I think uh try it and I let's say he had to do it again so oh this is a DFS algorithm and uh there's only one standard set of algorithm and you don't have to do a dry run to possibly make it understand uh I guess you know uh you have declared two variables the first one was current and the next one was parent so you kind of uh messed mixed the both the variables while you are writing the if condition right okay so like uh just recording to me I think that uh basically let's say whenever you are on any node let's call that node uh just name the variable as node and whatever the node uh previous to that node let's call it the parent of that node and whatever node that will come after to after that note let's call it adjacent of the node okay if you would have maintained a variable um like nomenclature in this fashion the present note it's parent and its adjacent node okay so in that case maybe uh it would be better to maintain the variables variables the flow of writing the code you would not have mixed up but nevertheless uh both were correct it was just from my point of view okay okay so although this is not a very good yeah not a very great mistake or anything like that okay so um so the next thing that I would like to say was in the first question the first question that I gave you was uh it was you have to find a sub array which contains the maximum sum okay so in that subject negative numbers are also present so uh basically what I wanted to know was what I wanted to basically hear from you was that you go in a step-by-step approach basically that is you first do a Brute Force approach when you try to move across all possible sub arrays by uh doing a nested for Loop and then try to find out the maximum value okay but you directly jump to the Guardians algorithm okay and uh one more thing in interviews what happens here is that interview doesn't want interview doesn't actually needs to know the name of special algorithms like it's Guardian algorithm or anything like that like uh maybe the interviewer may ask you but you're not supposed to say uh once you read the problem you're not supposed to directly say that this is a Guardians algorithm problem okay yeah it means that you already know that stuff and uh basically so what the interview basically looks is that how you are approaching the problem from the uh Brute Force approach to the highly optimized approach and you're not supposed to directly jump to the highly optimized approach okay so uh you would have done a bit of improvement there and overall uh according to me your interview was quite great you were able to answer both the questions and your communication skills were also very apt so yeah so overall it was very good and for the audience uh who have joined with us today so uh this is for uh all the students who are preparing for their internships and placements if you would like to have an interview scheduled with the mentors at Geeks for weeks you can fill the form in the description and we will have it arranged okay and Akash do you have anything to ask um no not okay okay so uh Akash tell me how do you feel how do your interview I think like oh it was great like the questions there was some like these questions were famous questions which I have practiced so yeah I knew the like the approach approach was mine so that's why I answered real quick but I think in case the question might have been harder like um so do you think like if the companies like Amazon Microsoft these companies ask harder questions than these famous things yes yes uh Amazon and Microsoft do ask another questions yeah so uh basically the like I have personally given the interview of Amazon and uh in that interview basically I was asked two questions one was involving a multi-source VFS and one involved a combination some dynamic programming questions so uh both questions were uh medium to Heart category foreign not related to data structure that we know like for example uh like lru lfu cache or something like that or writing a linked list part so those questions are kind of they ask so the the purpose of the mock interview was that uh the most important part in any interview is that communicating your knowledge okay so everyone is well prepared for the interview but sometimes students lack that they are not able to effectively communicate to the interviewer and this becomes a deciding factor for the whether they get the offer or not so practicing mock interview will basically help you to channelize whatever you know in the form of English in the English word so that you can convey to the interviewer okay and uh overall your interview interview was great uh from uh knowledge point of view you were perfectly up and uh communication was also good and uh just uh as I said uh first you have to basically uh tell a Brute Force approach and then finally uh move to the uh optimized approach okay so yeah that's it from my side yeah okay and um yeah okay I hope you enjoyed this session and I hope that everyone who joined this session live over you found it very very uh helpful and I would like to just say once again that if you would like to have our interview scheduled you can just fill the form in the description yeah thank you very much Akash thank you everyone for joining us today have a nice day ahead bye