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)Given a permutation of from 1 to n (an array), the only way you have to change it is to select any integer and put it into the end of the list. Return the minimal number of operations to sort the array.

Interview Feedback

Feedback about Secret Lobster (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

Support leaning strong hire. Good points: 1. Figure out the DP solution super fast (~20 min). Also, figure out the 2nd question (though no time to write code) correctly. 2. Have the good understanding of time & space complexities. 3. Good code style, bug-free, even consider about the optimizations on space (i.e reuse the input array). 4. Communication is good (ask clarifications) 5. Dry run the code Suggestions: 1. Recommend the "common pattern" to explain DP: i.e (a) what is the state? (b) How to do the induction ? (base + real induction) (c) what to return This framework (or similar one) is very useful to express your idea to the interviewer, and also it's very simple to change the root logic to the real code.

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)?

3/4

last hint was a bit confusing but I think you did a solid enough job of clarifying it because I was able to get to the correction solution by the end Also you had the best sound quality of anyone i interviewed with so far which was very nice

Interview Transcript

Rocket Wind: Hello.

Secret Lobster: Hi.

Rocket Wind: Hi we will have mock Google mock interview like before doing that do you mind briefly describe your expectation.

Secret Lobster: What do you mean?

Rocket Wind: What do you expect for this interview?

Secret Lobster: Sorry could you say that again.

Rocket Wind: Oh sorry. What do you expect on this interview? Like, expect to see more questions and expect to get feedback? So, like, what's your target value? Basically? What do you expect on this interview?

Secret Lobster: Ah, I guess Yeah. I mean, I'm applying for new grads position. So I'm applying for new graduates that's what I'm being interviewed for.

Rocket Wind: Okay. Okay, basically L3, right?

Secret Lobster: Yes, yes.

Rocket Wind: Okay. Let me give you a question here. I can work through the question like briefly walk through the question for you, like, we are trying to construct a string using only four kinds of characters, which are ABC and the D, and the strings, the length will be n, we are also given a two dimensional array, which is called so two dimensions, like N and four. And it means that let's take the 10s row as the example you line ten, we have the array of two multiply by three. And it means that if we pick the zeros position, let's make positions start from zero, if we put ABC and D on the zero position of the screen, we will have the costs of 234 and five separately. And if we want to put ABCD on the first subordination for the summary screen, we'll have the cost of 734 and one separately, so the cost is basically per position per character. And your goal is to construct a string of length N without using two neighbours with the same character. And that's the only restriction you have. And you'll want to find the minimum total cost to construct that string. In our case, we need to construct the string of length two and what we can construct is the string a and b. And for the zeros position, we selected a we have the cost of two given by the character rate and the for the first position, we have the character d and we have the cost of one given from the char rate. So in total, we have the cost of equal to two plus one which is three, so we'll return three.

Secret Lobster: Okay, so let me see if I'm understanding this, right. So basically, we're given an array cost, right? And the cost represents the cost of any letter ABCD. So but there are four letters to put it into that position. Right? So like, if I was to do for example, B, A, that would be eleven.

Rocket Wind: For, not not 11 right b is three

Secret Lobster: Yeah basic math. Okay, so that'd be 10. And I can't use the same letter twice in a row. It's like I can't have a, a, a

Rocket Wind: Right you cannot use the same letter for neighbours, but you can for example, ABA is okay.

Secret Lobster: There's okay. Right. Okay. Right. So I can't use a greedy solution, then because each answer I'm taking is going to depend on the last one. So let me just think this through for a second. Do you mind if I change this off of plaintext.

Rocket Wind: You can, like sure.

Secret Lobster: Oh okay. Okay, so how do I think about this. I feel like I can represent this as set of state so why is that oh it'll auto complete, right, okay. ABCD to form, so let me try a more meaningful example here. Because this doesn't really account for that. I mean, like it because in a case like this, I really can just get greedy because there is no the answer doesn't require me to use two things. I can just check the smallest one each time. But obviously, that's not gonna be the case. Sometimes we'll need a case where I'd say one or Okay, yeah. And then three, so in this case, if I was to try greedy. I would like to first Oh, I have to get back, I have to change this one first. Yeah. Okay. So If I had two here, that I have to I wouldn't be able to select one here and that would be that oh my god, no, I have to change another number here

