DSA Mock Interview | Amazon SDE Interviews a TCS Software Engineer

[00:00:00]Yeah. Hi. Good evening.

[00:00:03]>> Good evening, ma'am.

[00:00:04]>> How are you?

[00:00:07]>> Fine, ma'am.

[00:00:08]>> Great. Okay. So, uh the recording of this mock interview will be shared over the YouTube. Do you have any concerns on it?

[00:00:15]>> No, ma'am.

[00:00:17]>> Okay. Uh can you please introduce yourself?

[00:00:22]>> Yeah. Actually my name is Jam Mali and I have done my BTE from Krishna Engineering College Gazyabad and during my college uh I have I had given uh NQ exam thesis and exam and I had cleared that exam in a digital and then after I have joined TCS in a nontechnical project due to because uh they mapped forly to that project. After that uh I have joined uh AI team in medical uh team where I have done many uh PC's that is proof of proof of concepts. I have made laboratory uh agents. Currently I'm working on LLM parsers where we are uh making parsers for uh laboratories uh results.

[00:01:22]>> Yeah.

[00:01:24]>> Okay. So uh can you share your screen so I can start sharing the questions?

[00:01:31]>> Okay.

[00:01:33]Uh >> year 2020 uh Your graduate year is >> okay four from where I can share my screen. Okay.

[00:01:48]>> At the bottom you have an option.

[00:01:50]>> Oh yeah.

[00:01:52]>> Okay. Uh you can open some ID.

[00:01:56]>> Okay. Is my screen share now?

[00:01:59]>> Yes. Yes. It's visible to me.

[00:02:04]>> Okay.

[00:02:08]I think >> yeah, >> you can check the chat of the zoom.

[00:02:16]>> Okay.

[00:02:52]Uh I'll read the question.

[00:02:57]>> Have you open some ID?

[00:03:01]>> Yes, it is.

[00:03:03]>> It's not visible to me actually.

[00:03:06]>> Yeah, I share the screen.

[00:03:10]>> You have to share the entire screen.

[00:03:13]Yeah, I've shared on some >> Can you go to some ID?

[00:03:20]>> Okay. Okay.

[00:03:25]>> Is it visible now?

[00:03:27]>> Not yet.

[00:03:29]We're not sharing it properly. One second. Allow.

[00:03:32]>> Um there is a allow share screen and there is allow to share window.

[00:03:36]>> Yes, there is a option for the entire screen. Right. when you have shared there is option first option >> is it now available >> yes I'm able to see me can you go to some ID now ah it's visible now >> okay great okay okay so okay in the Okay.

[00:04:13]So there's a proper constraint.

[00:04:17]Yes.

[00:04:20]Can I uh write my uh for example some part on my uh copy or I should write on here?

[00:04:27]>> You can write here only it >> only. Yes.

[00:04:30]>> Okay. Okay. Okay.

[00:04:34]>> [clears throat] >> So for example if there is an array that is unsorted we have given already 10.

[00:04:44]Okay.

[00:04:48]Okay. So before this constraint if we go a simple method. Okay. A simple method.

[00:04:56]So there will be we sort an array 4 5 7 and 10. we will go sequentially and we will check if the past element is equals to that partic uh one uh minus. So it will be like uh nums of i nums of i equals to nums of i -1 + 1. If it is then I will do count ++ or else I will count equals to zero. Okay.

[00:05:33]So it is a simple method I think and it will be time complexity of a big of n login for sorting plus big of n on a loop and sc will be big of one.

[00:05:55]Yeah, but we need to solve it in a gig of n and would be big of one.

[00:06:07]Okay.

[00:06:20]Okay.

[00:06:25]So I think uh if there is a uh number that is uh not unique so it will not be a problem because you want a length of only a unique number sequence I think.

[00:06:39]So >> it's not unique number sequence. It's majorly consecutive elements. Right?

[00:06:50]>> Uh consecutive elements. For example, if there is a four, five, five, six. Okay.

[00:06:56]But you want a consecutive elements. For example, four, five, six. I think you want this type of sequence. And for example, length. You want a length. So it will return three. we go with this above example.

[00:07:12]>> So you can assume that you will not have the duplicates for this question.

[00:07:16]>> Okay. Okay. Okay. Okay. Okay. Since we have a no duplicate here and for example this is the sequence. Now what we will do here is H.

