Valid Palindrome (Python Interview)

Watch someone try to determine if a string is a valid palindrome in a mock interview with a Meta engineer. Explore this problem and others in the world's largest library of interview videos.

Interview Summary

Problem type

Valid Palindrome

Interview question

1) Determine if this string, after removing any one character, can become a palindrome. If possible return true, otherwise return false. 2) Given the string of parenthesis and possibly some characters as well, balance the parentheses. Do this by removing as few characters as possible and cannot add any characters to make it balanced. 3) Given a grid of characters and an array of string inputs, find if each of these words exists in this grid. To find it look at adjacent characters, using each character only one time.

Interview Feedback

Feedback about Aerodynamic Raven (the interviewee)

Advance this person to the next round?

Yes

How were their technical skills?

4/4

How was their problem solving ability?

4/4

What about their communication ability?

4/4

Great communication, problem analysis, problem solving, coding and testing. I really liked how you explained your test plan, and organizing code into helper functions. Asking for clarifying questions such as constraints and edge cases will help with solving problems. Most interviewers will ask you 2 problems so you have about 20m to solve each of them. Suggest practicing a few problems for every kind of DS & algo: string, array, 2-pointer (palindrome Q), stack, linked list, hash, DFS/BFS, tree/trie/BST, queue, heap. Good luck!.