Rocket Wind: doesn't matter, like just change it as you want

Secret Lobster: I was gunna say here, I'll just say some some numbers. Basically, if these numbers are the same, this one is smaller and it makes more sense to pick this one here. This one is some infinitely large number I guess, then we can't just pick the smallest in each thing. So basically, the amount we can pick from is at each point is dependent on the previous one that we've built.

Rocket Wind: Right

Secret Lobster: So in that case, I can go ahead and attempt to define and I'm going to, so I want to try to accomplish but a fairly small set of states here first. So for each, oh okay, for each n what, need to get the smallest cost n. Okay for each numbers, let's say we have just we're starting from here for the basic case where it's just n as one. Always take the smallest, then after that I'll just say. Cost of one with minimum of cost one, okay. Now what is cost to relative to this? Well, let's say so no cost for purchase. Let's just go back and define this as one, two, 345. Here is not a 2, that is a 3. 1234. So for one, we would pick two here. But then we go on to the second one. One is the smallest here. So we have to do is we look at what the value would be. If we take this was in the smallest be would be two so then we would have four. But if we take one here, then the next smallest here is three, also four. Actually, this is not a great example.

Rocket Wind: Sure.

Secret Lobster: Oh my god. Four there. Now it's worse. So now if we

Rocket Wind: let me give you an example to see well

Secret Lobster: yeah, my brain. I'm like, the brain farting on the numbers. Yeah. Yeah, I should've used your numbers. Yeah, okay. Right. Right, right. Yeah, so yeah, in this case, I pick one for the case where it's one. But that would mean here, I'd have to pick 100, which would suck. Because that's a that's a big number. So instead, I would have to pick one here. And then pick the second largest here. So it'd be two, three. So what is the relationship? I'm basically trying to see if I can do this. Like dynamically versus just like backtracking? I'm trying to think here, what would inhibit you from doing this dynamically? Let's see. One, two. And these are not ordered anyway. Right?

Rocket Wind: Right. Okay. Basically, they're arbitrary integers.

Secret Lobster: Okay, so I feel like I might actually I'm going to start by doing this. Right, right. Explain backtracking and then if it doesn't work, I can prove that it doesn't work then I can do something dynamic. Yeah, so first, pick smallest in array so second one that we do that. Okay, no, no, I'm thinking about this, this sort of work, but it would take I think it'd be all events it would be it would be time complexity will be pretty terrible. Because if I just go and check through each thing Eventually, I will find the smallest one. But there's definitely a better way to do this. I just need to think about what that is.

Rocket Wind: It's okay now, like if we want to have the brute force way, like implementation first, and optimize it later.

Secret Lobster: Okay. All right. I guess I'll go ahead and do that. I'll write it out in pseudocode though.

Rocket Wind: Sure.

Secret Lobster: Isn't that one? Back up okay. Okay. So just like looking at this, this is definitely, there's definitely a relationship here between each of the states.

Rocket Wind: Sorry, what's your question?

Secret Lobster: Not a question, I'm just like, there's definitely a relationship between the states here. So I will be able to do this in O(N) time, I think. Okay. How do I go about doing that is the question. So we know that for our 0 case, for our base case, where n is one. The costs will always be a minimum of one. N of N is 0, the cost is 0, I'm assuming is one of the constraints the problem is that n has to be one or greater. But for sake of like a relationship this makes sense because that would mean that as one is related to n of two, n of zero. Okay. Now how do I get from that to N? Is N two relative to N? Is there a limit to there's always ABCD? Right? So it's always four characters. Yeah.

Rocket Wind: Right.

Secret Lobster: So cost is always maxed out at four.