[00:07:52]Okay.

[00:07:55]100.

[00:08:04]One How to get this going?

[00:08:48]What?

[00:09:04]You can use some data structure to store it.

[00:09:08]Yeah.

[00:09:17]So what Don't for What I'm thinking here is uh all those And don't think in the terms of hashing.

[00:10:56]No no no no I'm >> you can try to think in the terms of hash set something like this >> yeah this uh that's why I mark this as a hashet but I'm we will not be able to do a uh sorting stuff so uh I'm thinking of You can speak whatever you're thinking.

[00:11:31]Oh actually I have uh think in in a headset stuff for example if there is a number one and I will go with uh till y loop till y loop for example till y loop >> until I don't find u this uh for example this is element okay so there is a element one until I don't find an element plus one >> then I will go count count >> and if I if I uh over out if I don't find any condition element + one then I will be breaking that stuff and storing that max and go further but now I'm stuck here because While checking the element plus one, do you not think so that you need to store an hash set also? So the next time when you are coming with the same element, so you should know that you have already calculated the length of that part.

[00:12:44]>> Yeah.

[00:13:06]But but if you think about storing uh like series of for example four comes one first.

[00:13:19]Okay.

[00:13:21]48 2 1 Okay. 4 5 6 7 Okay.

[00:13:28]Uh I'm thinking Okay. Okay. Okay. Okay.

[00:13:32]I got a solution. I think for example, if there is a four, for example, we had to store in a for example, this is a headset. It is not sorted. It is unsorted form. Okay. The element come that is four. Okay. Four came. I will loop till minus minus one one time minus one. Why loop minus one - 1 - 1 I will got a count here. Okay. For example, count ++ count ++ for example 4 3 2 1 sorry 3 2 1. So I will got a count that is three. Okay. I will go another loop that is count plus oh sorry plus one till I got a condition fail. Okay. So there is a count uh ++ again. Okay. So there is will be count plus+ there is a count ++ again for for example there is a 5 6 7 also. Okay. So 5 six will also be taken out. Okay. and I will out from this headset.

[00:14:43]Okay. So next time for example one games and I check in headset if it is not present I will not go with that loop this loop. So this is a count three and there is a 5 six not there. So there is a count no found here but still there is a three here. Okay. So at last there is a four also. So I will manage to have a here is max equals to max count max. Oh sorry it's a count + one.

[00:15:19]I think this algorithm will work here.

[00:15:29]>> No.

[00:15:32]Can you do the dry on one more example?

[00:15:36]Okay.

[00:15:38]Okay. For example, this is a question.

[00:15:51]Okay.

[00:15:52]>> H >> you had said there is no unique number.

[00:15:57]There is a unique number only. So for example there is 0 three for example it is a half set. Okay.

[00:16:05]No. Oh, okay.

[00:16:06]>> You can remove one zero from this.

[00:16:08]>> I will I will I will I will loop uh no issue. No issue. I will loop through it.

[00:16:15]There is a Okay. So, I will loop through it.

[00:16:20]I will loop through the array because if we remove het then it will be a indexing problem. Okay. So, we'll loop through array.

[00:16:29]>> Okay. So, let's suppose you have add all the elements into hashet. Okay. Till now we are done. Let's come to our next part.

[00:16:36]>> Yeah. Till now we are done. Okay. Okay.

[00:16:38]Okay. So we found a element that is zero. Okay.

[00:16:42]>> Okay. So we will loop while while this uh element zero. Okay. This over here while this will be le one. This will be le let take le. Okay. No issue by the limit.

[00:17:02]Fine.

[00:17:02]>> And there is a count.

[00:17:04]>> Okay. There's a count. Okay.

[00:17:06]>> So until until uh we could not find minus minus le. We could find minus minus le. We will loop through it. We will loop through it. We will count. We will count. Okay. And at the same time we will remove that element. For example minus count count plus count count. Oh sorry minus minus le plus.

[00:17:31]Can you talk in the terms of numbers rather than plus+ and minus minus >> because you're doing the dry run writing I'm not asking you to write the pseudo code I'm just asking you to do the dry run >> okay okay ma'am okay so there is a zero okay >> okay >> zero came >> zero asked is there uh minus minus min - zero of is minus one okay so we will not found minus 1. Okay, no issues but count is zero now. Okay, next time we have we pass the same zero to next loop but for the positive conditions. For example, there is no minus one. There is no minus one. Okay, is there any one? Yes, bro. I had found a one. So I will delete this one here and I will count ++ and hash set h dot remove that le++ at the same time. I will remove that one.

