Google Coding Interview With a Meta Software Engineer

Key Takeaways

$194,000 is how much Google pays their new grad software engineers. It's a crazy amount of money, which also means crazy competition and notoriously difficult interviews. So, today I'm pulling back the curtain and I'm hosting a mock coding interview with the former meta software engineer. I picked an actual question that has been used at both Meta and Google for their interviews. And my goal throughout this is for you to really understand how a top 1% software engineer really goes about problem solving. And as you're watching this video, try solving the question on your own. It will be challenging, which is the whole point. When I present the problem, pause the video, attempt a solution, and then come back and see how the XMA software engineer tackles it. And with that being said, let's get into it. Hey Connor, how are you doing today? >> Good. How are you? >> Good. Good. So, today we're going to go over a coding interview question. You're going to have about 20 30 minutes. I'm going to paste a problem for you to solve. The most important thing for me is I want to really hear your thought process as you're going through the question. whether you actually get the right answer or not. I'm more interested about your problem solving. So, are you ready to get started? >> Yeah, let's do it. >> All right, cool. Let me paste the question for you real quick. Given a string s of open parenthesis, closed parenthesis, and lowercase English characters, your task is to remove the minimum number of parenthesis in any position so that the resulting parenthesis string is valid and return any valid string. Formally a parentheses string is valid if and only if it's an empty string contains only lowercase characters or it can be written as a b a concatenated with b where a and b are valid strings or it can be written as parentheses a closed parentheses where a is a valid string. >> So just to clarify if we come below here if we do like this is I would assume valid this is not. So the idea is just same number of opening and closing and then like something like this that would be valid right? Yes. And then does the order matter here? So if we did like this or wait that's still something like this, right? That's not valid, right? Even though it has the same opening and closing, they're just like in different orders. >> Mhm. Correct. So to make it clear for you, let me actually paste in an example in terms of looking for minimum number of parentheses. Uh as you can see, we effectively based on the input, if you kind of think about it like a dangling parenthesis right here. Yeah. that isn't necessary for the output. And essentially it being a valid parenthesis, there's no opening for this one. >> Yeah, that makes sense. Cool. So, sort of what I'm thinking is, yeah, like I said, the actual English characters I think we mostly just ignore and just have to preserve. Uh, and then for the opening and closing parenthesis, a opening parenthesis always has to come before closing, right? So if we sort of iterate through our string, we have like the three letters that we're ignoring and then we have an opening parenthesy, which is good. And had we had a closing parenthesis there, we just remove it because at this point we've seen no opening parenthesis. So no need for it. And there's no way that that could possibly be part of a valid string. And then if we see an opening parenthesis, we can kind of just keep track of uh sort of like a we could do like a count. So say like at this point if we see an opening parenthesis we know okay we've seen one then we see another or we see a t we can just ignore that we see another opening parenthesis so at this point we have two and then we see a closing parenthesis so that sort of undoes an opening so now we have like one sort of dangling opening if you will and then we have >> another closing so now we have no dangling openings and then we get this last closing so we'd have to remove it because there's no corresponding opening um I think the edge case for just counting might not work though is if the opposite was true. So if the actual issue was so say we had like this um now we need to remove our opening parenthesis and if all we did was we got to the end and we're like oh count is one or two we don't know what to actually remove. >> Um so rather than just a count I think we have to keep track of like the indices of our parenthesis. So I think what I want to do is essentially iterate through the string, ignore all of the English characters. If we get an opening parenthesis, keep track of it. Um I suppose we need the last opening parenthesis corresponds like the next closing parenthesis. So it's sort of like a stack type of structure, I suppose. Um to keep track of the last one we got. So we get the index of the last opening parenthesis we saw and then the index of the next one. And then once we get to a closing parenthesis, we say, "Okay, that went with whatever the index was of the one we just saw." So remove that from the uh stack. And then if at any point if we see a closing parenthesis that and the stack is empty, we remove the closing parenthesis. There's no corresponding opening parenthesis. And if we get to the end of the string and we have extra opening parentheses, we go back through that stack and remove those from the string. >> Does that sort of make sense? >> So effectively are you you're storing the indices of opening parentheses on stacks? >> Yes. >> Okay. So if we have opening parenthesis uh a opening parenthesis b and then we'll have for now let's just do one closing parenthesis. So we're going to start at the beginning of the array and we're going to say essentially okay our parentheses are at zero currently. So I'll make like a stack here and in this stack we will have currently we've seen a parenthesis at zero and then we move on. We see an a. We don't do anything with the a and then we get another opening parenthesis. This one is at index uh two. So we'll add that to the stack. And then we get the b. We do nothing. And then we have this closing parenthesis. And when we see a closing parenthesis, that means, okay, this corresponds to the last opening we just saw, which was at two. So, we're going to pop two off of the stack. Just erase this here. And now we're at the end, and we still have something in the stack, and that's index zero. So, that means index zero was an opening parenthesis that had no corresponding closing parenthesis. So, that means in our initial string, we just need to remove whatever was at index zero. and we should have a correct solution. Um, and sort of the other possible scenario is we get to the end here and we have say two more closing parenthesis. So when we get to this next closing parenthesis that would remove index zero and then we get to the last one and this one we have nothing in the stack. So that means we had the extra closing parenthesis in this case. So in this case we would remove that last one. Does that make sense? >> Yeah. So, what are we looking at for time and space complexities? >> Yeah. So, we're doing one iteration through the string, right? So, we're just going through all the characters. So, that's sort of O of N. And then after we do that iteration, we have to iterate through the stack to remove everything from the stack. removing from the stack is O of whatever the max size of the stack is which is O of the number of like opening parenthesis but we could call it O of N if N is the number of characters and all of the characters were an opening parenthesis that would be the size of the stack we'd iterate through the whole stack removing from the stack is of one and then let's see so the actual like core part of the algorithm before we do the removal from the stack we iterate through every character uh what do we have to do for every character so if it is an opening parenthesis we push it onto the stack which is going to be of one. And if it's a closing parenthesis, all we do is remove something from the stack um which is also going to be of one. And then the only sort of other edits we do are just like editing a string just removing like one character um which is not going to have any effect. So yeah, I think we should be over time and and the stack is our space. So oven space as well. Uh but really the stack's maximum size is the number of opening parentheses which is likely much smaller than the size of a string but obviously it depends on what input we get. >> Yeah, we could get like an edge case, right? So >> yeah, >> would love to see it in code. >> Cool. Let's do it. >> All right, so uh what coding language are you going to use? >> Uh let's use JavaScript if that's okay. >> All right, sweet. So I'll come down here say function and let's say remove extra PNS or something like that. And is this just going to take in just the string? Correct. >> Yes, just the string input. Yeah. >> All right. Cool. Okay. So the first thing we want to do is iterate through the string. It might make sense. I think it's going to be easier if the string is an array just to actually handle it. Just an array of characters, which sort of the same thing. Uh, I just think it's going to be easier codewise. So, let's actually do that. So, let's say const uh I'll just call it array is going to be equal to str.split. And we'll just split on the empty string, which is going to give us an array of the characters in the string. And then we're going to need that stack. So, let's say const stack in JavaScript. We just use arrays for stacks. Love that. And then what we want to do is iterate through our string or really we can just essentially iterate through the array. So let's say let's give this a better name. Say characters I guess. Okay. So let's I suppose we probably need just a let's just use a traditional for loop. It will probably be easier. So let's say let I equal zero. I is less than chars.length and I ++ for each character. What do we want to do? So if the character is a letter, we're doing nothing. If the character is an opening parenthesis, we are adding to the stack. And if it's a closing parenthesis, we are removing from the stack. So let's say if chars at iop if chars at i is a opening parenthesis. Yeah, that's right. All right. So if it is an opening parenthesis, we want to say stack.push. And we need the actual index. So we'll have our stack be just I >> really quick uh why did you put a triple equal sign and not a double equal sign? >> Yeah. So in JavaScript double equal sign is equality in terms of it's loose equality. So triple equals is going to be equality with the type and the value whereas double equals is equality of just the value. So for example we had like five double equals the string of five in JavaScript to land. That's true. But if you do triple equals, it's false. >> So, >> gotcha. Yeah. Okay, cool. >> Fun JavaScript things. All right. So, if we have an opening parenthesis, we'll just push onto our stack the index. else if we have a closing parenthesis. So if chars at i is a closing parenthesis, then what do we want to do in this case? If it is closing, we want to see do we have something in the stack? If we do, we want to remove that corresponding element from the stack. Say like yes, this was valid and part of our string. And if it's not, we just need to remove this closing parenthesis from our output. Let's say if uh stack.length is greater than zero, then we will do stack.pop. Otherwise, we need to actually remove this from the output. So, what does removing from the output actually mean? Um, I suppose we could just build up a a like result string. That might be the easiest way to do this rather than trying to edit the one we already have. Uh, yeah, I think that's probably going to be easiest to make sure we're not like concurrently modifying this array and doing something weird. >> So, let's say let's output equal an empty string. And here we'll do Yeah. So if if the if we had a closing parenthesis, we just don't do anything or we remove from the stack, but we're not adding to the string. Otherwise, we want to actually add this uh closing parenthesis into our output. So we can say output plus equals chars at i. And the same would be true with the opening parenthesis. So these we're going to actually add to our output >> and it's a little redundant to have this in multiple places but do it this way for now. And then otherwise so if we didn't have any parenthesis we have just a English character and those we just ignore. So we can say else we'll also add those to the output output plus equals chars at i as well. Mhm. >> Okay. After this loop is complete, what we should have is an output string where we have removed any dangling closing parenthesis essentially because those are the ones that we were here and we skipped adding them to the output essentially. Um but we still have the potential for dangling opening parenthesis. So what we need to say is essentially while the uh stack.length is greater than zero. So while we still have some of these dangling opening parentheses, we just want to go remove them. So >> we need we need to remove them at the index that they were here. But I suppose that index is different than the index in our output, right? >> All right. So actually what I want to do is let's get rid of this output thing. And instead of doing that, let's say uh whenever we remove so let's get rid of the output stuff. So this actually simplify the code a lot. Anyways, we don't need that. We don't need that. All right. So let's get rid of the output. And instead when we actually we need remove too much hold on hold on hold on let's put it back put it back we need the part. So essentially what I want to do is rather than keeping track of this output we're just going to update the chars array and when we remove something I'm just going to put an empty string there and then at the end we can just join the chars array back together and the empty string is going to be ignored. >> Okay. >> Does that make sense? >> Yeah. Yeah. >> Yeah. All right. So if we have an opening string or an opening uh parenthesis, we put it in. If we have a closing parenthesis, if there's a valid opening parenthesis, then we want to pop it from the stack and we are keeping it. Otherwise, oh this was actually backwards before. So otherwise we need to say chars at i. So this is when we had a closing parenthesis but we had nothing in the stack. So in this case I want to say chars at ii is going to be equal to an empty string. >> Does that make sense? And then down here we don't actually need this else anymore. >> So >> so that's effective removal from the string. >> Yeah. So this is yeah by making it an empty string in this case we're just removing it from >> it's effectively removing this without changing the length of the characters array. That way >> we when we do this while loop at the bottom those indices are still the correct indices. >> Okay, cool. >> All right. So now all we need to do is say while stack.length is greater than zero we can do chars at stack.pop which will be the next dangling opening parenthesis uh is going to be equal to an empty string as well. And then the last thing we need to do is join the characters back together as a string. So let's say return the characters join. And join takes in the like delimiter by default. It's a comma I believe. So let's just pass in an empty string so that it just joins them all together. Yeah, I think I think this should work. >> All right. You got a small little syntax issue at line 30. Oh, yes. >> Yeah, there we go. All right. Um, okay. Uh, I mean, this looks all right to me, but do you want to test it out with the sample input output that I pasted up here? >> Yeah, for sure. Let's come down below here and say remove Let's log it out, I guess. Say console.log remove extra PNS. Let's pass in this string and then I'll just comment these out manually. All right. Run this. Yeah, we get >> all right. >> Get that. Is that the same? So, we could also if you want do a couple edge cases. So, like if all we had was like >> All right, >> this guy. Cool. >> Okay. So, just remove that. >> Yeah. If we had >> I I'll I'll just paste a couple inputs outputs at the top for you to test out. You want to try that one? >> Yeah. Let me copy that. And this one we'd expect nothing, right? >> Yeah. So, we get nothing. You can't even really see it, but yeah. Um, >> okay. >> And >> and then let's try this one. >> Yeah. Copy that. Paste that guy. AB. Yeah, seems like that's it's working. >> Awesome. Well, it looks like you got uh these answers pretty well and it looks like it's pretty efficient. Do you have any further thoughts on this if you were to enhance it by any means or do any other things to it? >> Yeah, I mean I think for one we could probably clean up just the code in general a little bit. Not necessarily from a time complexity perspective. Uh but >> it is I think there's just like a lot of nesting happening and also just doing this in JavaScript. It's not really this isn't particularly idiomatic JavaScript using like traditional for loops. I think I I did that to avoid concurrency concurrently modifying the array when I initially was thinking about it and then we switched to this method of like editing the actual value to like an empty string and because of that this could be like a for each loop or uh something of that nature and I think it just like look a little bit cleaner. Uh yeah, I think that's kind of the main thing in terms of efficiency. I think it's probably at least I can't think of something better. >> Yeah. Uh there is one scenario I want to pace for you. So um sometimes certain inputs can have two different types of outputs. Now if we actually try this string that I just pasted. So it'll give one of the possible outputs of basically like this first possibility. However, this second output right here is also another valid uh possibility. If you had to do a little bit of deduction, what do you think is the implementation difference? Like just to be clear, you're still accurate in your Yeah. >> response, but what do you think is the difference? >> Yeah. I had not even considered the fact that there could be two solutions. So, I'm sort of going left to right here and saying, okay, let's say every opening needs a closing and if we find a uh closing that had no opening, let's remove that. Presumably, if you went right to left instead and the exact opposite implementation, you would get at times like sort of an opposite result if that makes sense. >> So you're pushing for the closed and popping for the open. >> Yeah. If you did, yeah, if you iterated right to right to left and then Yeah. essentially reverse the if checks to do the opposite thing. >> Cool. Well, that's about I had for you today. Do you have any questions for me? >> No, I appreciate you uh taking the time. >> Awesome. Cool. Well, I'll talk to you later then. Take care. Bye. >> You too. >> Well, that's about all I have in this video. I really hope that you guys enjoyed it. And if you did, make sure to hit the like button, subscribe if you haven't already, and if you're interested in my absolutely free tech newsletter, link for that will also be in the description. And if you're interested in what a software engineer does on a day-to-day basis, you might like this video right