Rocket Wind: Sorry, cost is what?

Secret Lobster: The size of like an Array is always maxed out at four.

Rocket Wind: Right. So the second dimension is always four.

Secret Lobster: Okay. Okay. Okay. So that makes this feasible, because if it was much, much larger, valid, becomes way, way more complicated. Because in that case, what I can do is for each number, let's say I have some function. Cost, right? And cost of n gives me the costs of building the minimum at n. What then is cost of that? Well, there are four potential options I can pick from at n right. I can pick from A, B, C, and D. And, well, there's three really because it's dependent on what I pick last time. So unless n is one, there are three options I can pick from. So that means that cost is n minus one, minus one. We go back in the cost function. I feel like I'm trying to figure out a way to put this into words that works because I think I think I've got a handle on it here. It's just a matter of say. Always so hard to explain.For each element in our array, we get smallest of the previous three. X by, XYZ. So on so forth, I'm just going to use the same letters. This is an actual code, okay? The cast array like this. So for our cost function cost of n, right, if n is one, then the cost is going to be the smallest of whatever values this is. If n is two, then we have to go through. And for each of these we have to check what is the smallest for WXYZ what is the smallest for x at this point what is the smallest cost for X what is smallest cost for y was the smallest cost for Z. So, the cost here is w plus the minimum cost of cost minus again I'm just going to use the same variables. It's ugly, but it's code and then x, y, z. W, y, z, and so on. So forth. Okay. So, okay, I think that makes sense. So, let me put this into like pseudocode. So you have an array, represents the minimum cost, selecting that element at that point. What just happened, keybindings? Oh, I accidentally tapped into settings okay. Selecting the element at that point. We assign the minimum cost, so for cost one, that array would be cost one. For two I'd be each elements plus the minimum previous one excluding the one in the same condition then our answer is at the end is the smallest value in our final array. Okay. Yeah.

Rocket Wind: I mean, this makes sense.

Secret Lobster: Okay. Yeah. And I think that would be because it's constant at four it would be a little bad. But because it's a constant number, I hate that. But it's O(n) then. Because we can treat each element as just four elements. And the space complexity is also O(n) because we're just copying the amount that we're given in the input.

Rocket Wind: Cool.

Secret Lobster: Can I do this in place?

Rocket Wind: Sure.

Secret Lobster: I feel like I could, I'm not going to that sounds like it might draw memory issues, but I could also because the cost array will be the same size as some like bottom up dynamic programming solution. I can write that over so do you mind if I put some code on page if that makes sense what I said so far.

Rocket Wind: I don't mind do whatever you want.

Secret Lobster: All right. So let's say, def cost, probably not a great name, because we're calling the array cost too, okay yeah, cost at n. CostATN, cost is always the same length the length of cost is always n right?

Rocket Wind: Right.

Secret Lobster: I'm actually just gonna, I'm gonna do it in place that actually makes a lot more sense okay. So for i in range, four so I can just do range four yeah. Cost of I, j plus equals. How do I do this, I have to make that, I have to slice the array here. So the previous one, and then it is J. I always I always struggle when I'm supposed to remove one element, I think it's j and then plus cost by minus one. Okay. Plus one that looks right. Yeah. Okay. That should skip the one. N cost minus one, min of cost minus one, right. Okay.

Rocket Wind: Okay, this is very cool. Could you try run a test case? I think you are ready?

Secret Lobster: Yeah.

Rocket Wind: Yeah. I probably sorry. Probably you can just write like a main function. And like put the test case in so that we can just see an output directly.

Secret Lobster: Oh does it let me do that? How do I do that I guess. I don't actually know how this like, environment works at all. Like, can I just type this in here and it'll work?

Rocket Wind: I'm not sure about these environments as well. Yeah.

Secret Lobster: Okay. Yeah, it looks like it is up here. It looks like this is fine up here.

Rocket Wind: Yeah, let's try that.