[00:18:39]>> If you okay then I will again go with it two.

[00:18:46]Okay bro I had found a two bro delete it. I will I will go with one step more.

[00:18:52]Okay, bro. I found a three.

[00:18:57]Okay, bro. I found a four. Okay. Oh, sorry. Yeah, bro. Delete it.

[00:19:03]I delete.

[00:19:05]So, delete it. Okay, bro. Bro, I found a five. Okay, bro. Delete it.

[00:19:12]As it is 6 7 and 6 7 8 We'll delete.

[00:19:18]And at last we got a for example counter.

[00:19:23]I think it's seven. Okay. But till now we had not delete a zero. So we will delete zero. We will uh maximum we will do a maximum with count + one because zero is deleted now. So we had done this for in that way. And for example, for example, you got you got a three year.

[00:19:48]Okay.

[00:19:48]>> You can you can start writing the code.

[00:19:51]>> I got it.

[00:19:54]>> Okay.

[00:20:21]Okay.

[00:20:23]So we will take an H set of integer.

[00:20:34]You can take a variable as Thank you.

[00:21:14]Now we will loop through this length and uh we will take element that is nons of i And uh first what we will do here is we will uh loop this while uh and first we will check if this particular element is present in a heter or not. If not then we will continue.

[00:22:06]If Sorry this not only continue.

[00:22:27]Okay.

[00:22:32]If so if we found any + 1 while L + 1 is present we will look through it. Okay. So it will be like count + count equals to zero max is max length and uh pound ++ uh unique value dot remove and uh [clears throat] uh we will count we will okay I've done it and uh again we will assign this variable to this because for minus loop because I ++ and L minus one value of content elements very first. Okay.

[00:24:28]Count and uh at last we'll do max equals to math dot max of count + 1 comma max. And at last we will do remove the nons also because we are done with it maximum it is maximum variable.

[00:24:58]Okay.

[00:25:01]Okay.

[00:25:03]And if we are talking about the time complexity of this, it will be looping through each element.

[00:25:16]But if you see a many of the student fails during that there is a two loops but it is only looping each element once because there it is also removing that stuff. So it is it will be a time complexity of big of n and space is space complex sc of big of n because we had taken a head and if we uh go with the length I think and after each time we need to put count equals to zero.

[00:26:03]Yeah, >> if you're done, you can run this code.

[00:26:07]>> Yeah.

[00:26:10]Or this three.

[00:26:34]Oh, see ++ L + 1 and nums are again minus one pound plus and we are rem but it is zero.

[00:27:23]There is l + one need value contains.

[00:27:53]1 2 3 4 5 6 7 8 9 but zero on It's okay.

[00:28:32]Oh my Still you can do the dry run on your code. You will get it where you're wrong.

[00:29:05]Yeah.

[00:29:13]I'm giving you five more minutes. You can do the dry run on your code and fix it.

[00:29:18]Then we can move to next question.

[00:30:06]Just listen.

[00:30:18]Okay.

[00:30:28]Okay.

[00:30:36]0 1 Okay.

[00:31:16]Yeah.

[00:31:27]Okay. Uh let's move to question number two.

[00:31:31]>> Sure.

[00:32:09]You can you can copy paste the input and output also.

[00:32:14]>> Okay.

[00:32:19]>> Above also you have example one two block in front of you with four circular beads. Each wheel has a 10 slots.

[00:32:37]element of 0 to 9.

[00:33:24]Okay.

[00:33:34]Okay. Uh what we desert in or constraints >> sharing it.

[00:33:46]>> Okay.

[00:33:47]>> You can also copy paste the other examples as well.

[00:33:52]>> Okay. Sorry.

[00:34:23]>> [clears throat] >> Okay, this it will be easier or just if it will be an asset. So we can check posly but before that we need to >> can you speak loud?

[00:34:44]>> I can.

[00:34:46]>> Yeah. Uh actually I'm thinking of putting this dead ends in a hasset so that it will be fast to check but before that we need to see. Yeah. So for this uh dead ends we can make any so move three times.