Feedback about Clandestine Hamburger (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

Thanks for the practice with a third question!

Interview Transcript

Aerodynamic Raven: Hey Hamburger how are you?

Clandestine Hamburger: Yeah, I'm doing good Raven. Nice to meet you.

Aerodynamic Raven: Yeah, good to meet you.

Clandestine Hamburger: Yeah. So today it's a Facebook practice interview. It's the session is one hour, but the actual interview for Facebook, it actually takes 45 minutes. But we can use the whole time 45 minutes and then the end to to discuss anything regarding if you have any questions, or we can discuss feedback. Yeah, the format. Yeah. And for the interview that for the five minute, they, they usually have two questions. That means we have about 20 minutes ish for each question. And, most importantly, they do not allow you to execute the code. So we can run the code by hand. Okay. Yeah, we're not going to hit the Run button. Alright. So may ask if you have scheduled? If so you reach out and you have with the Facebook tip.

Aerodynamic Raven: Yeah. So I've done I've been doing a lot of practice, by the way. So this is, I was just getting a few in for the weekend, my interviews on Monday, and I'm pretty much expected to already be prepared. I just thought why not? I have a little bit of time.

Clandestine Hamburger: Yeah, practice makes up perfect. So let's get started. I'm going to pass Oh yeah, you can choose any ah you already chose Python. That's great. So let's get started. I'm going to put this example input and output you given a string input, and then you determine if this string can be removed any one character and it will be a palindrome. So, if you can make that a palindrome by removing one factor, then you can return true otherwise false. For example, you can remove this here to make this string a palindrome. So you can return true. You can either remove this string, this string, make it palindrome. So you're essentially Yes. But the last example, you cannot make it that Palindrome by removing any type. So that's the question.

Aerodynamic Raven: Okay, got it. So, we're going to be returning basically true or false. If we can remove a single character, if we have an empty string, Should I return a default value?

Clandestine Hamburger: Let's return true.

Aerodynamic Raven: Okay. I'm just going to write the function signature first is palindrome with one char removed, and we'll have some input string. And this is going to return a bool. Okay, I'm thinking of some other clarifying questions here. empty string is a palindrome. Is that correct? Yeah, that's correct. Okay, all this regard statements. And x, I should say, we'll say less than or equal to two. We have two characters. And any, we remove one, we have one character. Okay, so I'm gonna think about my strategy here for a moment. So okay. Maybe I'll just sort of talk about the first approach. I don't know if this is going to lead anywhere. So we have Taco cats. And maybe I have two pointers, one at the beginning and one closer to the end of the string. So if these two values are not equal, then it would mean that I would probably have to end up removing one or the other. And if we end up removing one, then we can just do a very quick Palindrome check in linear time. But okay, but then the question is really going to come down to well, what if we have another case here, where we have, I'm trying to think of how much what the time complexity of this is going to be. So these pointers are going to come in words. We are only going to remove a character once. And then when we do remove a character, we are only going to check once if something is a palindrome. So the total amount of time these pointers might be incremented, or decremented is going to be linear. So it's going to be something like n plus one See the Palindrome check is probably going to be to end, just because we have two different scenarios. And okay, so I think this is this might be linear, but I'm trying to think of any, you know, special edge cases here that's going to make this a bit more challenging. What about a scenario like, okay, let's say ABCD, we're to apply this algorithm, then we would look at A and D, they don't match. And so clearly, we have to remove one of them. If we end up removing D, then we have A, B, C, and we can very quickly see that this is not going to be a palindrome. And same with the C D, we can check that as well. If we have a true Palindrome, like, let's say, let's say something like this, a bunch of A's, but it's odd. Okay, so back, I'll just have three, we know that this should return true. But what I currently have is, essentially, these pointers are going to end up being set to the middle value. And we know that in this case, there's an odd number of characters. And so in this special edge case, we know that we're going to return true. And if we had four characters here and these are incrementing, and incrementing. Eventually, they're going to pass each other. And so I guess, if we do remove a character, it actually still is a palindrome if they end up passing each other. Then the question is, which which character should we remove? And I don't think that's necessarily an easy question. To answer here. So let's say we had, let's see, if it already happens to be a palindrome. And as an even number of characters, I'm trying to think of how we would know to remove Well, if it's even number of characters in a palindrome, the two middle characters are going to have to be the same. And if we remove one of those middle characters, then it's going to be still a palindrome. So we can say-

Clandestine Hamburger: Oh one thing, if the string if the string is already a palindrome, you can also return true, that means you you don't have to remove that one factor. If it's already a palindrome. It's just essential.

Aerodynamic Raven: Right? Sure. Yeah, it's got a cure.

Clandestine Hamburger: Yeah, it's like removing at most one character So that means you, you can just keep all character if it's a palindrome. I hope that helps.

Aerodynamic Raven: Okay. So I think the algorithm might have, I think it might work. So all right, I can go ahead and implement this, I think linear time complexity is acceptable. So I'll just start writing out some of the parts of it. So we have our two pointer approach, we have i is zero, we have j is Len string minus one. And, let's see, we, when we come to try to think how to process this correctly, when we come to a point where two characters are, you know, the the pointers, i and j end up pointing to some character that doesn't match and we want to remove it, just trying to think of how we're going to process it for a race car example, it's going to be E, and it's going to be r. So I can just make it very simple. We'll end up using constant where I have an approach that simple will use linear space, and I'm wondering if that's acceptable to you, or if you want to make sure that it's only constant space.

Clandestine Hamburger: Let's try and see I think linear space. Looks good. You have to check the character is right.

Aerodynamic Raven: Right. Okay. So, we could do is, let's see, we want to say while string, we're okay while i is less than j and string i is equal to string at J want to say i plus equals one j minus equals one. So down here we have is equal to j or mismatched. So okay, if is equal to j in that case, let me put less than or equal here Because trying to think if I want to do that or not, if, if i is equal to j, and the string is odd in length, then we can just remove it. So if i is equal to j and Len string mod two is equal to one, then we can return true. And the other scenario, where is equal to j in the length of string mod two, where the string length is even, then what we can do is that should actually not be possible, I will not actually equal j if the string length is even though actually crossover from each other. So I'll say, if I is greater than j, and Len string mod two is equal to zero, then we can still return true because the two middle characters will be the same. And if we remove one of them, then everything will still work out. So the scenarios here that I'm interested in is when i is less than j, and these two characters are not equal to each other. So we've already checked if something is a palindrome for the outer characters, so we should only need to check the subset of the string between i and j. So we could say if is palindrome. In this case, we're going to start at string I call in J, it will not include j. So that will be like removing the J character. is palindrome. Being i plus one colon, j plus one. Let me just put a comment here. I'll remove J character, in this case, remove I character. And if we get down here, we can return false. So do you want me to implement is palindrome? Actually, I can probably do it really quickly. Reverse string is string dot reverse a sink. Actually, there's another notation I can use that and return string is equal to reversed string. Okay, so let me work on a manual test case. And I'll try race car. I, I like that one. So we've got race car here, let me just put a comment block. Our string is race sir car. Right? If not string, okay, if length string is less than to return true. And if is palindrome string. Okay, as far as is palindrome. This isn't a palindrome. So I'm just going to skip over the evaluation of that function. And we have is zero we have j is length of strings. This is one, let me get the indices here. 01234567. So looks like it's eight characters. So the length minus one, seven. And we have some while loop. Currently, let's see if zero, J is seven. And let me put another two variables here. We'll say this is i and we'll say this is j. So R, okay string, I is R string j's R, so they are equal i is less than j, and then we increment i, and we decrement j. Oops, that was seven, this should be six. So all right, we're gonna try this again. We're going to increment i visually decrement j visually. So all right, i is less than j string it, i is a string at J is a, so we're just going to increment and decrement. You're going to increment again decrement j again, I still less than j string it i is C and string at JSC. So we're going to increment and decrement. Cool. And in this case, I is less than j but the two values are referenced are not equal. So we're going to break out we have if i is equal to j in the length of the string is odd, we're going to return true if Let's see if I is greater than j, which is not true. So then what we're going to do is we're going to try to run our is palindrome on to substring. So is palindrome. Let's see race car starting index i ending it index j minus one is just going to be E. So we're going to remove the J character. And E is just one character. This definitely is a palindrome reversed, so we're going to end up returning true. So we return true. Okay, it works, at least for that test case, I could try and come up with some other edge cases where I'm not sure. If you have some other ideas in mind.

Clandestine Hamburger: You try the negative case the case that return false.

Aerodynamic Raven: Okay, so we'll do ABCD. This real quick string is equal to that. And okay, make the string less than two is false, is this a palindrome it's also going to be false, because reverse is going to be DCBA. And we have is zero, J is Linksys is four or 123. Okay, and we have is going to be zero, J is probably going to be three because length minus one, so that's four minus one, three. And okay, so we have some while loop, we have i less than j string, I has a and string at J is D, and so they're not equal and we're going to immediately break out and the is equal to j check is not going to work is greater than j check is also going to fail. So then we're going to check is palindrome. String at index i to index j minus one inclusive, so that's a, b, c. So there's going to be our first check, we're gonna do our reversed string is C, B, A, and then we're going to return a b, c is equal to a CBA, which is false. And then we're going to try is palindrome it's going to be index i plus one, so it's going to be starting at B and it's going to end index j, inclusive. So B, C, D, and then our reverse string is going to be DC B, and we're going to return B, C, D is equal to D, C, B, which is false. So then we're going to be on line 83. And we're going to return false.

Clandestine Hamburger: Okay? What is the specified time complexity.

Aerodynamic Raven: So the time complexity is going to be linear reason being is that in our loop line 72, it's going to be linear time there. And then we're going to call is palindrome on line 80, which is also going to be linear and same with AD two. And same with 68. So linear time, as far as space, it's also going to be linear, because online ad one and 83. We're getting a slice of the string, and this could be up to the size of the entire string. Also within our is palindrome function or reverse string is a copy of the string, linear time linear space.

Clandestine Hamburger: Can you make the linear space better.

Aerodynamic Raven: Yeah, that is definitely possible. So far as linear space of the is palindrome function, I could have a two pointer approach to make that linear. I don't know if you want me to actually change the code for that. And what we can do for is palindrome function. We do this stuff is palindrome. Palindrome we have our string, and we have our start and we have our end. So we're actually looking for a palindrome of a subset. And then what we do is we have alkalosis, Palindrome two. It's while you know start is less than or equal to end. If string at start, not equal string at end, we would return false. And then we would adjust. We would say start plus equal one and minus equals one. And if we get down here You're in breakout, this means we can return true. So then what we would do is we'd modify is palindrome to contain our string, and then our start and ending indices. So that would make it constant space, since we wouldn't be allocating any more. Any more memory. So I could, you know, make those modifications if you want, but I'm not sure if you want to move on to the second question.

Clandestine Hamburger: Yeah. Seems good, at least, yeah, at least you understand that the is palindrome is the model net. And you can do it. So that's great. Like I said, I'm going to move on to the second question. Yeah, let's go ahead. Go ahead, I'm going to test key. So this is to get the input as a string, again, and output as a string. So the question is given the string of parenthesis, and that could be some characters as well, your job is to balance the parenthesis. That means by by removing as few characters as possible, that means you cannot add any characters to make it balanced. So let's go to the example. The first example is already a balanced parenthesis, so you don't remove anything and just return SS. But for the second example, in order to make it a balance, and this is the only way to make it empty, because you cannot add any more brackets. So you can only remove them. So empty string is the answer. And same as the third example. And for the fourth example, you gotta remove the first and the last parenthesis to make it balanced like this. For this one as well, right? The multiple correct answer, like these two examples. So you return either of them, if I just make sure that you remove the third as possible.

Aerodynamic Raven: Totally. All right, yeah, I think I understand this question. So I know in a single pass, I can remove unnecessary closing parenthesis, the way I can do this is, let's say we have a running counter for that we'll umm. Every time we encounter an opening, opening parenthesis, we add one to this counter, if we encounter a closing parenthesis, we subtract one. And then what happens is, whenever our balance would be negative, we know that we have too many closing parenthesis. And we would just sort of not add it to our results string. So in a single pass, we can get rid of all the unnecessary or, you know, all the unnecessary closing parentheses, what we can do is repeat this process scanning from right to left as opposed to left to right to repeat this process for the unnecessary opening parentheses. And then whenever we encounter some other character that's not opening or closing parenthesis, we just make sure to always include it in the result. And the time complexity for that is going to be linear two scans. space complexity is also going to be linear, because I'm going to need some, you know, result to to work with, I don't think there's a way that we're going to be able to with a lot of effort, it might be possible to get, you know, do in constant space, but I think linear should be fine. So that's cool with you, I can go ahead and start coding. Okay, so we want to say balance, you know, parentheses, and we'll have our string as input. And, okay, so the first thing I just want to do is if not string, then return, you know, empty string. And I think that's the only visual edge case to worry about. So, all right, as far as these two scans, I might want a, let's see. Well, I'll write out without a helper function, then I'll try and include a helper function. So we'll have a weights dictionary. And opening is going to be one and closing is going to be negative one. Okay, so why is this complaining All right, it's not using partial result, we're just going to keep that as an array. And so for char in string, if char not in weights, which means it's just a character, we're going to do partial result dot append. Simple, and we continue. So we also need a weight some start at zero. So if char char is equal to opening, parenthesis, in this case, we want to do weight sum plus equal one. And partial result, append char. And the second pass will get rid of the opening parenthesis not needed. And if char is equal to a closing parenthesis, then let's see if weight sum is equal. Let's see, if it's equal to zero, then we just want to continue. And, in fact, we'll say less than or equal just for my sanity. So I know at this point, it's going to be positive. And if we're here, it's positive. So we say, Wait, some minus equals one. Partial result dot append, Char. And that's it. And I'll just have a very quick guard statement. So all right, the next piece of code before I've write the helper function, we would be starting right to left. But if I'm going to do this in a way that uses a helper function, first thing I would have to do is we're gonna have a reverse string string colon colon minus one that we would want this one-

Clandestine Hamburger: This one, it will continue to this line, isn't it?

Aerodynamic Raven: Um, oops, I forgot to continue statement.

Clandestine Hamburger: Okay. That's awesome. Okay, go ahead.

Aerodynamic Raven: That's all right. So now we have new weights are closing parentheses shouldn't be one opening should be negative one. And then I think most of the code would be duplicated. And so let me create a helper function. And then let me just put a little comment here, do helper function, and then at the end of this, we would get some partial result. Partial. Let's see, okay. And when I said, reverse string, actually, what I want is I want to join our partial result. Let me just say partial result. And I want to reverse our process string. Okay, and then down here, we also get a new partial result. And what we want to do is, I think we want to reverse it first. So we say partial result is partial minus one, we're actually dot reverse. Really, this won't return anything. So I can just have this as its own statement, and then return this dot join partial result. Okay, so let me write our helper function. And this will be f remove unnecessary parse, and it's going to take in some string, it's going to take in some weights. And what else is it going to take in? I think that might be it. So then the idea is going to copy some of this code. We have our partial result up here. And we can copy this code as well. Try and string let's see A partial result is defined weights that's defined string that's defined. And then I need weight sum, okay? Weight sum is equal to zero. And then at the end of this, you return partial result. So what I can say is on here on line 62, we want to say partial result is equal, remove unnecessary chars, our string is going to be our are reversed, processed string. And our weights was just declared right above it. Okay, and then let me just copy this. And I will, I will comment out this code just because maybe I will want to in a moment, if I make a mistake, and our partial result is going to equal remove on the serie chars, it's just going to be their string, and our weights. So I'm gonna go ahead and try to manually test this. And let me see a good example I want to remove opening and closing parenthesis some, and I also have some characters that are not either, okay, so what we have is so I'm gonna take this line 13. And okay, that will be our strength. equals and let me bring this down closer to our balance parenthesis function. Just for my manual testing, I'm going to take this snippet of code, and I'm just going to remove it and put it elsewhere. I'll just put it at the very bottom case, I need it. Okay. All right. And let me get to cool. So this is our string. And let's see, it's not string return, something that's empty, we have weights is this dictionary, we have our opening, which is going to go to one closing, which will go to negative one. Also just want to make a quick edit, line 57. Now I've already switched them. Okay, so then, all right, our closing will be negative one. And we're going to say partial. So is remove unnecessary chars or you know, string weights. Cool. So inside remove unnecessary chars or partial result is going to be this empty array weight sum is going to be zero. Okay, and for chart in string. Let's see, I'm just going to have a little pointer up here. So our first char char in string, so our char starts at our closing parenthesis, and char not in waits is going to be false. So we are going to be on line 30. And weight sum is is less than or equal to zero, so we are just going to continue. So then our next character is going to be an opening parenthesis. And I try not in weights, and then we're going to go to Line 26. So our weight sum is going to be incremented by one. In our partial result, we're going to append this character. So I'm just going to put it up here. And then we are going to continue. So then our next char is going to be equal to a turn on weights is going to be true, so we're just going to append it and continue. So now we're going to increment this we have a closing parenthesis and turn on weights as false we're going to line 30 weight sum less than or equal to zero is false. So our weight sum is going to be subtracted by one to become zero. And we are going to append this character to partial result. And then char is another closing parenthesis. We've kind of gone through this case before sure not in weights is false. And then we're on line 30 Wait sum is equal to zero so we just continue and char is an opening parenthesis and Turn on weights is false, line 26, we're gonna increase weight sum to one. And we are going to include our opening parenthesis, and then we're done iterating, we're going to return this as our partial result. So say, Turn. That's cool. So now what happens is, that is our partial result, our processed thing is going to be opening a closing opening. And then our reverse process is going to be equal to opening, closing a opening. Okay, and then we have new weights. We have closing goes to one opening goes to negative one. And then we are going to run our function again, partial result is remove unnecessary chars with our reverse process string, so I'm just gonna copy these letters with the reverse process string and our new weights. Okay, so All right, we just create a little space. And we have opening close a opening is our string. So all right, we have our partial result is this empty array or weight sum is equal to zero. And for a chart in string, so we're going to start with this opening or char in string, char is going to start with our opening character. And char not in weights is false. It's definitely in there. And, okay, I need to make an edit. On line 27. What I want to do is I want to say weights at char in online 28 weights char. Okay. And for our initial case, you know, the opening was plus one closing as minus one, so it doesn't change our existing code. So we have our opening parenthesis. So we're on line 26, we want to do wait some plus, plus weights at the opening parenthesis negative one. Okay, so this is kind of a special case I tried this helper function is kind of let's see, we have want to make an A Quick Edit to this. So what we can do is, we can say, if we sum plus, weights, char is less than zero, continue. And likewise, we can say, can add this code down here. If weight some post weights, that chart is less than zero, just to make it generic. In fact, now that I've now that the actual code here is the same, we can just yeah, we can actually just remove the if char is equal opening or if char is equal to closing. And okay, so All right, so with this change, hoping that it didn't break any of the existing code. Alright, so we're the first opening chart weight sum is zero. And weight sum is zero plus weights at Schar is going to be less than zero. So we're going to continue. So our next character is going to be the closing parenthesis. And okay, turn on weights is false. Weight sum is still zero posts weights of char, that closing proceed contributes one. So that's going to be this condition is going to be false. So our weight sum, we're going to add that weight, which is one, so weight sum now becomes one, and then we're going to append to a partial result. So our partial result is going to start with a closing parenthesis. And then we're going to go to their next character, our next character is a and char not in weights is true, so we're just going to append it. And so our next character is going to be a closing parenthesis, where it starts opening parenthesis, the opening pregnancy contributes negative one, turn on weights as false weight sum plus weights, it's going to be equal to zero, so this condition is going to be false. And then we're going to adjust weight son to be zero. And then we're going to append this new character, the opening parenthesis, and then continue with the end of our loop, we return partial result. So we end up returning this array with three elements in it. And now we are on line 85. Remove unnecessary characters, we're going to reverse this. So we say partial result is now equal to opening a closing, and this is an array, so has three elements in it. And then we want to return a string of five version of this. So opening a closing. Alright, so that is our return value, just a surrounded by parentheses and taking a look at our input. That looks like what we do want to return. So let's just pass that test case. You have any follow up questions where I could talk about other edge cases? And just make sure it's working appropriately?

Clandestine Hamburger: Yeah, can you try this case, actually, from the example, try this.

Aerodynamic Raven: Okay, so All right, I'm going to go through this a little bit faster. So what's gonna happen is we're going to remove unnecessary characters, the opening will contribute one, so we start appending opening character, we have another opening character, we all also put our weight some currently two are closing character weight, some becomes one, and we have an opening character, it becomes to our we have a closing character, it becomes one, we have an opening character, and it becomes two. So the first pass is going to not actually remove any characters. Alright, and then what happens is, we're going to reverse this. So reversed is going to be it's going to look something like opening, closing, opening, closing opening opening, the weights are now reversed, no weights are going to be closing is one opening is negative one. So as we process this, our result is going to be just from the next function call, we're going to for the first character, we're not even going to add it because it's just going to contribute negative one to the second character, we are going to add it because it's going to contribute one and our weight some only one. And for the second character, we want to add it our weight sum is now zero, the next character is opening. And this is contributing one. So our weight sum becomes one, then we have a closing character that contributes negative one, we can add it in our last closing character, we don't add it just because it's it would you know, bring our weights and negative. So our next partial result is that what we end up doing is reversing this so result becomes opening, comma, closing, opening, closing Okay, and then we ended up string finding this so we get open and close, open and close.

Clandestine Hamburger: Awesome. Is that what's the space and time complexity again?

Aerodynamic Raven: The time complexity here is going to be linear because each of our removing the serie characters functions is going to iterate throughout the whole string. The space complexity is also going to be linear because we have some we have our partial results. variable we also have a reverse process string Um, so yeah, linear time linear space.

Clandestine Hamburger: Okay, great. You are just in time, actually, you finish a little bit earlier than the time limit. So that's great. Congrats. I would like to give you some feedback. Both of your questions, you got the optimal answer the is palindrome, this just, you were able to identify the bottleneck, which is in the is palindrome, and you can make it a constant time, I'm sorry, constant space, which is great. I also like how you communicate regarding to, you didn't jump to the solution right away, but rather ask some clarifying questions, you have to remember to do that, ask some clarifying questions, ask for constraints, that's great. You also got the edge cases to make the code simpler at the end. And I like how you organise your code into a helper functions, like you did for palindrome and the parenthesis. And then your code is pretty easy to read. And when you test it, I really, I really liked how you test your code, because it's pretty clear to me about how much you're thinking and running through the code because we are not executing the code. So running by hand and showing all the variables here it is very, very clear. And yeah, this is the most optimal answer and within the 20 minute time, Mark. And the next one is, it's a pretty interesting approach that you have you do the two scan forward and backward, and you came to the right answer. So yeah, that's a complexity linear. That's the most optimal answer. And how you test it, it is very clear to me on how this works. So that's great. By the way, for the second question, I would like to show you another way to solve this, which is using as Yeah, so it's not necessary to make it in this in the interview, because you've got the optimal answer already. But I just want you to think about what would you do with a stack if you want to use the stack for this to solve this problem,

Aerodynamic Raven: Right. Okay, in that case, okay, a stack would, let's see, we have opening parenthesis. And if we have a closing parenthesis, that doesn't match with an opening parenthesis, and we know that we could immediately get rid of it. At the end of the scan, I'm trying to think of how I know we can get rid of closing parenthesis with the stack, I'm trying to think of opening parenthesis, so I'm looking at line eight. Maybe we could repeat that process on another stack. So we would do what I just described for the first step, we'd have a second stack, and we'd pop each of these elements to that second stack and repeat that and then pop all those elements and just convert it into a string. So that would be one approach.

Clandestine Hamburger: I see. Okay, I have seen another approach of stack, which is keep track of the indexes of the opening parenthesis. And then when you, you come to the closing parenthesis, then you you peek on the top of the stack and remove the index of the polling parentheses. That means if you come to the let's say, you're here. You're here and then you push this to the faculties number zero, you put number one, and when you come to the closing, you can just pop number one. And then by the end of the scan, we will get the Oh I see. Yeah, whatever you have. Yeah, opening actually was a simpler way of doing it. Yeah, actually, what this lesson does, that will be something that you can remove. So after you have done the scanning, you can remove all the indexes and you have another array that you could put to keep the index of the extra closing parenthesis. For example, you have this one. You know that there's no that the stack is empty, so there's no opening parenthesis so you can keep this number zero to the other set. And then you can remove it. That's another way but module this is also pretty pretty great. Yeah, we have about 10 minutes left. Do you have asked me any questions about the interview process? Or if you really want another question, let me know.

Aerodynamic Raven: Yeah, we could try another question. See how far I get through it in the time we have.

Clandestine Hamburger: Yeah. It's just 10 minutes. So let's see if we can make it, I don't mind if you can not make it. So, given a grid of characters, I give you an input string, an array of string, you'll find if each of this word exists in this grid. So how to find it, the adjacent characters. So for example, the word Fez is pretty obvious here. But the word book is already it's also here, because if you start on V here, you can both of the FTS and all n k above what good is also here, G, O and D above, but not the word, but so you just output whatever exists in this screen.

Aerodynamic Raven: Okay, all right. I can use once?.

Clandestine Hamburger: You can use each character only one time.

Aerodynamic Raven: Okay, got it. So, all right. In this case, the time complexity, I'm thinking of doing kind of like a, what is it a depth first search approach, each depth first search is going to be you know, size of grid. Because we're gonna have all sides of grid different start points, in this case, four times three, which is 12. And, okay, so let's say we start this depth first search approach, we have, you know, G, the total number of iterations is actually going to be, actually can be quite a lot, it can be up to size of grid, again, it would actually be min size of grid, and size of word. But we could also look at all the different possible directions there. So I think it's really just going to be sighs of grid type size of grid. So I know, I think I know how to do it. And just thinking about how I would, what kind of optimizations that I'd be looking to make here. So let's say there are a few constant time optimizations, like I can check the characters in the you know, in the grid, and just you know, see if there are certain impossible results, like maybe the character count in the grid for each of the characters in a given word is less than it so for example, if you had F A z as a, you know, as a word, we know that we wouldn't need to compute that. But in any case, some from the code might look like for word in input, and we'll have our root result is np array. And we can say, for let's see, row in grid and T. will say for row one rows will say rows is Len grid calls is Len grid at zero. So for row in rows for call in calls. This is actually I have to use range, because rows is an integer causes an integer and we could say if DFS we have our grid, we'll need some visited set. Read word start sorry, grid word. row column will be the starting point. And we also want the word index. This is result. Append. Word. By the way, will our input have duplicates?

Clandestine Hamburger: The input, no duplicate

Aerodynamic Raven: Okay. And we'll say i j, and word index Okay. And also I need our visited visited character. And if word index is greater than equal Len word return true. And, okay, if see, if I come on J in visited maybe we'll return false here. And okay. So if grid i, j is not equal to Word at Word index return false. What we do is we want to get a list of neighbours, there's another helper function I'll say neighbours is get neighbours grid and to positions i n j and for neighbour in neighbours if, let's see DFS grid word will say, new I new j is equal to neighbour we have new new J word index plus one and we want visited but we need to update visited. So, let's see when we check if on 114 visited dot add i comma j, so we don't use the same space twice. And cool. So if this return true. And if we get down here we are going to return false for a good neighbour function.

Clandestine Hamburger: I get that verse that you mean to get the adjacent and within the bounds of the grid. Practice, right?

Aerodynamic Raven: Yep that's correct.

Clandestine Hamburger: And you don't need to do that I got it. So I think overall your approach was good. So what would be your space and time complexity on this one?

Aerodynamic Raven: Okay, so we just calculate this, let's say our grid is n cross m, and words is W in size that's on line 12 and 13. So we have time, and we have space. Alright, so as far as time goes, let's see, we are going to iterate through words. So it's w times something. And we're going to iterate through row and column. So n times m, just to start, and we're going to call DFS, the most that we can continue with DFS is the size of the word, or the total number of grid spaces. So I can say that min of n times n, we're, let's see, when I say the length of the word, we actually are going to look at our neighbours.

Clandestine Hamburger: The length of each word is constant. Let's say like they're always four.

Aerodynamic Raven: Okay, got it. All right. So if it's always four, then it just comes down to how many spots can we explore? If we have four? I think using n times m is probably the safer approximation. Okay, so our time is going to be n squared m squared times w w is the total number of words and as far as space, so when we do DFS, we have our visited set, and it's going to grow a bit in size. So our visited set can be at most n times m in size. We also have the DFS callstack and that can also be n times m, so DFS call stack and our result is going to be sized W Two sides W resort. And these exist separately of each other. So I think it's going to be n times m plus W. Space.

Clandestine Hamburger: Okay, cool. I think you got it. So yeah, great job. I think you've got all the communication, problem solving, writing, translating your idea into a good code, clean code, and to testing and analysis. I think you will nail it. Good luck.

Aerodynamic Raven: Thank you. Appreciate it.

Clandestine Hamburger: Yep.

Aerodynamic Raven: All right. Goodbye hamburger.