Secret Lobster: Okay. And then n here would be three. What's it complaining about? Oh that's why, syntax. Right. Okay.

Rocket Wind: Right this is a list yeah.

Secret Lobster: If I changed it, just use the keys it'd probably still work it'd just be ugly.

Rocket Wind: Yeah, let's print the output.

Secret Lobster: Right, right. I have also get rid of everything up here first.

Rocket Wind: Can you print the output otherwise we cannot run it.

Secret Lobster: Yeah yeah.

Rocket Wind: Well, there's the hard work. Before it has that word. Oh is seven the output or not? This seven is our output, right?

Secret Lobster: Yeah.

Rocket Wind: Oh, you'll have another you'll have another row. Oh, it's not the same as above why? Why seven instead of six? I think it's six. Right? Why Seven?

Secret Lobster: Wait let's see, so lets see what's going on here, two. Let's run it by hand first. Two, this would be five, four, five.

Rocket Wind: Oh it's seven okay sweet. is 443, 223. I think.

Secret Lobster: Here? Yeah, it's kind of AB, whatever. Lots of character. Yeah, it's AB something. So it's, yeah, I think seven is correct.

Rocket Wind: Okay. Okay.

Secret Lobster: Okay. Cool. Like, let me give you another one. Since you solved this one super fast.

Rocket Wind: Okay. That's actually very, I have been terrible at dynamic programming. So I spent about a week doing literally nothing except dynamic programming.

Secret Lobster: Yeah, dynamic environment is very popular in Google interview.

Rocket Wind: Yeah that's what I heard.

Secret Lobster: Do you mind I put it here? Or put it in plain text.

Rocket Wind: Either here is totally fine.

Secret Lobster: Okay. Let me put in here. I can briefly go through the question for you. So in this question, we are given a list, a list of interger list which is also array. And the list contains numbers of permutations one to n. It means for each character for each numbers from one to N for integers from one to N. It all queues once and exactly once and you'll have a magic the only operation you can do is using that magic to put each number to the end that is to move each number to the end arbitrary number to the end. So you don't care about like how you achieve that. Suppose you have this magic. For example, in our example, like in line, 97. What we do is like we move three to the end for the first time, and for the second time we move four to the end. And for the third step we moved the five to the end and our goal is to sort this list. Which means we want to make it like as 1234 until the end, and you are trying to return the minimum number of the magic. Yeah, the magic or the operations you need to use to sort the array.

Rocket Wind: Okay, so it's basically like a very specific sorting algorithm.

Secret Lobster: Right. But the operation is not like kind of

Rocket Wind: Right it's not just a store. It's one single operation,

Secret Lobster: Right. And it's not a simple operation.

Rocket Wind: Right? So what is that operation? So I see three. So why is it that we're moving three first here, select any integer and put it to the end of the list? And we're trying to Oh, the minimum number to do that. So you can select

Secret Lobster: Right. You want to use the minimum number of operations. Otherwise, it's very trivial. You got to move everything to the end.

Rocket Wind: Right. Right. Yeah. Okay, so it's about yeah it's about selecting which to move to the end and so then minus operations. Right. Okay. So, okay, so in that case, the last one has to move to the end, and every every case is the largest number. That will always have to be the case. Because even if the largest is starting at the end, it still has to be shifted over.

Secret Lobster: Right? So everything behind the integer will be, like move left, for one position.

Rocket Wind: Right, okay. So then starting from the right here, so I don't think it really matters too much what this information is. String on the right, let's look integers here, look at this first case, 5, 1, 4, 3, 2 All right. We see two at the end, so we also also need it doesn't we can't move the one at the end already. Because that's it's there. So that means I think we have to pick the number that is like sequential so the number that's currently at the end probably I'm thinking that's my initial plan. But I think I might also have another way of looking at this because in that case, because two we're always having to build around this two or we can't sort the list. Two is the only number we can't move. Whatever comes after two or three, so let's see, five one four three. Got the same thing it would give us 51234. That is yeah I guess that's the same thing here. So what about this case? Okay, that's not the case here. So why isn't that the case here? This is a case where five is at the end. So there is no sequential integer here that moves that forward. State that I can achieve is dependent on the previous states.