[00:35:43]>> You can go through the input and output if you haven't yet.

[00:35:50]>> Yeah.

[00:35:53]0 1 2 0.

[00:36:00]Okay.

[00:36:23]I'm thinking of one thing >> for example if we because it is a for example step first search approach like something because at each time we have a four options and we can think of any chain for example if you want to do it as a one if you want to do it as a one or next time to make it a true.

[00:36:51]But uh DFS be like how DFS will work here.

[00:37:09]Actually I'm thinking of moving it each lock one time up and down. But uh it can be a very high time complexity.

[00:37:23]But uh >> because if you will move let's suppose from we'll take it as a 0 0 you can move to 1 0 0 0 then 2 0 0 0 then it will go right.

[00:37:37]>> Yeah. For example, if we go, >> for example, this like 1 122. So it this one >> will go back to zero.

[00:37:50]>> But making that stuff can can be a problem. So DFS can be with a high time complexity of that. So I'm not agree with that first thinking about that. But after seeing this example, so it can be a problem.

[00:38:08]>> And also uh DFS can't guarantee that the first path is the shortest path, right?

[00:38:15]>> Yeah. Shortest path will be like >> cuz you need to find the minimum moves.

[00:38:22]>> Ah minimum notes. Oh yeah, minimum moves. So >> and you also have the dead ends. If you reach there, you can't move forward.

[00:38:35]>> You can think of a BFS type.

[00:38:42]>> Yeah.

[00:38:42]>> Yeah. Yeah. You can think of BFS.

[00:38:45]>> I can think of a BFS type.

[00:38:49]If there is 0 0, we can do any one of a step to a minus one. I'm thinking of a this approach VFS approach uh for example as a shortest part we had think about so + one + one + one + one >> but uh okay every time it go for example it is a 9 0 0 0 and 0 9 0 0 and just like this eight stops H >> each time in a queue.

[00:39:45]>> Do you think that we need to move all the ones at once like all the zeros to one in one occurrence? Do you think so?

[00:39:57]Or do we need to take it one by one?

[00:40:02]Like let's suppose we have 0 0 0 right and then we are moving to 1 0 0 0. This would be your next occurrence. You can't move all the zeros to one.

[00:40:15]Am I audible? Right.

[00:40:20]Hello.

[00:40:23]You're not audible.

[00:40:33]Not yet.

[00:40:43]Now audible.

[00:40:44]>> Yes. Now audible.

[00:40:46]>> Yeah. So uh what I'm thinking here is uh but so if we don't take this what actually I'm taking this eight stuff because we at each loop we need to go to we might go to minus one also. So for example this 1 12 02 we might go to 020 also. So that's why I'm thinking about this eight eligible criterias on each Q stuff Q.

[00:41:32]>> Let's do the dry run and see if it works or not.

[00:41:41]Uh so dry run will can be a very huge for this for example >> we can start something 0 0 >> 0 0 okay then for example I'm going through this only okay stuff for example at e at next step I got a 1 0 0 because I add + one here add a single this okay at another time stamp at a next time stamp I am adding + one to this stuff.

[00:42:17]So it will be like 1 1 0 0.

[00:42:21]>> Okay. And then again to this second and the third time third third time step I'm rotating this second lock. So 1 2 0 0 at another time step I'm moving for example there is eight uh stops okay 1 2 0 1 and >> tell me one thing one thing >> okay >> first you are moving first lock this is fine then you move another lock like the basically indexing w actually at each uh for example time stamp at each time stamp I will loop this eight For example, this is -1 -1 -1. So this is -1 - 1 - 1 uh and add in a q. For example, it is 0 0 0. Okay. So it will be 9 0 9 0 0 0. And it will be add in a q for the next time stamp. Okay. And for example, if we are here, so it will be like 1 0 0 0. it will be added to a same time stamp but with a different uh in a in a same queue but in a same time stamp. For example, it is 9 0 0 0. uh next time it will be 0 9 0 0 and for this eight step I think it will be a fifth or sixth step it will be like uh 1 0 0 0 and and at each time I am putting it in a hash set so that if something coming again it will not add in the particular queue.

[00:44:11]What would be the time and space complexity for this?

