Python Interview with a Google engineer

Watch someone solve the minimum cost to construct string problem in an interview with a Google engineer and see the feedback their interviewer left them. Explore this problem and others in our library of interview replays.

Interview Summary

Problem type

Minimum cost to construct string

Interview question

1) Use ABCD to construct a string. Suppose you can only use character A, B, C and D to form a string of length n. You are also given a 2-D integer array of cost[n][4] meaning for each position (0..n - 1), the cost to use each character (0..3 means A..D). cost[i][j] means the cost to put character j on position i. You cannot have 2 consecutive positions with the same character. Calculate the smallest cost to make a string of length n. 2) Finding interesting triplet Given an integer array arr, An interesting triplet is defined as 0 <= i < j < k < arr.size() such that arr[i] < arr[j] < arr[k] Please check whether arr has at least one interesting triplet.

Interview Feedback

Feedback about Massively Parallel Squirrel (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

Amazing. Support strong hire. Good communications. Good code style and algorithm designing. Good test cases/dry running.

Feedback about Rocket Wind (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

- The interviewer asked two interesting questions which I had not seen before - They provided an insightful answer to my question about mentorships at Google - They had a friendly attitude which made the interview process more enjoyable

Interview Transcript

Rocket Wind: Hello.

Massively Parallel Squirrel: Hi.

Rocket Wind: We'll have mock interview. So before doing that, could you briefly introduce, like, describe your expectation on the interview?

Massively Parallel Squirrel: Sure. So I'm going to apply for an L four position at Google, around two years of experience. Two and a half years of experience. And yeah, I just want to do this interview so I can better prepare myself when I have my Google interview. Cool.

Rocket Wind: Left that. Let me paste a question. Yeah, just paste one. Could you see whether it's clear enough to you?

Massively Parallel Squirrel: Sure. Okay, let me give it a read. For each position, the cost to use each character. Okay, got it. You cannot have two consecutive positions with the same character. Calculate the smallest cost to make a string of large N. I see. By the way, for this interview, are we just going to be doing it in text mode or do you want me to pick a programming language?

Rocket Wind: We use plain text for real Google interview. We don't use IDE as well.

Massively Parallel Squirrel: Okay, cool. Got it. So just to explain my understanding of it, like you mentioned, we need to create a string N. And these strings can only consist of like, four characters, right? ABCD. And then the cost is there in the cost array that you provided. And we want to minimize the total cost, right. So minimize total cost of string. And then one condition is, like, no consecutive no consecutive characters. So if we do allow for consecutive characters, it's pretty trivial problem because you could just take the lowest cost, right?

Rocket Wind: Correct.

Massively Parallel Squirrel: And then you form it. So the tricky thing is, now that we cannot have consecutive characters, what do we do? So let's see here. Correct. So let's say at position zero, I'm just going to try to work through an example to see what would happen. So let's say at position zero, we pick the one with the smallest cost, right? So say the smallest cost is two and that's equivalent to A. Okay? And then say at the next position. So let's look at what happens when we have these consecutive things. Right? So say in the next position, the smallest cost is also two and it's also A. But then we don't want to do this, so we can't pick the one with the smallest cost. So say we pick B instead, right? And then if we go to the next one let me see here if there's a pattern when if we pick the smallest one at a particular index, and then in the next index, we cannot pick that same character. So we'd have to pick like, say, the one with a bit of a larger cost. Right. But then the issue is that maybe if you picked a different character in the place before, your total cost now would be like minimized, right? If that makes sense.

Rocket Wind: Yes.

Massively Parallel Squirrel: You can't preemptively, at least as far as I see it now we can't greedily pick what's going to be the best at that position. You need to know future knowledge to be able to decide what to do. So one approach is to let's look at how the brute force approach would work. If you look at the brute force approach, what you would do is at each position, you pick a letter, say a each position, pick one of four letters, and then in the same thing in the next position, again, you pick one of the four. And then in the next one, you pick one of the four. You pick one of the four. Pick one of the four. And then you would have like so how many different combinations we would have, right? So we have four choices for the second one and then for the next one, again, we can't have any consecutive options, right? So for the next one, you would have three choices, and then for the one after that, for each of them, you would have another three choices and then another three choices and so on. And this would go up until so you have like four times three to the power N minus one possible combinations. And then you would compare the cost of each of them and then pick the one with the smallest cost. Let's see if there's some sort of memorization maybe that we can do. So, say, at a particular position. So we have like ABCD that we can choose. And then in the next one, let's say we have something like this, right? And then in the next one, again, you can pick like B, C, or D, and then you move on. And so if you see here, we see like a repeated structure because the branch you're going to make from B and C and D and all you're going to do a lot of the computations within the first three as well, right?

Rocket Wind: Right.

Massively Parallel Squirrel: So if we look at the memoized case of what would happen, again, at a particular index, what we want is at this particular position, what letter you're going to choose, right, so what letter for current position? And then you would be able to kind of compute let's see, at each position, you kind of compute all the different possibilities. Let me try to formulate this. Yeah. So at a particular index, you could pick what letter you want, right, and then you have X number of other indices to keep processing, right? Say at position zero, you pick ABC or D. And then at position one, again, you pick another letter, and then you have another N minus two remaining positions to fill. So what you would want to do is you can pick the so, like you pick letter for current index and then you want to add the cost of you would want to minimize the cost of so you pick a letter, right? And then you want to minimize cost of N minus one string. But actually you don't want to minimize the cost of an N minus one. You would want to minimize the cost of an N minus two string plus one of the letters that we can pick. Right, so say you pick a letter for the current index and say that letter is like A. Then what you would have to do is you would want to find the minimum of like B plus this and then C plus again like the cost of N minus two. And then D plus again like the minimized cost of N minus two. Right. You could do something like this and you could do this for all the different so whatever letters eligible. Yeah. So you pick a letter for the current index and then for all the other letters you pick one of them. Actually, let me see. No, I think we can make the formulation a bit neater. Yeah. So you basically want to find the minimum of every eligible letter plus the minimized cost of yeah. So probably when you want to minimize the cost of a string, you would just have to pass on what letter it can start with and then it can figure out what is the minimal cost for that. So you would need to know what letter you can start with and then minimize the cost of the rest of the string. Right. So you can say what is the minimum cost of a string with N minus two elements that start with a letter A, n minus three elements that start with a letter B, n minus four elements that start with the letter C, and so on. Right? Right, so if you do it that way, what you would end up having is like, you would have four different letters that you could start string with, and then you would want to calculate it for N and minus one and minus two and minus three and so on until N. Right. So you'd have basically four N different function combinations, which is going to be like start letter and length, basically. So these are like the number of unique function calls that you would be making, and in each function call you would be making another four function calls. Right. Another three function calls. So I think in total so the complexity would be like four times N, and then within each of these four N calls, you would be making like three calls. So it seems to me like it would be something like this. Perhaps if I write down this pseudocode a bit more clearly, I could have a more concrete estimate. But it does seem that if we do some memorization, we would be able to solve it in linear time.

Rocket Wind: Okay, sounds good to me. Yeah. Do you want to write code or write pseudocode? Whatever. Do you want to elaborate on your algorithm?

Massively Parallel Squirrel: Yeah, I think I'm just going to write like pseudocode, but it might look kind of like python because I'm used to python. And python looks pretty like pseudocode as well. Okay, yeah. I'm just going to write it in sort of a mix of python and pseudocode and I'll try to make it as understandable as possible. So let's just call the function like minimize cost, right? And we are going to have some sort of this cost array that you mentioned and then some length n that we're going to give to of the length of the string that we want to create, right? And again, like we mentioned before, so at each position you basically want to pick a letter that you want to start with and then you want to minimize the cost, right? So you'd probably have some sort of minimum cost here and then this could be set to positive infinity or something. And then we could keep updating it. And then we want to try for each of the letters, right? So for example, you could have for letter in ABCD, you would pick cost for that particular letter, right, at whatever index you're in now. So we need to have some way to figure out what index we're in now. And then at each iteration we'd have a different index, right? So say we have some sort of helper function and then this helper function would have your current index. And then what you would do is for each letter we can just use a range function, have like and so the cost of the current letter current letter cost is just going to be the cost array. And then we take whatever index we're in and then whatever letter we're in. Right. So we'll have this current letter cost and then we want to calculate the cost of the future iterations, right? So you would have for the future iteration, what you could do is you would want to iterate on the next index onwards and you would have to have some sort of starting letter as well. So let's say you calculate the cost for the next index onwards and you would probably want to specify the previous letter, if that makes sense. We have like previous letter and then current index. And then what you'd have to do here is like if I is not equal to previous letter, then you could iterate over that, right? And then you'd have this and then you would want to add the cost of whatever this previous letter. So in this case it's going to be I and then you're going to go to the next index. Does that make sense?

Rocket Wind: Is it x plus one. Sorry? I plus one.

Massively Parallel Squirrel: Yeah.

Rocket Wind: Okay.

Massively Parallel Squirrel: Yeah. So this is going to be I'm going to change I to letter. I feel like it's a bit more meaningful.

Rocket Wind: How to yeah, like how to return.

Massively Parallel Squirrel: Sure. Yeah. So basically like for first of all, like this line just so we get the cost of the current letter, then the helper should return the minimum cost from that index onwards. And then letter is like the previous letter, right? And then what we would want to do is this is not current letter cost, this is going to be like remaining cost. And then what we would want to do is we would want to minimize this cost, right? So you would do like over here, I think you would have your min cost. And then this would be infinity. And then you would do a minimization across this. So you minimize the min cost and the remaining cost. And after you've done that so yeah, you're going to do this for all the different letters, right? And then you can return the minimum cost that you have obtained so far, right? And then the terminating condition for this would just be like if the current index is already equivalent to N, right? So that means we're done. Otherwise you keep doing this. And how this would be called is you would probably start with so there's not going to be a previous letter, right? So you can do whatever as your previous letter. And then the current index is zero. So you could do something where you just minimize helper. And then we could give like an invalid previous letter. You could give like an invalid previous letter. And then the current index can be zero. And then you can just run this. You don't even need to minimize it. And the way that we would be memoizing things is we just need to memorize this call of letter and the current index plus one. So which means from that point onwards, in a way so you could just have some sort of we could code it out. So we could have some sort of memoization. And then we could check over here, like if memo so if like rev letter and current index in memo, then we can return memo of this. Okay. And then we would do the same thing here. At the end, you would assign memo of like rev letter. Current index is going to be equivalent to min cost.

Rocket Wind: Sure.

Massively Parallel Squirrel: And then you could return the memo.

Rocket Wind: Sure, sounds good to me. Can you run like dry run a test case?

Massively Parallel Squirrel: Sure. Yeah.

Rocket Wind: You probably don't need to run a very large case because it's a recursive. So it may not be very easy to render, but just like just a trial example.

Massively Parallel Squirrel: Okay, sure. Let's say like a four letter length, or let's do like three maybe for N. And then for the cost array, let's keep it simple. Let's say the cost is just like 1234 and it's going to be like the same for all the cases. So what's going to happen here is we are going to go inside, we're going to call helper negative one, and for index zero, right? And then we go in. We don't pass the terminating condition and we don't have anything in our memo. So we start looping, right? And yes, letter zero is eligible, right? So in that case, our cost for the first one is going to be like one, and then we're going to add helper, and then we're going to pass in letter zero and the next index, which is one, right? So maybe it'll be easier to have some sort of tree that we go in at the bottom, right? So now at helper zero and one, we go in again. And then we check if it's in the memo. No, it's not. It's determinated. No, it's not. And then we start looping again. And then zero is the previous letter. So we'll skip that one. And then we check letter one. And then we calculate the remaining cost for this, right? So the cost in this case is going to be two for letter one. And then we're going to start calling helper two with index two, right? And then we're going to go there. And now over here, we go back to our helper condition again, like not matt, not terminated, start looping. And then we can do letter zero because it's not the previous letter. Here is one, and then we can do letter zero because we haven't done it yet. And then we check the remaining cost. So for this one, it's going to be one plus. And then we're going to call helper for the current letter and then for the next index. So the next index is going to be three, right? And then we go back to helper call. This time again, nothing in the memo, but we hit the termination condition that the current index is equal to N, which is three, right? So we're just going to return zero, right? And so over here, actually, over here, we would probably we may not need to add the memo, I guess. So over here, what would happen is this would become one plus zero. So it will just be one, right? And then we would start looping through the different so then over here, our min cost is going to become one. Does that make sense? And then it's just going to loop over all the other different ones, right? Let's say here word helper one and then index two. And then we go one plus helper zero, we return zero. And then we're going to basically try helper one, comma three, helper two, comma three, sorry, helper two, comma three, helper three, comma three, and so on. And then that's just going to return zero every time. That's going to return zero every time. And then we would just end up having a min cost of let's see here. So yeah, that's going to return zero every time. When we call helper zero, comma three. Let me just write it down so I don't get lost here. So at index zero, then we call index one. Sorry, we're at index one, then we call it for index two, and then we call it for index three. And then we would do the same thing. So we would have like helper zero comma three, then we would have, so we would have two comma three, and we would do the same thing. Like we would have three comma three. So we would end up doing all and they're all going to return zero, right?

Rocket Wind: Correct.

Massively Parallel Squirrel: What we end up having is it's just going to be one for helper one and two, and then we're going to have another version where we're going to call helper two comma two. Right. And then for this one and then for two comma two we're going to do. And then the cost is going to be upper two comma two current index. Yeah, so the cost of the current letter in this case is going to be that's the previous letter and the cost of the current letter and so on. Sorry, 1 second. I think the previous letter current index thing is a bit hard to follow here at this position. We have like so I think if I mentioned the current letter in these calls it will just make things a bit clearer. So we have A equals to one and then, so the initial call is going to be yeah, so we pick letter A, right, and then we call this for the previous letter and so on. And then for the next call we're going to pick a different letter. So we pick the cost and that's going to be B, and then we make the next call, right, and then over here we're going to again pick like A, and then we're going to pick a few different ones. So we're going to pick C, and then we're going to pick B, right? So we're going to do all of this and then the minimum cost is going to be returned by A, essentially. And the minimum cost by A is going to be one, right? So Min is A is equal to one. And then what's going to happen is we're going to call it for different variations, right? So we finished calling it for when B is true. And then we would do it for the next letter which is eligible, which is going to be C. Then you're going to call helper with index two, comma two. So current letter is two and then the next index is going to be two. And now we do the same thing. So you're going to have this whole logic all over again and then the minimum here is going to be which is equivalent to one, and then you're going to have the same logic with D as well. D is four, and then you do the same thing with checking all the different letters and again the minimum is going to be A, which is going to be one, right, and we can't pick A because that was chosen in the previous index. So it's just PPD first and then at the end of this the minimum that we would be returning is going to be B and A because it's going to be two plus one, which is three, right? So Min is BA with cost three, and then we're going to do this again with a few different letters. So we're going to do B equals two, and then we're going to start calling helper one, comma one, right? And now over here, one, comma one, and then we can start doing different letters, right, so we can start with like A and that's going to be equal to one. And then we're going to end up calling the next index, right, so current letter is going to be one and then the next index is going to be two. Sorry, in this case, yeah, so we pick index zero, then we call helper one, comma one, and then we pick A, and then we say that the current letter is going to be zero. And then we move on to the next one, which is going to be index two. And then again over here, I think we still haven't encountered a memoise case yet, so let's see here. Yes, zero, comma two, and then over here we would start exploring the different conditions. Over here we can try B equals two plus we're going to do like the next helper call and that's going to have the current letter. And then the next index is going to be so the next index is going to be three. And then again we're going to terminate over here, right, so this is going to again return, this is going to return zero. Then you're going to end up with B AB, and then you're going to do the same thing with C, and then you're going to do the same thing with D. And each time you're just saying what's your current letter and what's the next index? Right? And over here we can start seeing some memorizations are going to come into play. I think in our function, we didn't memorize the last index, but I guess it doesn't matter too much. We could memorize in the previous call. So D equals four and then the same thing, right? I'm just going to just return the minimum directly. So the minimum here is going to be B. This is going to be the minimum and we're going to do this thing for, again, every other index except for B, right? So we're going to do it for C, we're going to do it for D as well. And what we're going to end up with is over here the cost is going to be one plus two, right? So it's like AB. And then over here the cost is going to be you pick C. So the cost for C is going to be three plus the next minimum, which is going to be A. So that's going to be four. And then for D it's going to be four. And then the next one is going to be A. So that's going to be five. Right? So this is like basically A plus B, and then C plus A. D plus a So the minimum here is going to be AB and then for B equals two. Yeah. So we do this and then the cost for this iteration specifically with B is going to be B plus A plus B. So that's going to have cost of like three plus two. So that's going to be five. And then we're going to do again the same thing with the next combination. So that's going to be we start with C, and I think we can probably see the pattern here. So if we start with C, the minimum is either going to be AB or BA. Right. So that's going to be a cost of three and then for C. So the cost is going to be like three plus three, which is going to be six. And then when you pick B, it's again the same thing you're going to pick like AB or BA, and it's going to be four plus three. Yeah. So that's going to be seven. And then if we look at all the minimums here, the minimum is going to end up being aba because that has cost of one plus two plus one. So this is going to be a cost of four and that's going to be like the lowest one out of all the combos.

Rocket Wind: Okay, sounds good to me. Yeah, I'm not sure whether probably I'll give you not very difficult one because we probably don't have much time left, but let's try another one probably.

Massively Parallel Squirrel: Sure. Yeah.

Rocket Wind: What about this one?

Massively Parallel Squirrel: Okay, let's see. Given an integer array such that I less than arr, j less than Arr, please check whether Arr. Okay, so an interesting triplet, if I'm reading here, is just you basically want to find a subsequence of three elements and they should be in increasing order, right? So for example, here you have two negative one, negative five, three. So you've picked zero. And then the next bigger one is going to be negative five. And then the next bigger one is going to be three. And then, so you found an interesting triplet, otherwise you return false.

Rocket Wind: Correct.

Massively Parallel Squirrel: So say we start at a particular index. Say we start at index zero and then we have a specific value. What we can do is we can move to the right. We move to the right. Check if the current element is bigger than index zero. Right. If it is bigger, then we have two elements of a potential triplet and we can keep going. If it is smaller, we now change the smaller element to the first element of the triplet. Right. And then again we keep going.

Rocket Wind: Let's formalize and if you have a pair, how do you continue?

Massively Parallel Squirrel: Sure, yeah. So if we have something like this already and then we are traveling obviously, if we see an element bigger than the last element, then we found the triplet, we're done. Right? So the interesting case here is like, what happens if you find an element which is one possibility is you find an element which is in between this, right? And if you find something like this, replace high with x. Okay, keep searching. And if you end up with x less than low, less than high, if you end up with something like this, let's see what we could do here. So if we end up with like, x less than low, less than high, you could like, let's see, this could be like the start of a new subsequence potentially. Or not. So I think this is reminding me of the longest increasing subsequence problem, sort of. So I think what we could do is we can replace low with x and then again, so what's going to happen is if we end up replacing low with x, and then we just keep going, and then we see another element greater than high, okay, we found a triplet and we're all good. Right, but replacing it with yeah, replacing it gives us the possibility of eventually finding actually no. Yeah. If we replace low with x and then we see another element which is greater than high. No, yeah, it's fine. Okay. Yeah. So we replace low with x to give us the possibility that we might want to start a new subsequence. Right? So what could happen is, like, you replace low with x and then you end up with like, x and high, and then say you eventually find a new element, y, which is between x and high, right, and then you can now replace high with Y, and then you can form a new subsequence. So in a way, like, replacing low with x lets us store multiple possible subsequences while just maintaining one variable.

Rocket Wind: Why you replace low with x, right? If you have another value that is larger than high, why can you think it's a triplet?

Massively Parallel Squirrel: It'll still be a triplet because at some point low existed, right. Even though it's not in our array, we know logically that there was an element before high for high to have been in our pair, right? There must have been some element somewhere. We don't record it, but that means that the next element greater than high will still be a valid triplet. But the variable that we are maintaining is not a valid triplet. But we're returning a boolean.

Rocket Wind: Sure.

Massively Parallel Squirrel: Okay.

Rocket Wind: Sounds good to me. Can you write the code? I think it's very simple to write this code.

Massively Parallel Squirrel: Sure. Yeah. So the code here is just going to be like, has triplet, and then we're going to have some sort of array here and we just need to maintain two variables. So this is going to be like low and high, and then we're just going to iterate through our array, right, so. For number array. And then you're just going to see like so if low is none, then low is going to be equal to this element, right? And then if high is none or NUM greater than low, then you can replace high with this current number and.

Rocket Wind: Then that may not be true.

Massively Parallel Squirrel: Sorry, high is none. I think this one is fine, right?

Rocket Wind: What if NUM is even larger than high?

Massively Parallel Squirrel: What if NUM is even larger than high?

Rocket Wind: You want to say smaller high, right, I see.

Massively Parallel Squirrel: Yeah, good point. Yeah. So if high is none, or basically we want to say that if high is none, then we can definitely put it down there, right? Or if it's between low and high. So for example, if it's like this, you would probably want to replace it, right?

Rocket Wind: Right.

Massively Parallel Squirrel: Otherwise if it's greater than high, then we found a pair, right? So that's one of the conditions. So like if NUM is greater than high, then we would return true, right. And the condition where we want to replace X with low, replace low with X that we mentioned before, we also have to take that into account. Let's say NUM is less than low. We would replace low with NUM. Then high is none. Or this is this high would always be valid over here. Because if high is done, the previous condition would have been triggered and then if NUM is greater than high, we return true. And then over here, we can just return false.

Rocket Wind: I suggest you to check for the equal, right? For example, if NUM is equal to low and then high is none at that time, for example, if you have like eleven, for example, you do you want to set a high to one or not? In your logic, you will set high to one because high is none at that time for the second one.

Massively Parallel Squirrel: I see what you're saying. Yeah. We would probably need to change the order in which we do these things. So for example, the first thing we could check could be like if high and NUM greater than high, we would just return true.

Rocket Wind: Sure.

Massively Parallel Squirrel: And then the next thing we want to check is next thing we would want to check is if this condition right, so if low and high and this or another possibility is if for low and high is low and NUM is greater than low and high is none. Right. So those are like two conditions probably. There could be a way to simplify this boolean logic. So if this condition or like, we have a low and then we have a number bigger than low and high is not populated, we could set high to this number, right? And then finally the next one is just going to be a number, which is going to be like, either it's going to be, like, equivalent to low. So we can probably just do something like, let's see so if it's this and then if it's in between and then if it's lower than or equal to low, you could probably just convert low to here.

Rocket Wind: Okay, sorry. Let me copy that code.

Massively Parallel Squirrel: Sure.

Rocket Wind: I'm not sure whether there's a way to copy sir, can you control Z? Let me copy that code. You can delete it now. I'll copy it at the end. I think there's a very simple fix. I think what in my mind is something like this. You don't need this. It I think it's quite simple, something like that. If you just add equal to the condition, because for the first condition, like low equals to none or NUM is smaller than or equal to low, you set low to NUM and after that, low is not none and basically number is larger than low. So you only need to compare the number with high. Similar high is none or like high is larger than or equal to NUM. You set it otherwise both low and high are not none and then NUM must be larger than high because you check the equality before.

Massively Parallel Squirrel: Got it, yeah, I see what you mean here. It's already implied that low is defined. Right. So you're already checking for this condition within here, right?

Rocket Wind: Yeah, I think what you mentioned is most of optimizer solution. Basically I understand the algorithm, I just want try to know whether you understand it as well. Like whether the triplet is always low, high plus another element. Basically there are two different subsequences, they're not the same one.

Massively Parallel Squirrel: Yeah. Are you talking about the replacement of low or what do you mean by two different subsequences here?

Rocket Wind: No, basically low is subsequent with lens one. Basically.

Massively Parallel Squirrel: Yeah.

Rocket Wind: Basically the last element of subsequence of lines two. Basically.

Massively Parallel Squirrel: Yeah. And then you're finding the next element which is greater than high.

Rocket Wind: Yeah. They may not be even the same subsequence. That's a key point. The reason I ask you is trying to understand whether you know this or not.

Massively Parallel Squirrel: Yeah, I think that was the point of replacing the X, right? Whenever you replace low, you're basically like you've created a new potential subsequence that is going to be evaluated.

Rocket Wind: Right, go ahead.

Massively Parallel Squirrel: Yeah, I just wanted to say that when we have never replaced low right? That's just like we have always had one subsequence and then when we do that low replacement, we have now created a new potential subsequence that we can form, right? Yes, pretty much. Cool.

Rocket Wind: Yeah. I think that's all for today. I don't have other comments because for the second question, you already give me the most optimized solution. It's derived from the longest increasing subsequence unlockin DP solution because we only have two, so we don't need to do the binary search, but it's kind of binary search as well. Do the brute force on the last element of each subsequence.

Massively Parallel Squirrel: Yeah, that's what I immediately thought of too, because over there, you kind of replace the elements, even though you kind of destroy the subsequence. Right. But it lets you still solve for the boolean condition.

Rocket Wind: Right. I asked this question to some other candidates before and who gave me a similar solution and why. I asked why you replaced the low and the candidate got confused because he thought the low high with another element is a sequence. That's the reason. I ask you the same question again, because we need to be clear that they are not the same thing. Basically they are not the same tripolate.

Massively Parallel Squirrel: Yeah. If we had to return the subsequence itself, I think we would probably return the actual subsequence. Like if the problem were to do that, I think we would probably have to store all the potential ones. The memory constraint will definitely increase, though the complexity should be the same.

Rocket Wind: Correct. Like, I don't have other comments and you are perfectly good. Do you have any question to ask me?

Massively Parallel Squirrel: Sure. Are you working in Google currently?

Rocket Wind: Yes.

Massively Parallel Squirrel: About your experience, what do you think of the company, things like that?

Rocket Wind: Yeah, I think I work as infrastructure. Google is very how to say that? Fast changing question, faster changing company. We always have new things to do and it's more like a big family. So if you have any questions, technical questions, you can ask not only your team member, but also some other team members in other team. And basically the main challenge is like we have lots of tools that are doing similar things, so you probably need to find the best thing, find the best tool you need. Right. And sometimes the documentations are not very detailed and they may just be out of dated. That's very common. So when you want to do something and you are trying to find a tool, it's very difficult to find the correct tool if you don't ask anybody else. So typically we ask, we publish a question and lots of people will help you. And they are very friendly to typically when I have a question, typically I can solve that in just one or two days and you can even schedule meetings with other team members. But basically we have a spirit to be tough on the problem, right. To be friendly on the customers and the team members. I feel quite welcome in Google, no matter I joined like seven years ago or even now. So basically Google is really like a big family. Yeah, that's my experience and my feelings for Google.

Massively Parallel Squirrel: Got it. I guess I'm planning to apply for L Four at that level. Is there some kind of official mentor relationship going on or are you kind of just expected to make friends within the team and then eventually get your own unofficial mentors to help guide you through it?

Rocket Wind: I'm not sure whether it's official, but conventionally for L Four, no matter what level, no matter what level, when you join the team, right. You probably will have a mentor. That's my experience. I joined Google as R Four seven years ago, and then when I joined there's another L Five worked as my mentor. But I'm not sure whether it's kind of like in the official employee website, whether the guy is marked as a mentor. I don't think that's official. But basically that's the convention. When you join the team, there should be a more experienced member who will take the mentorship. Something like that. I don't think it's official.

Massively Parallel Squirrel: Okay, cool. Yeah. I guess the point is just to have someone to guide you through it, right?

Rocket Wind: Yeah, that's quite normal. Right. And also if you want to increase or make more impact right. So you can ask probably not immediately, but after one year or so, you can ask to have some internship. Right. It's not mentorship, but it's a kind of internship. You can have some new grad working for you or working with you. Right. And also we have some other programs like I cannot remember the exactly program name, but before, we call that the Technical Resident, which is another kind of internship. But they are just new Googler. Yeah. Before they are not even just a new Googler. There might be some candidates that didn't perform as well during the interview, but we didn't give them no hire. We gave them another opportunity to study or to work in different teams. And for each team, the period I think is probably half a year or something like that. And during the work, it's kind of internship. And then the mentor, we call that the host. It's not the mentor, but it's same as mentor. The host needs to give the guy a project to do, and we need to write feedback. Just like interview, probably not interview. Just like our performance review. We need to review the performance.

Massively Parallel Squirrel: How.

Rocket Wind: To say that on the technical resident. And then we decide I think it's like a bilateral selection. Basically, the tech resident also decide whether to stay at the team or not. And our team also decide whether we want this technical resident or not. And if not, he has another opportunity to work on another team for another six months, something like that. So basically, if we want to enlarge your impact, there are lots of programs for Air Four, even for Air Four. And some Air Five also has the similar opportunities. So basically, you can have intern and you can officially give some entry level engineers. Otherwise, basically, typically, you don't need some official concept or official title. When we do the performance review, we really consider what you did. Right. It doesn't matter whether you have the title or not, basically.

Massively Parallel Squirrel: Yeah, I see. So you were saying that as an L Four, you have an opportunity to mentor and also be mentored by more.

Rocket Wind: Right. But I don't mean as long as you join the team, you can lead others. I think you probably need at least one year. For example, in my team, right? I was L four before, and then at that time, I had opportunity to lead R three. It's not like the manager. So R three needs to report to me. It's not something like that. It's unofficial. Like, we have a project, right? We need to do it together. And I'm more experienced than the L. Three, so I can split the project into some subtasks. And then for each L three, for example, I can have two L. Three, and I decide which task to give whom. Something like that, you can lead a small project. And for L Five, you can even lead larger projects. And for L Six, you are the manager.

Massively Parallel Squirrel: Okay. Yeah, that makes sense. I know we're like a couple of minutes over time already, so yeah, I think that's all good. Thanks so much.

Rocket Wind: No problem. No problem. If you have no questions, we can stop here.

Massively Parallel Squirrel: Sure. Yeah, I think it's all good. It was a great interview. Thanks.

Rocket Wind: Sure. Bye.