Secret Lobster: I'll let you think about like five minutes and then like, I'll give you some hints if you cannot figure it out.

Rocket Wind: Okay, okay. So the question is, you can pick you start from the right. I think the farthest left that's out of place? The farthest right. As a matter of putting them in the right position, because the two the two things that we know for sure, at any given time, all the numbers always start from one right?

Secret Lobster: Right. It's a permutation from one to N.

Rocket Wind: Right? Okay. So we always know, what do we always know? Always know that one must be left most numbers and n must be the right most. So those two are my conditions here? That's what I am striving for. Ultimately, I mean, obviously everything else sort of, but those are the two things that I can like know right off the bat.

Secret Lobster: Right?

Rocket Wind: So how do I go ahead and place that? So after, okay, so I see here. So in this situation, because one isn't left most but like the main difference between these two, because after after, we move one here these two follow the same pattern again, where I start, I take the three, I put it there.So let's see five has to come at the end. Just the problem is here. So the last number I move has to be five. But I also need one to be to the left of n to the right of N before I move it. So need to put the array in form such that n one dot i'm gunna say I is the final append position where one two i is sorted. Okay. But I guess yeah, the i would actually just do you know what it is? It's n minus one.

Secret Lobster: Five.

Rocket Wind: Right. Okay. So how do we achieve this state then? So I think we always have to start with the numbers that are between five and one if they exist. Let's see. So in this case, let's see if I. I guess if we look at this, what's it called? Like, the cyclic array then five is, two is technically between them. The only thing we need to do is. I suppose it's not always true. Now, this is not always true, because I can also have a final case like this. Where everything is sorted.

Secret Lobster: Right. I don't think the like the right order matters here because they are not consecutive anyway.

Rocket Wind: Right? Yeah. So the one the only thing that matters then is that one is my left most number at the end. In that case

Secret Lobster: The positions may not be very, it may not be a very good metric, right? It's not stable, right? Because if you move a number, as you mentioned, all the numbers behind that will be like shift the left so all the positions will be changed by one if we move a number.

Rocket Wind: Right, right.

Secret Lobster: Okay, do you mind. If I give you some hints, or

Rocket Wind: Yes, go for it.

Secret Lobster: Okay. So first, let me ask you several questions. So the question are working as hints. I'm write on line like 116. For instance, like, it's a very simple question, like, do you think. Do you think we need to move number one in any cases?

Rocket Wind: No, we should never need to move one.

Secret Lobster: We should never move number one, because if you move number one, you need to move all the numbers, right? Basically.

Rocket Wind: Right so the goal is always to put one on the left.

Secret Lobster: And second question is, like, it's also very simple, how many times at most do you think we need to move the same number. Do you think we need to move the same number more than once or?

Rocket Wind: We shouldn't have to, we shouldn't have to if we select optimally.

Secret Lobster: Right? Because the reason is that if you want, if you have to move the same number twice. You can just skip the first move, because like the second move will always move the number to the end. So no matter where the number is, so the first move is no use

Rocket Wind: You can also move some numbers zero times right so the max we have to move zero just one time.

Secret Lobster: Right. I mean, at most the once, it's zero or once. And the third question is the most important one. If we like, we already have the two conclusions before. And in some times if you need to move the number x, what do you think about the numbers that are larger than x.

Rocket Wind: Then they're also going to have to be moved,

Secret Lobster: Right. Because x is like, you cannot solve them right? If you move x, you need to move all of them.

Rocket Wind: Right, right.

Secret Lobster: All the numbers greater than or equal to x must be moved. So easy to understand. Like, if we have the three conclusions, you will find that the optimised moving strategy is something like you can keep like numbers from one to x minus one. Keep them and from

Rocket Wind: Right, right. We have to move everything to the left of x first. Yeah.

