Minimum Window Substring (Java)

Watch a Java mock Interview with a FAANG software engineer. See someone try to solve the minimum window substring problem.

Interview Summary

Problem type

Minimum Window Substring

Interview question

Given two strings s and t of lengths m and n respectively, return the minimum window substring of s such that every character in t (including duplicates) is included in the window. If there is no such substring, return the empty string "".

Interview Feedback

Feedback about Declarative Bandersnatch (the interviewee)

Advance this person to the next round?
Thumbs up
How were their technical skills?
4/4
How was their problem solving ability?
4/4
What about their communication ability?
4/4
Strengths: + TC clarified all important details regarding the input. + TC explained their approach by running with example. + TC identified sliding window pattern for solution early. + TC wrote easy to follow code with good naming conventions. + TC handled the edge cases like empty string well while writing the code. + TC debugged their code while working with example test-case. Improvement Areas: - Overall speed was on little slower side which did not leave enough time for me to ask follow up question. Suggestion: 1. Try to skip running through example while discussing the approach. Overall Hiring Decision: It will be leaning hire. Could have been hire if there had been enough time for follow up question.

Feedback about Red Maelstrom (the interviewer)

Would you want to work with this person?
Thumbs up
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)?
3/4
N/A

Interview Transcript

Declarative Bandersnatch: Hello.
Red Maelstrom: Hey hello, am I audible?
Declarative Bandersnatch: Good, how are you?
Red Maelstrom: I'm doing good. Awesome. So let's start with the coding questions. We will spend like 45 minutes on coding, like the last 10-15 minutes on the feedback.
Declarative Bandersnatch: Okay, sounds good.
Red Maelstrom: Sure. I'm just pasting the question. So basically you have two strings, S and T of length, M and N, respectively. You have to return the minimum window substring of an S such that every character in it, every character in T, including duplicates, is also included in this window. If there are no such substrings, return the empty string. So if you look at example one, ABC, you can also have ABC in the substring, right? This window also has A, B and C, and this substring also has A, B and C, but the letter one is smaller. That's why it's.
Declarative Bandersnatch: Okay. I just want to ask a couple of questions to clarify. So in this, in the examples, there are capital letters and lower case letters. Are these the only kind of characters that can be in the string or could have, like, punctuation, like exclamation points, periods, et cetera, that kind of stuff?
Red Maelstrom: That's a good question. Let's assume that it just has capital and small letters.
Declarative Bandersnatch: Okay. And also, can either of the strings be empty S and T?
Red Maelstrom: Yes, in that case output should be empty.
Declarative Bandersnatch: Okay, and what would be the max size of the two strings? Sorry, could you say that again?
Red Maelstrom: Ten to the power of five.
Declarative Bandersnatch: Ten to the power of five. Okay, so the goal is we want to find every character in T is included in the window. Okay, I think I understand. So I guess how I want to approach this, kind of like the question says, we want to have a window to keep track of when all the characters are in our window. So first things first, we would have to know the characters we're looking for. So what we want to do is count the occurrence of every character in T. So we could do something like that, maybe with a hash map, and we would say in this example, for example, there's one A, there's one B, and there's one C, one C. And so once we have that information, we can start counting. We can start looking for our window and our mainstring, right? So take this down here. So this is our mainstring, right? So what we want to do is we can have a pointer. What we'll do is actually have two pointers. So we'll say like a first pointer and a second pointer. And basically what we want to do is every time we see a character in a character in T, in our little hash map over here, we should move our second pointer up and start looking for the next character. For example, A to start is in our map, right? So we have an A. So we would push this pointer up, and because we've counted an A, we should keep track of the characters we use. So since we use an A, we can increase this down and say we don't need any more A's in our window so then we should keep looking. So D is not in our window, so we'll keep looking. O is not in our window so then we move a pointer up again and then we say B is in our window so what we can do is we can use a B and we can decrease the number of bees we've used and we should keep looking. So we keep going. E is not in our map so we're going to keep going. And then now we've got a C is in our map so we'll decrease it. And then once we see that we've used all the characters in our map, the three characters, what we can do is we can save the size of our window because it's possible, like there's a smaller window. So I think the first pointer is at index zero and the second pointer is at 012345 at index five, which would give us a size of six characters so we could have some min to keep track of our minimum window and we'd say the minimum size of six. And the reason why I would also take note of where the pointers are is because we're not returning the length of the minimum or actually turning the actual substring. So we're going to need to know where the substring starts and ends to return it. So I would keep track of that. And then I guess the next thing to do would be keep pushing our second pointer up, looking to see if we can get another one of these characters. Maybe we would want to push up the front pointer. Yeah, because we use these first few characters so we can push the first pointer up and say, okay, now we're no longer using an A, so we should actually put this back and say that we have an A that we're looking for now. And every time we move a pointer we'll check, right, like is our map empty if we use all the characters? Obviously right now we haven't. So what we'll do is we'll keep searching for another A to see if we can find one. So we'll push up the pointer. There's no O in our map. We'll push up the pointer, we're at a B, so we've used up the B, so that's not going to help us. And then we push our pointer again and since B now is no longer in our window, we have to put B back in our map, right, because we need to find another B again to make sure we have the right window substring. So we'll keep looking. We'll push our pointer up again, keep looking. And then now we're at C. And then once we can say once the first pointer is equal to the second pointer, we should start looking, moving our second pointer again, looking in our window again. We'll put this back because we basically need to look for every single character again. And then we'll push both of these pointers up because we're no longer using a C and the s, we're going to move the S now to search for characters. So we would keep going, we would push S. The D is not in our map, we push S. E is not in our map, we push S, okay, B is in our map. So we'll take away B from the map and we'll keep looking. Push up, a is in our map so we'll take A away from our map, that would be zero and then we'll keep going. We'll push S above again and then N is not in our map so we keep going. We push S again, we're at C so we can take C away. C is in our map and then what we'll do is we push this up one more time, right? And then basically we would say, okay, we found another substring. So now we want to check is this smaller than the other substring we already found? And in this case I think the size is bigger. Yeah, it looks like seven letters. So we've would just keep our minimum the same. And then the next step is to try to decrease the size of our window and see if we can find a smaller one. So now we're going to come back to this first pointer and push it up always in our map, we don't need to do anything. So now and every time we'll readjust the size well, every time we'll check okay, have we still used all the letters? Yeah. Okay, what's the size? The size is now six so it's the same, it's not going to change. So we'll push the first again. Now this time we still use all the letters and the size is now five so we can actually say the minimum is five. And we'll say that the first pointer. I think this is 234-5678, this would be index eight and then we would save the last pointer, which I think is going to be 910, 1112, 13, so it would be 13 and then we continue doing the same thing because we want to go through every possible window substring. So we push F up again, we still have used every character and we check the size. Now the size is four. So now we got to resave our pointers. So I believe this would be nine and the last one is still 13. That hasn't changed. And then we'll push up our pointer again. So now we've gotten rid of a B, so we put the B back, there's one and now we're not going to adjust the size because we're missing a character. Then we keep going until our first string meets our second string. So we've lost an A, we got to put an A back and then we push our pointer up again. And there was no end, so we're fine. Then we push our point up again one more time. We put C back and then now both pointers have passed the string. So we've checked every possible window substring and this is our smallest. So now that we have these indexes, we can just return the substring at these indexes. So that, I think, is one way we can do it. I think if we think about the space complexity, we're going to need to have N space, where we can say N is the number of characters in T because we're going to have to keep track of every character in T in some sort of map. And then if we think about the time complexity, looking up in the map is going to be constant time. So that's fine. And then as we iterate over the string S, we're moving two pointers, but we're never reiterating over the same characters multiple times. We're just keeping a sliding window so we can say that the time complexity of to iterate over the T string, we can call it O of M, where M is the number of characters in T because we have to go through every character in T at least once. So I think all of them time and all of them space is the sufficient solution. So I think I'm going to go ahead and code it.
Red Maelstrom: Basically, let's say if there are multiple A in between, how will your sliding window take care of it? Will it go in negative?
Declarative Bandersnatch: So if there was two A's, so what would happen is, let's say this was we had something like this, whatever, ABCG, and we have only one A, right? So we have our first or second. So we would push our second, we have zero. And then now if there's another A, essentially like it's almost as if we don't have an A, so we're going to skip over, basically, we're going to push up and we're not going to change. Should we go negative? Let's see if if we go negative, let's say we call that negative one. And then we keep looking. We go up, we have a B, that's zero. We go one more time, we have the C at zero. So in this case, this is a valid window because that's the three characters. So I think this size would be I don't know, we call that four. Yeah, four characters. But then now we have to push our first pointer upright because we found a sufficient window. So if we push this up, we would put the A back, which would make it zero, and then it would still technically be valid because these are all zero or less. And then the window suffering would be three. So yeah, basically, if we have a duplicate characters, we can go into the negatives because we'll count them later, we'll count them in the window at a later time. Like in this example, we have the first window where we include both, which is valid, and then we count the smaller window. So, yeah, if we have duplicates, we'll put our map values into the negatives.
Red Maelstrom: Understood cool yeah so let's try it.
Declarative Bandersnatch: So we're returning a string, right? Public string. The goal is to find min window sub string. Then it's going to take a string. We called it there was an S and the other string we called it T, right? Do you want me to include a class as well or just a function fine?
Red Maelstrom: Just functions fine.
Declarative Bandersnatch: Okay. So first things first. We said the strings can be empty, right? So we want to check for that edge case. So if S is empty, so if S length equals zero, it would not be possible, right? Because there's no characters return the empty string. If there is no such substring. I guess technically if both are empty, then we would still turn empty. Yeah. So if S is empty, we'll return an empty string. And I guess if T is also empty, roll will return an empty string. We'll return an empty string. And then in the case where if there's characters in S and there's no characters in T, I guess technically we would return all of S, right? Like if we had ABC and then T was just an empty string, then technically the entire string is valid as part of the window. Or it would be there's no substring. Yeah, that would be there's no substring. I think we can say. Well, just say or here actually, if either one of these is empty or turn empty string. Okay, so that handles that case. And then what we want to do now is we need to count all the characters in T, right? So what we'll do is we can use a hash map, like I was saying, or we can also try to use an array representation of the hash map, which would just be a bit better because we can avoid collisions if we use an array representation. I think for now, I'll do a hash map and then later, if we have time, I'll switch to the array representation. So what we'll do is first we're going to need a hash map. So we'll see hash hash map. It's going to be a character as a key and an integer as the value. And we'll call it chars in T. And then what we'll say is equal to new hash map, right? And then that's the hash operating need. We also need to keep track of a minimum. So we'll say Min window and we'll set this to the Min is the largest way the window could technically be the whole string. So we'll say s.length and then what else do we need? We are keeping track. We need pointers. So we're going to say I will say int first and equal zero. And we'll say second equal zero. So I think these are all the variables we need. So now let's put everything in a hash map. We'll say four dot char c and t dot to char array for every character and t. What we're going to do is we're going to say chars in t put if absent. So we'll put in the character C and we'll just put in zero. And then the next line will say chars in t dot put, chars in t dot get c plus one. And we got to put the character back in. So we're just putting it with a value of one. This would just put the character with zero. And then we just add one to the character because we have to count it once. And so this will count all our characters in t. That's all good. And then the next step is to try to find our window, right? So we'll do a while loop. We'll say while, s is the longer one. So we'll say while. And first is the one we want to say. Well, first is less than s dot link. I will start and we'll say so while that's the case, we want to find our windows. So we'll just say if dot char at second. The map contains it. If Chars in t dot contains, char at second. Then what we'll do is we will say chars in t dot put. We'll just update this. We'll say s char at second. And then we'll just say so we're just decreasing it. Yeah, so we're just decreasing it. And that's then that would update our value. And then once we've done that, what we want to say is we're going to have to do second plus plus. We're going have to to push our pointer up. And then we also want to know when we found our window, right? When we've actually found our window. Actually what I might just I think it'll be a little more simple, actually just. Actually I don't think that would work. I was going to suggest changing all the characters to just be lower and then use the array representation. But I don't think that would work because if we have capital A, lower case A, it would mess it up, right? Yeah. So I'm not going to do that. Okay. We will just stick with the map. I'm just thinking because I need to know when I've got my window, right? I need to know when I found my window so I can check the size, save the size. So there needs to be a wait. Essentially, when hash map, all the values in the hash map are zero. I don't want to have to iterate through check every value in the hash map to see if that's zero. That will take too much time. So I'm thinking maybe what I'll do is have some we'll call it chars found. And basically every time I find a character, I'll increase this. In this case, we found a character. So what I'll do is I'll say chars found plus plus. And then basically once as long as the number of characters I found is greater than or equal to the length of T, then I've got my valid window. Actually, I don't think that's going to work because what if we have two B's? If we have two B's and a C, we'll say we have three characters found, even though we don't have them all found. Yeah, that's going to be a problem. I guess what I'll say is if s dot char at second or what am I doing if char is in T dot get s dot char at second. I think I'm going crazy with the brackets char dot int t dot get char at second. If that is, so long as it's greater than or equal to zero and I haven't gone to negatives, then I'll say I found a character. So I'll say found chars found plus plus. Yeah, I think that's good. If that is greater than or equal to zero, after I've just taken a character away, I'll increase it so it'll be chargs found plus plus. And then we'll say second plus plus. And then the other cases when we start, we want to say if char is found equals equals t dot length. So we found all the characters. What we want to do is we want to save the size. We want to say min window equals math min of the current min window. And the difference between my second pointer than my first pointer plus one because we're zero indexed, so that will save the size of our window. And then after we've saved the size of our window, we have to also save the indexes that we're going to be using later. So I'll actually have one more variable to keep track of the indexes. We'll just say window indexes equals new integer of size two. And we'll just say window indexes at zero equals first and window indexes at one equals second. So I know what substring to grab later. And then the last thing we want to do is we want to move our first up because we want to see if there's a smaller window. So, yeah, that I think is good. We check if we found the character, we push the second up and then I think that's good. So then at the end at the end of our loop, once we're done going through the first or no, actually, chars is found equals and then we go. I'm just thinking, if we have a case where we have a window and there's multiple characters we need to go through, like, in this case, if we have a window, something like this, and we're trying to see if there's a smaller window. I should make this a while loop. Or if that doesn't matter, because I think actually this can be an else. And also I forgot to add back the character and we push it up. So before we push it up, we'll say chars in T dot put we will put back the character s dot char.
Red Maelstrom: Will you push back the character which was not originally present in T also?
Declarative Bandersnatch: Pardon?
Red Maelstrom: Will you push back the character which was not originally part of T also?
Declarative Bandersnatch: Oh yeah, you're right. I see. So what we'll do is we'll have an if. We will say if chars in t dot contains key s dot char at first. So if it was actually in it, then we can add it back. So we'll say chars in t dot put, we'll put s dot char at first plus one. So that will put that back. Only if it's one of the keys that's actually in T, we'll put it back, then we'll push the pointer up. Yeah, so I think that works. And then we'll just keep doing that. Basically if also if we still have a valid window next time, we'll keep pushing up the first pointer so we no longer have a valid window. And then we'll go back to searching through seconds. I think that makes sense. And then at the end of a while loop at the end of the while loop, I think we're missing oh no, it's still here, the last phrase. So then what we want to do is we want to return the string, the substring, right? So we can just use Javas. Actually we need to check one thing. We need to check in the case where maybe we just never found the window, right? It never existed. So we'll know the window never existed. What we'll do is we'll change this to plus one. So that way because like I said, there's a possibility the entire S string could be the window if S and T are equal to each other. So then what we can just do is we'll say if min window equals equals s length plus one, that means we never updated the value of min window, which means we never found one. So we'll just return the empty braces. Otherwise we can just return we want to return a substring, right? So we can just use Java substring function. We can say S sub string and we need to pass in the first we'll say new indexes window, window indexes zero and we'll pass in window indexes at one. And I think we should do plus one. Because of the way the substring works, it doesn't take the last character. The second parameter is not inclusive. So think that makes sense. So I'm just going to run through an example just to make sure, make sure everything works fine. I can just do something similar to this. I'm just going to add some duplicates and maybe I'll shorten the length of it so we'll have something like B. We can even throw in more case letters too. I think this is good enough for me. And then we'll have T. Maybe we can say T is something like we'll say A. Let's do ABC like this and we'll put in one more c just to have a duplicate. Okay, let's run through this. So first things first, let's stick to all our variables. So we'll generate a new hash map. And it's going to put Map for short, to make it simple. And then the next thing we have a min window is going to be the length of min window is going to be the length of S plus one. So the length of this is four, seven. So min window is going to be eight. And then what else do we do here we have a first and second equal to zero. So these are pointers. So I'm actually going to put them right here. And then we'll say chars found. Chars found was zero. And we'll have window indexes right now are just zero, zero. That's how they're initialized. And then the correct answer would be ABC for this. So I'm just going to say results is ABC and we want to make sure we get that. Okay, so you have all the variables declared. First thing is put everything in a hash map. So for every character and T, we're going to put in the map the character. So we got A and then nothing. And then the next line is get A and then add one and then put A back with put a new thing back a with one greater than what it currently is. So this is going to be one and then B is going to be one as well. And C is going to be one. So we built our map now while first is less than the length of test. So we're going to say if chars found chars found. Oh yeah, chars found a zero if chars found equals equals the length of T. No, because it's three, it's zero. So they're not the same. So we're going to skip all this and what else we're going to say. If the chars in T dot contains s chars second s chars second is A, the map contains it. So what we're going to do is we're going to put in the map A, but we're going to put one less than its current value. So A is going to become zero. And then the next thing we're going to do is we're going to say if Chars and T dot get A. So if the value at second, which is A is greater than or equal to zero, which it is, it's equal to zero, we will increase our chars found. So we have one character found. Cool. And then we say second plus plus. And I think, yeah, I made a mistake. This second should be in this else if because we don't want to push the second up if we only done with the first one. So, yeah, we'll push the second up and now we're on to the next character. So the next step is same thing. Chars found is one, the length is three. So we're not going to run this. We're going to go to the else if. So we're going to say if the chars in T contains s char at second so the map does contain A. So what we're going to do is we're going to put in A one less than what it is currently, so it's going to become a negative one. And then we're going to say if A's value is greater than or equal to zero. Well, it's not. So we're not going to increase our chars found. So we're simply going to say second plus plus. And then just for time sake, same thing is going to happen. Exact same thing. We're just going to push past A and this is going to be negative two. And then now we're on B. Right. And also actually, I think I was too out of myself. I think this is supposed to be outside because if we have like a random, random letter, we have like a K here. We need to push up second, otherwise the loop will go endlessly. So that's why we have to have the second plus plus outside. Both of these if statements would be false on the K. And then we push the pointer up. Yeah. So it should be like this. And then now we'll check again. Chars found is still one. The length of T is three. So we're not going to run this. We're going to go to the else if. So we're going to say is the character at second, which is B? Does the map contain a lower case B? Yes, it does. So now we're going to say put in the map one less than the current value of B. So it's going to become a zero. And then we're going to say, is the value at B, is it greater than or equal to zero? Yes, it is. So we're going to increase our chars found by one. It's going to be two. We're going to push the second one up, second plus plus. Then we're going to be on a C. And now we're going to say same thing. Is chars found equal to the length? No, two is not equal to three. We go to this else if we're going to say, does the map contain the character at second, which is a C? Yes, it contains a C. So we're going to say put in the map the same character C, but one less than its current value. So it's going to become a zero. And then we're going to say, is the value at C greater than equal to zero? Yes, it is. So we're going to increase chars found by one. So it's going to be three. And then we're going to push the pointer up. So we're going to go to here. And then now if chars found equals equals T dot length, that does they're equal. So we're going to say the minimum window is second minus first plus one. I think this might be a mistake. So if we skip first there's how many characters? 123456 characters. But I think I have here second minus first is. Going to be seven minus 0012-3456. And there's six characters. So let me get rid of this plus one. Actually, the way I'm doing this actually should keep the second minus first. So this would be six minus zero, which would give us six. And that is smaller than eight. So our new min window is six. And then we'll save these indexes, right? So indexes first. So where did I put these here. So first is a zero and second we said with six. So we're going to save these and then we are going to say does the map contain does the map at first, which is an A, this capital A here, does the map contain it? Yes, it does. So what we're going to do is we're going to add we're going to put back in the map in A with one more than its current value. So this is going to become negative one. And then we're going to push first up and here. And then we're going to continue with our yeah, this is a problem because we push second up. We don't want to so we want to push second up. We can say second plus plus here. And then maybe if we just say else second plus plus. Then in this case, if both of these aren't true, we still push second up. In this case. Second is in this case. We just run this statement. These two else's don't run. So second will stay the same. I think that's the appropriate fix. Now we check again, basically. And chars found. Do I ever change the value of chars found? No. Okay, that's another problem because we need to change the value of chars found. So what I'll do is once we put it back, we'll say if r's in t dot get s char at first, if it's greater than or equal to or no, if it equals equals one, if it's now greater than zero, that means our found chars, we don't have all the characters we need anymore. So let's say found chars minus minus. So in this case, our found chars, it won't change because the value is negative one. So we still found three characters. So that's good. So the next step is and the loop is going to continue. So now charts found is still three. The length of T is still three. So we're going to grab the new minimum window. So second minus first in this case is one minus six, which is five. And so window is going to be five. And we're going to update this to be one and six. And then we have to increase this A by one. So we'll say A is now zero. And then we're going to say, is the value at A equal to one? No, it's not. So our found chars is going to stay the same. And we push the first pointer up. So this is going to come here now. And then we're going to go back to the start of the loop because these two else's aren't going to run. And then chars on is three, the length of T is three. Then we're going to grab the new min window, which is going to be six minus two, which is four, and then we're going to say two and six. And then we're going to say is the value at first in the map? Yes, it is. A is in the map. So we're going to say put back in the map one more value than the current value of A. This is going to be one. And then we're going to say if the character A is one, then we'll say found chars minus minus, which it is. So we're going to decrease found chars to two. Oh, I called it found chars, it's chars found. And then we're going to push the first up like this. And then these two elsewhere aren't going to run. We're going to restart the loop. Now we're going to say two is not equal to three. So we're not going to run this. We're going to do this else if. We're going to say is the current character I think that's a K. Yeah. Is the current character K in the map? No, it's not. So we're going to go to this else and we're just going to push the second pointer up. Yeah, we're going to push the second pointer up. Wait, our minimum window? Yeah, that's right. Actually, we're going to push this. I forgot I changed the problem. We're going to push the second pointer up oh my bad my bad. No, I was looking at first, not second. We're actually looking at the second. So we're going to say is the C in the map? It is. So we're going to put one less than the current value of C, which is zero, so it's going to become negative one. And then we're going to say if the value is greater than or equal to zero, the character found is we're going to increase the value of the character found, but it's less than zero, so we're not going to do that. And we're going to push our second up. So we're going to say second plus plus. So we're going to push the S up and then we're going to get to B. And then at capital B we're going to say is chars down equal to the length of T? No, it's not. Two is not equal to three. So we're going to come this else if it's B in the map, capital B and what's not. So we're going to go with this else. We're going to push second up. And then actually what's going to happen here is we would actually get an index out of bounds at this line because there's no more characters. Like we would check this, this would be true. So we check this else, but second is out of bounds, so we have to fix that. So if this is the case, I think if second is out of bounds yeah, I think we can actually do in the second one, because based on how our window works, if you had ABC in here, our window would still be valid. So we would never get to else if. Once it's done, we can end the loop and then loop would be done. And then we'd say is the min window equal to the S lane plus one. Then we'll just turn the substring windows at index zero, which is two and windows at index six plus one which is seven. So I just want to make sure that's right 20012 so we'd return A and then three, four, five so we don't need the plus one. Actually we should just keep it to this. So it would be two and six. And like I said, the substring the last value is not inclusive so it would end up returning that substring of AKBC. So. Yeah, I think I'm sufficient. I'm satisfied with the solution and like I said, the time complexity is O(M) where M is the number of characters in S and the space complexity can be O(M) where M is the number of characters in T.
Red Maelstrom: Understood? Yeah. Cool. I think this should work. So I'm just trying to go through the code once. Give me just a minute or two.
Declarative Bandersnatch: Sure.
Red Maelstrom: Cool. Let's move to the feedback part of it. I think you really started well by asking really good clarification question like whether string can contain the special characters or can string be empty? Any of the string can be empty. What would the output in that case? Right, yeah. We also asked what would be the maximum length of string so that we can have found on the time complexity of algorithm. I think that's a good thing. I found most of the candidates missing on asking these questions about what characters can be involved in a string. Right, so good that you did and you also come up with sliding window approach because that's what will be used to identify the pattern in this. And you also handle well the education where either of the string can be empty. When we started writing code you also debug yourself the issues in your code and rectify it. Right. So I think you click on all the check boxes. The only thing which could happen include is there could happen an easier way to write this code. There could happen rather than having just one while loop inside it you could have things like keep it rating unless you found a match or keep it rating unless you found the first character which will bring the out of it. But I think like saying is easier but like you are trying to solving this problem first time considering that thing like it's a good course. So yeah, I think you did really well. Only thing would happen is like you would have done the implementation part a little faster. Right. So basically I think five to ten minutes faster would have been a good thing because I was trying to ask the follow up question on this, just the approach of follow up question, not the code. So I think overall on the speed side, there was like a bit the speed was on a bit of slow mostly on the implementation part. And also while explaining it, you could have explained it more rather than going with example. Basically we could have say like five to ten minutes in between and had some time for the follow up question.
Declarative Bandersnatch: Okay.
Red Maelstrom: That's the only issue I'm having I have from this thing. But overall, if it was a good thing, I think you have a good framework clarify the question, you share the proof, you identify the complexity by yourself and then only you went on coding it. So, yeah, I think in terms of your structure or of course, I don't have any recommendation, but maybe like a bit time check could be useful, like making sure that you have some time for follow up or something at the end of interview.
Declarative Bandersnatch: So do you think then just for when I start coding and I'm explaining kind of my thought process, So you don't think like running through an example is necessary? As long as I kind of just talk through what I'm going to do.
Red Maelstrom: I think, yeah, approach wise, it's not necessary to talk through with example. That could save some time. Okay, yeah, but what do you need once you have done with the code running through example? That makes sense because there you discover the issue with the code running your approach through example at the beginning that could have been avoided.
Declarative Bandersnatch: Okay, yeah, but sometimes it might happen.
Red Maelstrom: That approach is tricky and interviewer might ask you to go through. Can you help me how it will go work with this example? At that time you don't have option but to go through it.
Declarative Bandersnatch: Okay, cool.
Red Maelstrom: Do you have any specific interviews lined up?
Declarative Bandersnatch: Yeah, I have on Wednesday my interview with Google. So I've just been practicing.
Red Maelstrom: Understood, understood. Cool. Awesome. Is it for L three or L four?
Declarative Bandersnatch: For new grad. I think that's l three.
Red Maelstrom: Right, right, cool. I think for Google, my suggestion would be like to also have some time. Is it just a coding interview or all the interviews on that?
Declarative Bandersnatch: All of them in one day have three technicals and one behavioral. Yeah.
Red Maelstrom: My question would be like to also have some examples written on a document so that you get in a structure of like star format, situation, tasks, action and result. Right. And have some numbers back in those things, like how much time it took for your project, how many people were in it, things like that.
Declarative Bandersnatch: Okay.
Red Maelstrom: All the best for your actual interview.
Declarative Bandersnatch: Yeah, thank you. Thank you so much for taking the time to do this. Appreciate appreciate it.
Red Maelstrom: I think you need to write a feedback after this.
Declarative Bandersnatch: Yeah.
Red Maelstrom: Thank you. Bye.
Declarative Bandersnatch: Thank you. Have a good day.
Ready to practice with a mock interview?

Book mock interviews with engineers from Google, Facebook, Amazon, or other top companies. Get detailed feedback on exactly what you need to work on. Everything is fully anonymous.