Python Interview with a FAANG engineer.
We helped write the sequel to "Cracking the Coding Interview". Read 9 chapters for free
Missing Ranges & One Edit Distance
Watch someone solve the missing ranges & one edit distance problem in an interview with a FAANG engineer and see the feedback their interviewer left them. Explore this problem and others in our library of interview replays.
Interview Summary
Problem type
Missing Ranges & One Edit Distance
Interview question
The first problem asks the candidate to return the shortest sorted list of ranges that cover all missing numbers within a given inclusive range [lower, upper], given a sorted unique integer array. The second problem asks whether two strings are exactly one edit distance apart, where a single edit is defined as an insertion, deletion, or replacement of one character in the source string.
Interview Feedback
Feedback about Rocket Centaur (the interviewee)
Advance this person to the next round?
No
How were their technical skills?
2/4
How was their problem solving ability?
2/4
What about their communication ability?
3/4
Communication: He was engaged throughout the interview and communicated his thought process clearly. He successfully solved the easy problem with an O(n) solution. Areas for Improvement: He should focus on improving his coding speed and problem-solving efficiency. He attempted the medium-complexity question but was unable to complete it within the available time. For the One Edit Distance problem, he initially proposed a dynamic programming approach, which added unnecessary complexity to the solution. Advice for Future Interviews: Focus on improving coding speed and quickly identifying the simplest optimal approach. Aim to complete easy questions within the first 20 minutes and medium-complexity questions within 20–30 minutes, leaving enough time to test the solution and discuss edge cases.
Feedback about Verdant Goblin (the interviewer)
Would you want to work with this person?
Yes
How excited would you be to work with them?
4/4
How good were the questions?
4/4
How helpful was your interviewer in guiding you to the solution(s)?
4/4
Interview Transcript
Rocket Centaur: Hello.
Rocket Centaur: Hello, how are you? Hey, I'm good. How are you?
Rocket Centaur: I'm doing okay. I hope you're having a good day so far.
Rocket Centaur: Yeah, so far so good. Thanks for asking. Um, so this is a data structures algorithm coding interview, right?
Rocket Centaur: That's correct.
Rocket Centaur: All right, uh, we can get started. Uh, so what is your language of choice?
Rocket Centaur: I would pick Python. I would probably choose that here. Yes, I would go with Python 3. Yes.
Rocket Centaur: Okay. All right. Um, so are there any specific companies you are targeting for so that we can, uh, change our coding?
Rocket Centaur: Yeah, nothing, nothing specifically. I'm just doing this as to— but it's been a while that I've done some coding exercise. So it's been like more than a couple of years. So yeah, just, just getting prepared for that.
Rocket Centaur: Okay, let's start with the brief introduction. Normally I provide feedback on the introduction as well. So why don't you start introducing so that we can get started?
Rocket Centaur: Sure, sure. I have around like 16, 17+ years of experience. I started working in like 2010, '11. Initially was a Java developer, backend Java developer, and A couple of years back, and in 2023, that's where I moved to ML AI space. So since then, I was an ML engineer, then I got into AI agentic automation. Yeah, that's, that's a whole thing about my, my tenure. Recently, I've been, you know, doing lots of automations on agentic with LangGraph and LangChain. Um, yeah, that's, that's in precise about me.
Rocket Centaur: Okay, all right, sounds good. Uh, so in this interview I'll be asking 2 questions. Uh, one is like, you see, [REDACTED] Easy and [REDACTED] Medium. Uh, so if you solve those 2 questions, I can go, uh, go with one more question as well. Makes sense?
Rocket Centaur: Sure, sure, perfect. All right, um, after I completed Sorry, no, no, no, I said that I would, I would try to complete it. I don't know how far I can do, but yeah, yeah.
Rocket Centaur: All right, so should I paste the question here?
Rocket Centaur: Yeah, yeah, that should be fine.
Rocket Centaur: I don't know what is a comment in Python.
Rocket Centaur: Is it—
Rocket Centaur: so you see me, right?
Rocket Centaur: Yes, I see the example. Yes, I see the example. Oh, I, I think, right, probably I think you pasted in the wrong window. I think that should be put in the, in the file where—
Rocket Centaur: Oh yeah, on the left side.
Rocket Centaur: Yes, yes, yes.
Rocket Centaur: So I'll just put like this, that way it will be easy for you. OK. I'll remove you. Oh, I can't remove. OK, you can, you can go ahead and read the question.
Rocket Centaur: Array numbers, all elements are within the inclusive range. So before that, just, um, okay, I just have issue with all this red line and, and yellow line. I'm just getting like, I would see what is the, um, uh, one line to comment, uh, to all these things, that would be helpful.
Rocket Centaur: Uh, well, I, I'm— I think you will be writing code on the right side, right? I'm removing those, uh, lines everything.
Rocket Centaur: Oh no, I, I would be— no, so I— that is the execution layout. Like if I run, you would see, uh, so it would be still on the left-hand side, I guess.
Rocket Centaur: Okay, so, uh, what is the, uh, Python, uh, comment, blog comment?
Rocket Centaur: I honestly do not know. I forgot. I always use the shortcut.
Rocket Centaur: I think it's a Facebook star or something.
Rocket Centaur: Oh yes, I think you're right. There was something like that. Let me Google it quickly.
Rocket Centaur: I think it says hash. OK, OK, 3 double quotes.
Rocket Centaur: Yes, right.
Rocket Centaur: OK, where is the double quote?
Rocket Centaur: I use this shortcut on a daily basis, but I honestly could not remember when you asked it.
Rocket Centaur: Yeah, I know.
Rocket Centaur: Yeah. OK, OK, so. OK, perfect. So let me go through this. You are given an inclusive range, lower and upper, and a sorted unique integer array numbers where all elements are within the inclusive range. OK, and number X is considered missing. If X is in the range and X is not in numbers, return the shortest sorted list of ranges that exactly covers all the missing numbers. That is, no element of nums is included in any of the ranges and each missing number is covered by one of the groups. So here, 0 and 99, lower and upper. The nums is 0, 1, 3. 50 and 75. Uh, so the output is 2 and 2. Uh, the range, uh, the ranges are 2 and 2. Uh, so 0, 1, 2, 2 is actually, um, missing. And then from 4 to 49. Oh, I see. So the starting and ending missing and then 4 to 49, 51 to 74, and 76 to 99. And these are all— so they're written as a list of lists, if I get that correctly.
Rocket Centaur: Mm-hmm.
Rocket Centaur: Perfect. OK. And there are other inputs for -1. Nothing has to be included. I see. I think I overall I got what needs to be done. Let me see if I have covered all the, all the scenarios. If I have— so this is something that we need to handle where there's, there's no inputs at all. On the other hand, if I get lower and upper, and then if the list is empty, then I would have to give lower and upper, right? That should be one of the scenarios if I understand that correctly.
Rocket Centaur: No, if the nums is empty and if there is a lower and upper there, probably you should return -1 or the empty output, or empty output.
Rocket Centaur: Oh, the empty output. Okay, so only if the number exists, then we got to give the list, or else I have to return -1.
Rocket Centaur: Or yeah, yeah, so sorry, I'll retract a little bit back. Like, if you're asking the numbers itself is empty, but there is a lower and upper bound, then yes, yes, the output would be the lower, top, upper bound, right?
Rocket Centaur: Got it. Perfect. Yeah, then I think my understanding is correct. So let me write a couple of scenarios here. So if it is empty and if there is an Lower and upper. I think I got that. Would we ever have a scenario that lower one— like between lower and upper one is -1? And okay, so I think I have the constraint here. So the constraint is -109 to 109. So it it could be in the negative numbers too then, right?
Rocket Centaur: Mm-hmm.
Rocket Centaur: I see. Um, so here it means that, um, between, uh, 2 numbers. So if it is between 2 numbers, actually it do not exist anything. Uh, so, uh, that's the reason we are returning the empty output. Um, on the other hand, I, I would— okay, I think I am getting the point. So the length could be of 0 to 100. All the values of the numbers are unique. Okay, I think I got a complete picture of it. So probably we have to run a loop from lower to upper, and then— so from— it should actually start with lower, right? So because the condition already says it is between lower and upper. And if starting from the lower— so do I— no, I probably don't have to do that check. I can probably start with the first variable.
Rocket Centaur: Right.
Rocket Centaur: And if the list itself is empty, right, I can— okay, there are actually a couple of edge cases, but let me start with building the core algorithm and then we would cover the edge cases.
Rocket Centaur: Mm-hmm.
Rocket Centaur: Okay, so what I think I should do is I would start with this, right, the first variable, and then I would keep— like, I would, I would probably run a loop and see that if if the variable exists in the— meaning, so—
Rocket Centaur: Are you writing something?
Rocket Centaur: I would— oh, no, no, no. I'm just thinking. So I would actually have something like a previous, right? Prev. So my prev would be nums of 0.
Rocket Centaur: Right.
Rocket Centaur: And then probably I would start with 1 and I would, you know, constantly update prev after all the single loop, right? And then I would see if prev plus 1 is equal to this. So I do that. So then I have a condition. If it is If it is same, I do not have anything to do. If it is not same, I would keep incrementing it the moment I find— So I probably do not increment it, right? Like, I would probably have start and end. And I would leave the start as it is. And end, I keep updating it the moment, like, you know, I would find a variable in the list Then I would update the list, and then I would add it to the output, returning output. So I would keep doing that until I find— go to the end of the list. So that would be my core algorithm.
Rocket Centaur: Okay.
Rocket Centaur: Do you want me to write some sort of a template to get a sense, or you're good with what I communicated?
Rocket Centaur: I think what, what you communicated, you will run a loop right between, between lower to upper. Is that what you're saying?
Rocket Centaur: Like, so I would do run a for loop for the nums. So something like, yes, so for i in range of 1 to the end, right? That is length of num. And then I already, you know, have this added. Now I would see if prev is equal to nums plus 1— sorry, i, right? So if it is same, I would have a logic. And if it is not, I would have a logic.
Rocket Centaur: Mm-hmm.
Rocket Centaur: So if it is not, If it is same, then I actually would see— so to start with, I would— let me do this as well. So I would have start, right? My start would be lower, right?
Rocket Centaur: Mm-hmm. So if—
Rocket Centaur: prev is equal to lower, then I, I would not do anything, right? So the moment when I see the prev is not matching, in that scenario, what I do is I will initiate the start to nums , right?
Rocket Centaur: Mm-hmm.
Rocket Centaur: And then I would come to the next loop, right? So Well, so if it is same, I actually have 2 scenarios, right? If it is equal— if it is not equal, I would have to initiate both start and end, right? Then the moment when I find this is equals, then it is the moment where I have to update the end as nums of i, right? And then break it. But I think it is, it is not a complete good solution because if I start with— if there is already a continuity, then it is gonna break it. So I probably need to do something else. I need a clever solution. No, this, this I don't think would, would work properly. Let me, let me think through. Give me a moment. Another thing what I can actually do is run from lower to upper, see if lower is present in nums. So that is probably the easiest, but I think then I have to put this in a set and see from lower to upper. I will keep running a loop and see. I would get the variable, see if it is in the nums. Then I would, I would, so give me a second. Let me write that up here. I have start, right? And then I have the end. Now the way how I need to update it is If I find the value inside the, inside the map, then I do not have to do anything. No. So to start with, I probably do not need that, right? So when I actually start checking, then I do not have anything to add. So probably what I needed is the first number, which is actually missing. Um, so I could probably run, uh, initially and see, uh, what is the first, uh, place it is actually, uh, missing the, uh, value, uh, right? So, um, 0, 1, and then 2, uh, and Then, uh, from 4 to 49. Uh, okay, so I think, uh, let me, let me think again. Uh, I, instead of doing this, I can actually say, uh, previous, current, and previous. Um, and if, if it is not right, so if, if I am having 3 and 1, uh, then like I mean, okay, I think I got, I got an idea now. So this, this should be fine. So what I have to do is now actually have prev, right? And I also have current. Now, oops, what is that?
Rocket Centaur: Right.
Rocket Centaur: So now I could literally add this logic, right? That list of prev plus 1, right? And then I could say current minus 1, right? And then I add it in the list so that we would be able to do it in like one single run. Does it make sense to you? Yeah.
Rocket Centaur: Can you run this with that output? Whatever the input they had given?
Rocket Centaur: Sure, sure.
Rocket Centaur: So I see line prev and what is the current? Where did you—
Rocket Centaur: the current? Oh no, actually current is not required. Current is nothing but nums .
Rocket Centaur: OK.
Rocket Centaur: So this would be nums . This— so whenever— if, if the prev and nums do not match, meaning if prev Uh, if prev plus 1, right, if this is not equal to nums of i, so that is where I would, uh, add this. So we would have something like, you know, output a list of int, right?
Rocket Centaur: Mm-hmm.
Rocket Centaur: Uh, right, it is actually list of list, right? Uh, So it is actually a list of lists. And then what I would do is output.append of the list which has these 2 things. So that if there is an— so let's run an example. We would start with 1. If 1 and 0 is— it actually, you know, do not satisfy this condition, so nothing happens. Um, 3 1 is equal to num i, right? So it would not happen. But when it comes to 3, right? So first, when it comes to 3, it do not match. So 1 1 is not 3. So what we would have is, um, prev plus 1, which is 2. Um, obviously we would update prev as well, uh, like after the loop. Uh, so, um, that I can write it here. Uh, so after the logic update, then I'm gonna add this, right?
Rocket Centaur: Sure.
Rocket Centaur: Uh, so the prev is gonna be 2 and the num minus 1 is gonna be 2. So this I would add it to the, uh, output. So the first one, 2 and 2 would appear. Um, and then, uh, I would go to 50. Again, like, you know, 3 1 is not 50, so I would update 4 and 49, right? And then I would come to the last 75 and 50. Finally, I think we also have to start with the edge cases, right? Probably. Mm-hmm. So this would not cover those scenarios. So along with this, we have to probably start with, um, uh, 0. Uh, so, uh, I would, uh, probably, um, if so, how can I do that? Uh, so I have to start with 0, um, right? Um, or what I would do is I would see, uh, um, if lower and first variable is same. Um, if not, um, I would, uh, append it to the front and I would append the upper to the bottom so that, so that we would be able to cover that edge case as well.
Rocket Centaur: OK. And what happens at the end of the loop if start is lesser than or equal to the upper? If start is lesser than Or the previous lesser than or equal to upper, because once you run the loop, right, because the loop may not see the end of the element, right?
Rocket Centaur: Oh, you mean this scenario for 99?
Rocket Centaur: Oh, you see, this scenario is 75 until 75, right? 75 to 99 has to be because by the time you'll be out of the loop, correct?
Rocket Centaur: Oh yeah, yeah, but so before, even before this logic, we will have something like this that so if lower is equal to num of 0, right? And if not, I'm gonna add nums.append of lower to 0, right? And same logic I would have for the upper as well. Okay.
Rocket Centaur: Let's run this with that input and see.
Rocket Centaur: Sure, so something like this. If it is equal to nums of -1, that is the end of the thing, right? If it is not same, then I would say nums.upper. To cover the edge case scenario, and then I would run this loop throughout.
Rocket Centaur: Mm-hmm.
Rocket Centaur: Does that sound good to you logically?
Rocket Centaur: Yeah, yeah, yeah, yeah, I think it looks fine to me. Can you run this with both the inputs and see how your program behaves?
Rocket Centaur: Sure, sure. So you want me to— let's code this out, right?
Rocket Centaur: Yeah.
Rocket Centaur: Uh, def— what should be the name that I— yeah, the other IDEs would come with some default method, but here I could not see anything. So let me call it solution, right?
Rocket Centaur: Mm-hmm.
Rocket Centaur: And then I would actually have nums and 2 integers, right? So, uh, nums of int— no, a list of int, right? And then I would have a lower, which is an int, and then upper, if I am correct. Um, right. Um, okay. And the return would be, uh, List of a list of int. Not sure why this is not picking up. Should I use— do you know why this is not Getting no— actually, this is good. I could see this list working properly here.
Rocket Centaur: Yeah, now, now it went away, right?
Rocket Centaur: Yep, yep, yeah, this is good. I think that was just because it did not return. Yeah, this is good. So I would have output, right, which is called as list and just .print. Right, and then okay. So let me see the constraint here once. I would always have okay. So let me. Do this. If lower is not equal to nums of 0, right? I'm gonna say nums.append of lower at the 0. I hope this actually works. Expected one positional argument. Am I allowed to see what is the right method to add it in a particular position?
Rocket Centaur: Yeah, I think, yeah, that's fine. Like, you know, you can use some IDEs that will automatically populate that, right? That's fine.
Rocket Centaur: OK, OK, yeah, so let me check that. List of Python tools. Okay, oh, it is insert. Okay, I see. Um, insert 1 and upper. Okay, so it is insert, uh, 0, um, and lower. Right, um, and then if upper is not equal to nums of -1, uh, right, and then, then it is complex.insert upper at -1. OK, I think in Python it actually returns add set at the end, I guess, so this should be fine. I don't have to get the length. OK, so these 2 are good. The next is, um, for— no, I have to say prev int is equal to nums of 0 now, right? And I would have to say for i in range of 1 to length of nums, right? So I run this and then if prev plus 1, right? If this is not equal to— if this is not equal to nums , what I would do is if this is not same, if this is not same, output.append, and then I have to insert a list and the list would be prev plus 1, right? And then nums of i minus 1.
Rocket Centaur: Yeah.
Rocket Centaur: Right. And then I got to update is equal to nums of i. Let me see if this is what I have written there. Yeah, I would delete this part. Okay, uh, fine. Uh, so far, so I still have which case to handle. Uh, I will come to that later, but let me go through this.
Rocket Centaur: Yeah, yeah, let's, let's, uh, focus on that 2 cases what we have specified, and then we can move on to the edge case.
Rocket Centaur: Okay, okay. You mean the corner ones?
Rocket Centaur: No, no, whatever the— in the problem we are given 2 inputs, right? One is 0, 1, 3. Okay, so that's—
Rocket Centaur: yes, yes. Okay, okay. So for this one, let me write— take this one up here. Right. So we have prev and we have output here. So actually the input would become as this, right?
Rocket Centaur: Mm-hmm.
Rocket Centaur: So we are changing the input. So this is what we are passing. Now what happens is we are running through the loop. So we are starting from 1 to the end of the length. So the previous is actually 0 first.
Rocket Centaur: Right.
Rocket Centaur: And we are starting from 1, 0 plus 1, which is prev plus 1. If it is not equal to num , so which is 0 plus 1 is 1. So this is not executed. Now prev will become 1. Right, and then we would go to 3, right? So 1 2 is not 3, which means this condition fails. So this 1 1, which is 2, is not equal to nums, right? So now I would add this one, so this becomes 2 and 2. Right, and then we are updating this to 3. And we are coming to 50. So when it comes to 50 again, like 3 1 is not equal to 50, so I would add 4, that is 3 1, and then I would also change this to 50 minus 1, which is like 49, right? And then I would come to— so this becomes 50. So the same thing happens for 50 and 49. So then it becomes 51 comma 74. Right, and then this would be updated to 74— sorry, 75. And then comes 99, like, you know, the same thing happens. So this would become 76 and 98. Let me see if this is what we are expecting in the output. Yep, yep.
Rocket Centaur: Okay, yeah, yeah, yeah, I'm good with it. Can you run this program and show me that it is creating that output?
Rocket Centaur: Okay, sure. Uh, how can I call this? So, uh, so we still did not handle the edge cases, but I will, I will come back Yeah, yeah, yeah, yes, we can come later. Okay, so I'm gonna call, uh, solution and then, uh, And, uh, what was the 2 values? 0, 99, right? Why, why solution is not defined? Unknown. Why it is not able to I delete everything here. This should be good. And let me take this to the bottom. Okay. This should be good. Let me run this.
Rocket Centaur: Print then.
Rocket Centaur: Yeah. Okay.
Rocket Centaur: Why did you put in a loop?
Rocket Centaur: I actually did not. Oh, I actually copied this. Sorry about it.
Rocket Centaur: Okay.
Rocket Centaur: Okay, but still, yeah, there is some issue, I guess. Wait, let me run this. 76 to 99. Yes, I think I did not handle, uh, so I know, I think this should have messed it up. Um, probably it does not. Let me, let me print this once after adding it, then I could be wrong on this. Um, print of nums. I had a vague— yeah, so this shouldn't be this. I was wrong then. So what I actually got to do is length of— right, so this should be -1, right? And then I should say Length of nums. Yeah, I was wrong. Like, you know, I— for, for few of the scenarios, -1 works. I don't know why. Probably I'm missing something. I should, I should know what is wrong there. Uh, what is it now? Oh, because I get Minus— Sorry. No, I don't think it is actually working. Again, insert upper. Upper is actually 99. If upper is not equal to length minus 1, Okay, so if upper is not equal to the nums of length of minus 1, then I am adding. Not sure what is wrong here. Let me think. Is there a way I can reset this? Okay, yes. So it is actually printing 4. Why would it print 4? Which means the insertion It should be actually the other way. I misplaced the— yes, this should work. It should be this guy.
Rocket Centaur: Yes.
Rocket Centaur: Yep, yep. I missed out, messed up around the length and the index of these 2. Yes. Are you, are you good with this?
Rocket Centaur: Yeah. Can you run? Yeah, it's clear actually. No. Did you check the output? Like, it is missing.
Rocket Centaur: Yes, yes, it is actually missing this guy. So, uh, yes. So for this scenario alone, I need to add the final variable itself, right? How can I add it? How can I do it? That actually do not work, so that won't work for all the scenarios. So I'm not sure if that is a problem. Then I think the the fair value or the fair way of doing that would be. probably like doing at the end, right?
Rocket Centaur: Mm-hmm.
Rocket Centaur: So I would say if upper is not equal to nums of length of nums, right, minus 1, uh, then, uh, what I got to do is, uh, um, Output.append of 1 is append, so prev, it should be prev plus 1, right? And then I have to directly add the upper here. I think this would be able to Why is there an error here? I expected one positional argument. Oops, just the— so this way, uh, the edge would be handled, and I think I should use the similar way to deal in the output, right? If these 2 are not same, then I could actually say output.append, and it should be lower— should be lower plus 1, right? And then it should be nums of 0 minus 1. This would handle the scenario, I think. Yeah, are you good with this?
Rocket Centaur: Yeah, yeah, this is good. Let me quickly Shouldn't be 79, right?
Rocket Centaur: 80. So 80 is supposed to—
Rocket Centaur: I think 76 to 80, it's fine. Um, so let's do this one, right? The second output, which is second input.
Rocket Centaur: Yeah, I think that there is an edge case that I don't think I have handled that. Like, if— let's run this. Okay.
Rocket Centaur: -1 is empty. Right. Okay, why don't you explain what is the complexity of this particular program?
Rocket Centaur: Um, we are running the loop only once, so it does, it does O. Um, initially I was doing, uh, no, uh, hold on one sec. So, uh, the time complexity is gonna be O since we are running the loop once, and the space complexity is gonna be The worst case that it could, it could, it could have, if exactly each of the numbers are missing, then it is going to half of it. So it is going to be like, you know, off in the time and both time and space complexity.
Rocket Centaur: Okay. All right. All right, I think let's go with another question.
Rocket Centaur: Okay. Yep, yep.
Rocket Centaur: I'm typing here.
Rocket Centaur: Oh, it is at the bottom. Did you add it?
Rocket Centaur: Oh yeah, at the bottom.
Rocket Centaur: Oh yeah, sorry, I did not pay attention to that. So given 2 strings, return true if they are both one edit distance apart, otherwise return false. A string S is said to be one distance apart from A String T. If you can insert exactly one character into S to get T, delete exactly one character from S to get T, replace exactly one character of S with a different character to get C. Okay, so AB, right? AB, it is actually 2 And this is also true. Yeah, so this is going to be a classical DP problem. But, you know, there is, there is a recursive solution as well that we— meaning like, you know, we, we run a recursive call, right? In the recursive call, we're gonna start with A first, uh, and then here A first. Um, if both are same, then, uh, there is nothing to do. Um, in that case, we're gonna increment both the index right now.
Rocket Centaur: Mm-hmm.
Rocket Centaur: This would be incremented to B and this would be incremented to C.
Rocket Centaur: Mm-hmm.
Rocket Centaur: So if both are not the same, we have a bunch of options here, right? So one is we can actually insert, right? Which means that— so it is gonna split into 3 parts, right? So if we have to insert, we can actually Uh, insert, um, like we have 2 parts, right? C could be inserted between A and B, or B could be inserted between A and C, right? Uh, so if it is an insertion, it is gonna make another 2 recursive calls, and if it is an Delete. So no, wait, I think it is only on one, right? So we have to probably insert only in S. Let me read that question again. They are both one unit distance. The string S is said to be one distance apart from a string. If T can insert exactly one character into S. Okay, so the insertion is only at T. The deletion is also at— sorry, the insertion is only in S. The deletion is also in S, and the replacement is also in S. So we probably only have to consider the case that C has to be added, right?
Rocket Centaur: Mm-hmm.
Rocket Centaur: And the adding in T is actually not required. So the first is having inserting C between A and B. So that is one scenario. The deleting of would be, uh, you know, uh, deleting, uh, B, and we have to, uh, get past the string as just A. Uh, so it would be considered as A, and, and in, in that case, um, we would just increment, uh, the S string— I mean, S index— and we do not increment the, uh, T index. So that is to deal with, right?
Rocket Centaur: But what happens, like, T could be also like, uh, here the case could have been T can be in place of S, like, which means ACB, and T could be like AB as well, right?
Rocket Centaur: Uh, sorry, sorry, say that again.
Rocket Centaur: So, um, the S and T could be swapped also. So you need to work on that condition as well. Like in the case like here, the T is ACB, right? The ACB could be— yes, yeah, it could be S as well, right? Then the, the input S could be ACB and the input T could be, uh, uh, AB.
Rocket Centaur: I see, I see. Okay, uh, you mean like, you know, if you interchange it, what happens? A, C, D.
Rocket Centaur: Yeah, yeah, it can be interchanged also. Like, uh, so what I would like to understand is which string you will use to identify, uh, the, the source to compare, right? Uh, and also like, how do you compare? Like, and how do you calculate this one edit distance?
Rocket Centaur: Yes, yes. So, um, uh, if, if I try to do a recursive call approach, right? So I'm just writing the template, uh, req call. So then I would actually have index here, right? So I'm gonna call s index, right? And then I would also have t index. Now, um, if, um, so if both, uh, if s of s index, right, if this is equal to T of T index, right?
Rocket Centaur: Mm-hmm.
Rocket Centaur: T index, then I think we just have to increment it and do the REC call again, meaning REC call of— yes, index. So there is no incremental operator in Python. Just for readability, I'm doing it.
Rocket Centaur: Right, yeah, so probably assume that you can use substring.
Rocket Centaur: Mm-hmm.
Rocket Centaur: OK, yeah, OK, will that simplify your logic?
Rocket Centaur: Yeah, so that, that is probably have to be used in the else part if I'm not wrong, right? That's what you're— okay. So now let's go through these cases that insert exactly 1 character into S. Okay, so insertion Into S to get T. If I insert, then what I actually do is— so insertion means then I have made one. So, okay, so let me write it here, right?
Rocket Centaur: Um, for Insert.
Rocket Centaur: If it is insert, which means that one value which has already matched, right? So I can actually say count got incremented by 1. So this would be +1, and I can actually say that. I can— so wait, so if I assume that insertion happens, C has worked. So I would leave index as it is and I would only increment T of index. So this is what insertion would look like. Would you agree with that?
Rocket Centaur: Yeah, insert. So I think in this case, like, we don't need to insert, right? What you're trying to see here is—
Rocket Centaur: No, we don't have to. Yeah, so we don't have to We are not actually inserting, but let's assume that we are inserting C here. In that case, yeah, exactly. Yeah, so we are, we are actually incrementing 1, right? So the, the count, the count is incremented by 1, right? And how are we treating this is we are leaving the S index as it is and we are incrementing the T index, which means that—
Rocket Centaur: Yeah.
Rocket Centaur: This stays here and this becomes this, right? So this, that, that we are treating as insertion.
Rocket Centaur: Right, right. So if I give the substring operation, you don't need to go for dynamic programming, right? Because—
Rocket Centaur: Yeah, yeah, this is not DP. Yeah, so like, you know, that was like 2 of the solutions that I told. So one solution is using recursively what we are doing it here. Another one is DP table, like, you know, we build and do it, but I did not even go to DP. Like, this is This is completely on recursive calls.
Rocket Centaur: Okay, okay.
Rocket Centaur: And so this is the first insertion, and let me see how to do the deletion. So in deletion, again, we have to increment the count, right? And then delete means we are deleting something at this point. Right. So what actually happens is we are incrementing S index, but we are not incrementing T index. Would you agree with that? So that would be—
Rocket Centaur: Uh, Yeah, the deletion is nothing but you just need to— so first what you have to look at it is whether the first character, the character matches or not. If the character is not matching, then only you need to, uh, compare the— do that operation.
Rocket Centaur: No, no, so that, that is in the else part, right? So here in else part, what we would do is, um, so we would, we would say, uh, the minimum value, right? So, uh, we, we would have Recall of s index, p index.
Rocket Centaur: Right, but if the character is same, you don't need to do anything, correct?
Rocket Centaur: No, no, that's right.
Rocket Centaur: It is, it is matching. Yeah, yeah.
Rocket Centaur: So, but we have already covered that here. So if the character is same, we do nothing. We just increment both the indexes. So this is only if it is not matching, then we're going to expand it, right? And, and we're going to get something like for Delete, then for deletion, what happens, right? So that way we also have to pass the distance, distance, right? So if, if distance is equal to— if distance is greater than— like, this is— I'm just writing the template. You would, you would still find some problems, but the distance Yeah. Than 2, then I'm gonna return false, right? So I'm gonna return false, but this would be, you know, getting one of the values. So I would have all the 3, like both delete, insert, and replace. I would keep incrementing and I would, I would up the answer of all the 3 so that, you know, we would, we would get like— so for each combination we are expanding and we keep expanding in all the 3 zones, that is insert, delete, and replace. At any point of time it grows bigger than 2, like, you know, we return it as false. So that way we would be able to track.
Rocket Centaur: Okay, all right. I think Yeah, we are on time. Uh, um, I think— what do you think about this exercise?
Rocket Centaur: It was, it was, it was good. It was good. Uh, the, um, this— I think I feel, I felt that I could have done a little bit better, uh, with this scenario. I, I messed up with the, with the edge case. Um, but yeah, because the easy—
Rocket Centaur: yeah, I think the easy question is something like you may want to solve within first 20 to 25 minutes.
Rocket Centaur: I agree.
Rocket Centaur: Yeah, it's almost like 45 minutes.
Rocket Centaur: Yes, yes.
Rocket Centaur: Normally.
Rocket Centaur: Yeah, I agree.
Rocket Centaur: The higher one companies—
Rocket Centaur: Yeah, I have no argument. What you say is 100% true. I expect that this I should have solved at least in like 30 minutes, then I should have made a decent approach for this one as well. But even then, I should have at least covered those edge cases properly, which I didn't. not do. Um, but yeah, uh, that would— I would keep practicing.
Rocket Centaur: Yeah, yeah, I think it's a keep practicing, you'll get it. But at least the, the good thing is you were able to identify the logic, and, uh, in the get-go you were able to identify some kind of edge cases is the one where you need to spend some, some time.
Rocket Centaur: Sure, sure.
Rocket Centaur: Uh, and you were able to solve the problem with big O of n, right? The first problem. And this one is almost done, but we are not able to complete. Um, but that's fine. I think more, uh, focusing or more practicing and trying to address this, uh, easy question within 20 minutes, um, and medium questions maybe 30 to 35 minutes will get you, um, clear those interviews.
Rocket Centaur: Sure, sure. Yeah, and how did I do on the second one, um, from the interviewer perspective?
Rocket Centaur: The second— yeah, the second one is the logic is simple, right? Because where, you know, we need to identify, uh, whatever the length is greater, right? Uh, so that, uh, that string will be the source string, and then the lesser string, lesser length would be the target string, right?
Rocket Centaur: Yeah.
Rocket Centaur: Uh, if the length is If, if the length, the difference of the length is greater than 1, then you can return right there, right? That's a base. That's what you also done, right? Return false at the beginning.
Rocket Centaur: Yeah.
Rocket Centaur: Otherwise you go there. So here, here the condition what you have to check is if the character is not matching, right? You have to compare character by character. If the character is not matching and if the length is M equal to N, N, right? If it is both are same length.
Rocket Centaur: Oh yeah, and if it is not matching, so that, that would be actually covered up here. So we would have a base case, like, you know, I did not probably cover that. So here we have to check the, um, the S.length is less than S.lengthOfString. So those things I did not cover, but like I was trying to cover these 3 logics. like what, what to increment and what the other one. But yeah, I honestly do not have enough time to come to this, this part at all.
Rocket Centaur: Yeah, so what I'm saying is we even within the for loop, right, if the character is not matching and if the length is same, you just need to compare the substring from i 1 to the target string i 1. If that matches, Then it's good.
Rocket Centaur: I see. Right. I actually did not—
Rocket Centaur: then you don't need to worry about it.
Rocket Centaur: Yeah. So I did not even think through the, the for loop, right? Like I was thinking on the recursive call and where I call them recursively. So that's what I was thinking through. Yeah, probably like you, you were thinking through on the, on the for loop from index to index, which, which I did not even like, you know, I was trying to solve it using the recursive. 1. But yeah, I, I, I, I know what you mean. Yes.
Rocket Centaur: Right, and if it is not matching, then what you have to do is you just need to— the source substring i and target substring is i 1, right? Because you're deleting 1 character and then comparing whether that string matches. That's all we need to do.
Rocket Centaur: Yeah, yeah. All right. Yep, yep, makes sense.
Rocket Centaur: Cool. Um, awesome. Thanks. Yep.
Rocket Centaur: Yeah, it was, it was good. Uh, yeah, yeah, thank you, thank you.
Rocket Centaur: Yeah, yeah, practice more and then you will get to, get to that.
Rocket Centaur: Sure, sure, I will do that. Thanks for the inputs.
Rocket Centaur: Yeah, yeah, no worries. Good luck. Bye.
We know exactly what to do and say to get the company, title, and salary you want.
Interview prep and job hunting are chaos and pain. We can help. Really.