Secret Lobster: Right and your goal is trying to find the largest x the larger the X is, the smaller the last numbers you need to move. In the other direction, you are trying to find the largest X meaning the largest numbers, you can move you can keep right. So how many numbers who can keep starting from one?

Rocket Wind: So figuring out sequentially Oh, okay. So like, wherever one is sequential numbers, those don't have to be moved. So for example, my 31254. This is instead our left condition.

Secret Lobster: When you say it's sequential like that, like they are x and x plus 1 and something like that. But the position doesn't like need to be consecutive, right? For example one

Rocket Wind: Oh yeah, that's true.

Secret Lobster: What about like, six or 2435? What about this one? In line 130.

Rocket Wind: Right I have to move here or by sixth?

Secret Lobster: Right. Right. That means you can keep one two and three, right?

Rocket Wind: Right, right.

Secret Lobster: Do you find a pattern?

Rocket Wind: What?

Secret Lobster: Do you find the pattern the criteria to keep the number or to find the x?

Rocket Wind: I think so. I think I pick the smallest number that's out of order. Or the yeah, the smallest number that's out of order.

Secret Lobster: Okay how can you do that.

Rocket Wind: So go through the numbers. It's basically I'm trying to keep the sub sequences in order. So I go through and I check whatever the starting from one obviously this one can never be moved. So we start from one I guess you don't need to start from one, we can just skip one. Because whatever is behind one needs to move no matter what. Yeah, I guess we have to start with the numbers before one so like if I move one there then how do I do this, then I'll just change to, well in that case I'll just put two there first. Then three. So I think I start I think like how it is, I would start with numbers that appear before one and I take the smallest number that appears before one and I move it on. Yes, okay. first get smallest numbers appearing before 1, and move them one by one until 1 is in the leftmost position.

Secret Lobster: That's not necessary right? For example if you have like if in this case we move six at the very beginning

Rocket Wind: Oh right yeah I just as you said it yeah. I feel like so close to this okay 32145, 32154. I'm gonna do this by hand real quick and see.

Secret Lobster: Let's let's think about what are the largest number you can keep you don't really need to move the numbers right?

Rocket Wind: The largest number I can keep?

Secret Lobster: Like just find what numbers you don't need to move

Rocket Wind: One never needs to move

Secret Lobster: What about your good case you need to move two.

Rocket Wind: Yeah wouldn't I have to move two?

Secret Lobster: Like in this case you will have to move two because two is before one and the worst case you don't need more two

Rocket Wind: Because two is after one yeah.

Secret Lobster: Like if you don't need to move two what about three, in what case you need to move three so basically just check the numbers one by one.

Rocket Wind: Oh okay right right right. And see what the largest number I need to move is. Or is it the smallest number I need to move?

Secret Lobster: The largest number you'll have to move

Rocket Wind: Wouldn't it be the smallest one that I'd have to move? Because I have to move five at some point, if I move five first

Secret Lobster: I think it depends on our int rotation, we are trying to maximise the smallest number you want to move

Rocket Wind: Next one is small, okay so 31254. So in this case what is the first thing I have to move? Three.

Secret Lobster: Right.

Rocket Wind: Two one moves from there. What if I have oh yeah that doesn't do it for me. In this case, five has to move, four has to move. Four is the smallest number I have but I'm picking the smallest number that I have to move. So I have to move the largest one last. I feel like I'm missing something here

Secret Lobster: If N is greater than right number

Rocket Wind: That's the candidate that's a candidate for being, the last to move. Then we have to move it at some point t. After that, at some point like in any case, if I see so like three one here, at some point three has to be moved.

Secret Lobster: If N is greater than its right number, right neighbour let me think about it. What about the last number? It has no right neighbour right.

Rocket Wind: Well, the last number we can't move because it's already in the last position

Secret Lobster: But what if we have like 123...12435?

Rocket Wind: What do we do? 12435

Secret Lobster: Do want to check this condition again and again, or only check it once?