[00:44:17]So it will be a all the numbers between 0000 to 99999 between all the numbers because we are having a hashet and it will storing all the values that is only unique and it is also uh uh checking a visited stuff that if something coming again if some value is coming again for example it is like 1 12 0 0 is coming again then it we will not put it in a que.

[00:44:53]>> Okay. So you will mark something as a visited like that.

[00:44:57]>> Yeah. We will take an visited array. For example, it is 0 0 0. At the next time we will go with 1 0 0. In 1 0 0 0 there is a minus one back loop also for this one log. So if it is coming back but we had said that it is a already visited and if there is a deadlock we will not uh go for this eight loops we will continue that particular stuff. For example it is a something like 00002 is a deadlock. So we will not go for that eight loops because it is a deadlock.

[00:45:29]You can you can't move a lock >> minus one plus one.

[00:45:35]So I think uh of that stuff.

[00:45:38]>> Okay. So you can start writing the code now. I >> I think I'm good with it.

[00:45:44]>> Okay.

[00:45:46]>> So okay.

[00:45:52]Okay. So okay we can write a code now.

[00:45:58]>> Okay.

[00:46:00]So we will take a Q of integer Q equals to should be a link test.

[00:46:12]Okay.

[00:46:14]So and also we want a hset to check deadlocks asset of integer deadlock new asset O and I N. Okay I not put in that log here.

[00:46:54]So we will have a catalog here log.

[00:47:10]So for that add dot add this I don't know why this error is occurring here.

[00:47:29]Okay. So we will add a cube that is with a 0 0 0.

[00:47:50]Uh okay. But uh the issue is how we will decrease that stuff.

[00:48:06]See put a string put a string here.

[00:48:21]But I think Sorry for the auto partition data log less than length I ++ uh the reds of I do is empty.

[00:49:23]Okay.

[00:49:25]So there will be a because we want and enter time to zero and uh in size we'll have a dot size.

[00:49:45]We loop through it for J = to0. J is less than size.

[00:49:52]J ++ and at each time we will uh adding a we will remove remove equals to remove element that is Q dot remove it is a string.

[00:50:29]Yeah.

[00:50:30]Uh for this we'll have a visited array boolean as set of boolean that will handle the visited stuff string string.

[00:51:18]We remove a element.

[00:51:22]We will go through a group of minus1 and + one.

[00:51:34]So next of 0 0 0 but 4 in = to 0.

[00:51:53]Okay.

[00:51:56]What's zero is less than 4 I ++.

[00:52:09]So at this time we will add we will change that particular character in a string. So we will take a care at CH equals to if position.

[00:52:32]>> So we will have a remove le dot care at I.

[00:52:41]Okay. So we will add a stuff. So I think uh adding care will be like uh care. Next uh will be like ch uh but I think it will do me int of ch + one.

[00:53:10]Uh I think it would be a care uh end of care actually I'm confusing at that part uh but yeah uh if we got then we will uh Q dot header Uh uh string will be changed here is string change will be remove dot uh replace but I think there can be a less like think uh I think instead of going into care if you can take a array that would be easier for you >> to writing a code >> anyways it's up to you but just a suggestion >> okay no issues I think That would be a great idea to split an string to an array and then adding stuff. Okay, >> that would be easier for you to write the code.

[00:54:47]Yeah, I think so array and uh we can have a remove le dot split split.

[00:55:16]Um it's fine. I think I'm good with it because we are out of time now.

[00:55:21]>> Okay.

[00:55:21]>> It will take I think 10 more minutes. So let's come back to your feedback. Now you can stop sharing your screen if you want.

[00:55:32]Okay. So there are few things which I have note down. First is you can u concise your introduction like you should know what you are speaking. So your introduction should be fixed. like let's suppose if you have some project so you should know okay this is what I need to highlight or this is what might be not required so you can little bit work on your intro part second thing is uh whenever you start reading the question you are good with your technical skills there is no doubt but the thing is key you need to speak loud >> so other person should know okay what you're thinking right >> I think apart from these two things you can third thing is the time management you're already good with it but if it is possible you can just have a timer and whenever you are trying the questions so you can just manage it okay I don't want to give more than 20 minutes because in interview you need to explain also you need to dry dry also so that also take 5 to 7 minutes >> so writing a code won't take more than 7 to 8 minutes you can have 20 to 25 minutes like 20 minutes per question I think that is more than sufficient which you can give while practicing apart from this I think you're good with acting.