Rocket Wind: Right, right. So um, well, I mean, I have to check individually each after each permutation no?

Secret Lobster: Then you, do you need to really move the numbers, like, for example, for the first time when you move four to the end, and you're like, you really do this to the array?

Rocket Wind: Yeah, that's what I was thinking. I guess I don't have to like,

Secret Lobster: Okay. Okay.

Rocket Wind: So I don't need the extra space do I?

Secret Lobster: We are running out of time. So I think we can stop here. I can give you some feedback. I mean, we're really into the time, we can just stop here. And I probably will give you a hire here. And like, for Google interview, probably you may have one or two questions. And if you have one question, the question might be, like, more difficult than the than the one you saw before. But I think typically or very often that have you will have two questions. It might be one with a follow up or like, one with another, like a totally new question. Okay. Okay. Like, I want to give you some general idea on Google interview, like for the first question, like, the highest rating you can get, it's kind of it's kind of higher. So it's very rare to give a strong hire based on only one question is, especially the question is, like, the minimum level? And for the second question, it's kind of like we are trying to raising the rating or raising the bar. And the second question is, like, more difficult than the first one. And, like, if you cannot solve them, it's okay, we just will keep the original rating. If we will can solve that, then we will improve your rating like from, if we give a weak hire before we can improve that to a higher if we give a higher before we can improve that to a strong hire or something like that. So that's the setup of, of a Google interview. And I think you already worked out the first one for the second one. Like, I think you are very close to that. But we don't need to, like really move the number because if we really moved the number, the time complexity is o(n), right? It's

Rocket Wind: Yeah, it increases dramatically. I wasn't even thinking about that. But yeah, right. What I finally do is see what the largest number I have to move is, and then based on that, I can calculate how many more moves there are.

Secret Lobster: Right. The tricky part is there, like we just so seems you delete my, you don't have my previous case. Like, it's like one, six, whatever two four three five something like that. In this way, if you don't need to move 123. The reason you don't need to move 123 is because that.

Rocket Wind: Because your subsequence is five

Secret Lobster: Right? You have one and you have two and you have three here, and you cannot find a larger integer number on the right. And it's not the neighbouring it's just a number. Yes, you can keep 123 and in this case, like the implementation is very simple. You can just keep a counter here, which is like, the largest number you cannot achieve right now. And for all,

Rocket Wind: You just get the longest subsequence starting from one, right, the rest of that okay, yes.

Secret Lobster: Right. You just plus by one and the return. And so forth mine is counter or something like that.

Rocket Wind: Yeah. Okay, that makes sense.

Secret Lobster: Right. And for the first question, like, you understand the DP perfectly. And let me see. Yeah, what I want to introduce is, I mean, what you explained, and what you like, gave me is totally fine. And what I want to give you is like probably a unifying like a unified framework, or unify the pattern for DP like you can answer these three questions is then, like writing so many words, and which may make your explanation like much clearer and like, which may save some time

Rocket Wind: You saying I should try to do it yeah.

Secret Lobster: Like for DP, as you already know, that like really to define the state, like, what is the state? Called to do the induction, whatever we're working on, it's mainly on for the second question, third, what to return? And, like, these three questions only make sense, when like you are very familiar with DP. I think you already, like reach to that state. So how to differentiate, there multiple ways to define the space, I can just like, pick up whatever way I want. Like DPIJ means, the minimal costs.

Rocket Wind: Okay. That's probably what I do when I do it on my own. But I'm afraid it's not clear enough. Like you think that's fine. Because the reason I do all of this is because I'm like, Oh, I feel like if I sit down like, okay, dp of x y, is this. And I feel like that's not enough. I don't know, though.

Secret Lobster: Right? I think like, as I mentioned, what your gateway is, like, it's totally fine. I just like other perspective to see whether it's like you're like that or not, like. So basically, it may save you some time, a cost of valid string of length as I plus one, ending with char per j. So the reason I use i plus one is because like, I want i to start from zero. And to do the induction, I think we already got the point. So basically, we need 2.1 is the base case, the others is the real induction. For the base case is quite simple. DP zero, equals to cost zero, because it's only simple, it's only single character, we don't really need to consider about the the restriction because there's no neighbours, so we only have one single character and the cost that is given by the char rate. And right, induction, if we want to construct a string of length, i plus one. Here i is larger than zero, ending with character J, let's construct a string of length for which is already solved the by DP i minus one. And suppose it's ending characters K let's select the minimum one, and append, the character J. Like we introduced the cost of i j and this is just the induction, the real induction, and the only restricted like K doesn't equal to j, and what to return, just the last row of the minimum value for last row. And basically, you are exactly doing this. And like you're just to reuse the cost. You just reuse the cost of array basically. And, like from these, it's also very clear that like, DP i only depends on DP i minus one if you don't want to reduce the cost so you can like, keep a separate DP array and you can

Rocket Wind: Right yeah, that's what I was talking about first. But I figured I could do with less space.

Secret Lobster: You can, like, just keep two rows, which is supposedly okay. Yeah, I think, yeah. If you think this is better, like, you probably can use this to describe your idea. And to change that to the code is also very simple. So that's my, like, kind of recommendation. And I don't have, like since figure out of the last question, I probably can change your rating to like, a leaning strong hire or strong hire because, like, you figure out that the second question before I gave you the, like, the real solutions. Yeah, I think that's all I want to describe today. So do you have any questions to ask me?

Rocket Wind: I'm thinking, Oh, okay. This is a question. So I saw this on screen coming up. How does on site usually work? Like, is it actually on site now? I have, because I don't have I have no interview experience outside of this website.

Secret Lobster: How onsite really works? So I think that these kinds of interviews kind of phone interview, the reason is that for onsite interview, like although the like the format or the style is more or less the same as this one for onsite you definitely have more ways to like to impact or to communicate with the interviewer for example, you will have a black border, right? You can, you can write, you can draw a picture, you can have body language or you can have like you can have eye contact. So, basically, you'll have some other potential ways to communicate with the interviewer. But then in terms of the question styles and like, the general processing, like how the interview looks like, it's more or less the same as onsite.

Rocket Wind: Really, so okay, so it's basically it's not that different. Okay.

Secret Lobster: Right. And also, by the way, by the way you for phone interview or probably even for onsite, we don't use IDE for Google interview. Basically, we write the code on the blackboard, or we use Google Docs. But since we are using this it's okay to use IDE. But, like, keep in mind that we don't really use IDE for Google interview.

Rocket Wind: Okay, no that's good to know. Because I, that's what I thought. But the last two I've done with Google on this site, they both had me switch to the IDE. That's good to know. Okay. I'm actually banking on them not using it because my code can be kind of buggy sometimes.

Secret Lobster: I mean, that's my experience, you probably can like, ask the, like, the recruiter for the like, updated information. From what I can tell

Rocket Wind: Yeah that's what she told me to I think you're 100% right.

Secret Lobster: Right. And also, I think other companies may like, let you probably grab your laptop, right, though, and you can use your own IDE but I don't think that's a Google thing.

Rocket Wind: Okay. That's how I prefer it anyway. So that's good.

Secret Lobster: Okay. Any questions at all? Like do you still have any feedback on me. And so whatever you want to ask or you want to suggest I'm open to all your, like, ideas or questions or suggestions.

Rocket Wind: Ah, honestly, no, I think this was good I think I was struggling at first, like earlier, I would have said that you were a little unclear with the first question, but I also think that might have been me because I'm kind of ditzy today. Because like, I completely got what you were saying with the second one. So I think that was mostly me. I think it was this was good. This was very helpful.

Secret Lobster: Okay, thank you. If you don't have other questions, we can stop here.

Rocket Wind: All right.

Secret Lobster: Bye.

Rocket Wind: Have a good day.

Secret Lobster: You too bye

Rocket Wind: Bye.