We helped write the sequel to "Cracking the Coding Interview". Read 9 chapters for free
Please read our definitive guide on Google's hiring process and questions
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) 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 Intrepid Panda (the interviewee)
Advance this person to the next round?
YesHow were their technical skills?
3/4
How was their problem solving ability?
4/4
What about their communication ability?
4/4
Support hire. Good points: 1. Figure out the DP algorithm super fast. 2. The implementation of DP only takes ~15 min 3. Dry run the code carefully. 4. Good communications. 5. Understand the time & space complexities correctly. And even do the optimization on the space complexity. 6. Good code style, bug-free. Suggestions: 1. Probably we can do the dry-run faster (It takes ~13 min to do the dry run), particularly, I think we can just use dp[i][j] = min(a, b, c) + cost[i][j] and write the result for each value directly instead of doing (simulating) the run step by step. 2. We didn't discuss the explanation of dp, I'll give suggestion here. For DP question, we can use this framework/question which makes it very simple to explain the idea and change it into implementation. Just ask & answer. the 3 questions: (2.1) what is the state? (2.2) How to do induction (including the base case and induction expression) (2.3) What to return? 3. As you mentioned during our talk, focusing on sample test cases/hints is useful sometimes. 4. In terms of "popular" categories, I think dp, graph and binary search (as a sub-step of a complicated question) are very popular categories for google interview though they are still very wide.
Feedback about Rocket Wind (the interviewer)
Would you want to work with this person?
YesHow 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
They provided great hints and guided me throughout the process. The second question they gave me was a great question and I learnt a new perspective to look at questions because of that. Overall great experience!!
Interview Transcript
Intrepid Panda: Hello.
Rocket Wind: Hello.
Intrepid Panda: Hi. Good morning.
Rocket Wind: Morning. We will have mock interview, so before doing that, do you mind briefly describe your expectation on the interview?
Intrepid Panda: Yeah. So I am going to be interviewing for Google on site l four level. And it's going to be like they told me there's going to be three coding questions and one Google enos and leadership round. So for this one, I want practice with the coding part.
Rocket Wind: Okay, sorry, why? You mentioned three coding questions. You mean three coding round, right?
Intrepid Panda: Yeah, three coding rounds. Sorry. Yeah, three coding rounds and one leader Google in this round.
Rocket Wind: Sure. Let me give you a quick question here. Let's see whether you encounter this before.
Intrepid Panda: Okay.
Rocket Wind: Yeah. I just paste it here and I can walk through this question for you like briefly. We want to create n. And to construct that screen, we only have four kind of characters to use. We track a, b, C and D. And our character set only contains a, b, c and b. And we also have a cost array. And the cost array is two dimensional integer array. And the first dimension is always n. The second dimension is always four. So it means the cost to put each character on each position, meaning it's per position, per character's cost. Let's see the example in line nine, which is the cost array, which is two by four. And it means we want to construct a string of lines two using a, b, c and d. And let's say the position starts from zero. And if we put a, b, c and d on the fourth, on the zero's position, the cost are two, three, four and five given by the zero zero of the cost array. And if we put a, b, c and d on the first position, the costs are seven, three, four and one separately given by the first row of the cost array. So that's the meaning of the cost array. And we have a restrict that we cannot use the same character like on the two neighbors. Basically, the string you construct cannot have like a, a, bb, cc or db as the substring. And that's the only restrict we have. Our goal is to construct the string for less n with the minimal total cost. So for our example, the string we can construct is ab. So the cost is position zero. We use a, which is two, and position one. We use b. The cost is one. So the total cost is two plus one, which is three. We need to return the integer three as this example.
Intrepid Panda: Okay. Okay. Okay. Okay. Okay. So, yeah, so what I'm going to do is first I'm going to quickly write down some constraints.
Rocket Wind: Sure.
Intrepid Panda: So you said that the cost array, the size of the cost, the number of rows in the cost array will always be equal to n. So correct.
Rocket Wind: This means basically we don't really need n because the cost array. Yeah. Already has the n as a parameter.
Intrepid Panda: And then there will be four columns. So correct length of cost of zero is always equals to four. Okay. And so can the costs be negative?
Rocket Wind: So let's assume all the numbers are positive here.
Intrepid Panda: Okay. Okay. So. And is there an upper limit or is it arbitrarily large? The values, they can be any very big value too. Right?
Rocket Wind: There's no bound. But like, we don't need to consider like, the total cost is larger than like the integer, the measure. Yeah, you don't need to special consider that.
Intrepid Panda: Okay, so I'll assume. Yeah. Okay. Okay. And how large can NBA. So can n be zero at all?
Rocket Wind: No, let's assume all the numbers are possible, including n. Okay. And probably let's assume like, let's say the cost are like less than 1000 and, and the n is less than, let's say 1 million. Less than or equal to 1 million.
Intrepid Panda: Okay. Less than equals to 1 million. Okay. So that is right. Okay. Yeah. Okay. So these are my constraints. Okay. So, okay, the first thing that is coming to my mind is what I can do is for each position, I can. So for the first position, so when I'm looking at the first position in the string, since there is no previous value associated, I can pick the minimum cost value from here. So for my first position, I see, okay. Two is the minimum value which corresponds to the character a. Yeah, so I actually forgot to clarify this. So a will correspond to zero, b will correspond to one, and so on, right?
Rocket Wind: Correct.
Intrepid Panda: Yeah. Okay, so for the first character, I can see that. Yeah, I can pick a as that has the minimum cost and there is nothing before it. So there is no chance of duplication. Now when I go on to the second character, I need to make sure that there is no. So based on what my first character choice was, I have to select the minimum. So for doing that, what I can do is for each of these, for each of these characters, I can find the minimum cost that I can get. So for, let's, let's forget that I had picked a in the previous, previous choice. So if, if in this choice, if I wanted to pick a, then I cannot consider this, right? Because then it would create duplication. But then I have to pick the minimum out of these three. So if I consider that the minimum out of these three is three, and this will get added with this current, current a's. Cost. So that, so, so to pick a on the second, to pick a as my second character, the minimum cost that I can generate is three plus seven. That is ten.
Rocket Wind: Right.
Intrepid Panda: Now when I'm picking. Now, if I want to assess the cost of picking b as my second character, what I have to do is I have to ignore this and then take the minimum of the other remaining three. So that becomes two and two plus three becomes five. So similarly for c, I have to ignore this, pick the minimum of the other three, that is two. So that becomes six. And then for d, I have to pick the minimum of these, these three, and that becomes two plus one, three. So I'm assuming that we only have to return the cost and not the actual string, is that correct?
Rocket Wind: Yes.
Intrepid Panda: Okay.
Rocket Wind: Your idea sounds cool to me. So what about the time complexity?
Intrepid Panda: Yeah. So in this, what I will be doing is I will start iterating from the second value itself. So in the cost array, I will start iterating from the second row and for each second row. So, so for, sorry, for each of those iterations, I'm going to look at. Okay, so the first thing that comes to my mind is I'm going to have to create another, another 2d array called min cost. So this min cost array will store the minimum cost for the previous iteration. Actually, I think to optimize space I can have just the previous state, right? So yeah, I think what I can do is I can have a prev, prev variable. So this prev variable will store the cost zero row. So this, this variable will stole the store the cost zero through. And then I'll start iterating on this row. And then inside that, for each of the position, I am going to look for the minimum of the other positions in the previous one. But since we are guaranteed that it is of the length of four, that is a constant time operation. So in essence, what I will be doing is I will be iterating over each and every row and there are n rows. Let me think if I am doing any other operation or not. So basically it is four n because I'm doing like four times. I'm trying to identify the minimum, but I think the time should be big o of four n, which is actually considered as big o of n and the space. So what I'm doing over here is I'm going, we're going to have only like the one row, right? Like the previous row. And that row has only four columns. So that is constant. So I would say space is big o of one.
Rocket Wind: Okay.
Intrepid Panda: Does that make sense?
Rocket Wind: Yes, this sounds cool to me. So do you mind implementing it?
Intrepid Panda: Yeah, def, let's see, min string cost. So this function will take in the cost matrix. We don't need the n value because as we said that we can just take the length of cost and, oh, this is a tab, I'll use two tabs. So n is equals to length of cost. Okay, so I will have to define my previous state as cost of zero. So I have, I know that it, it will at least have one rule, right? Yeah.
Rocket Wind: Right? Yes.
Intrepid Panda: Yeah. Okay, so I don't need to check that base case. So then what I do is for I in range one to n, for I in range one to n. Now I have to create my current, this thing, right? So what I'm going to do is cur cost is equals to cost of I, and then I'm going to update this cur cost and then assign the cur cost to prev cost for the next iteration. So what I'm going to do over here is for j in range four. So cur cost of j is equals to minimum of, okay, so again over here also I will have to find the minimum of the other three. So here what I will have to do is, okay, so I'm considering for the row I and the position j. So for this position I have to get the minimum from the previous state. So min prev cost, min prev cost. So min prev cost can be prev of zero. And then for k in range four, min prev cost can actually start at one min prev cost is minimum of in prev cost and prev of k only if, because now I have to make sure that, so if j not equals to k, min prev cost is this. So when I come out of the k loop, I have the cost for the minimum cost from the previous state for all the three other characters, right? So in this case what I can do is curve cost of I j plus equals the min brev cost. And then after this loop I can do prev equal curve cost. And then what I can do is I can return, okay, so for at the last iteration, Prev will become the, the final, final one, right? Yeah. Prev will be the last, considering the last row. So I have to return the min out of that. So I have to return min out of breath. What I can do is I can quickly do a dry run of this and check if it works or not.
Rocket Wind: Okay. By the way, what's the dimension of the current cost? I think it's a one dimension.
Intrepid Panda: Oh, yeah, yeah, yeah. Sorry. Current cost is a one dimensional list. I don't know why I did that. Sorry.
Rocket Wind: No question why k starts from one. Basically. Why you, like, skip zero there.
Intrepid Panda: Because I assigned. Oh, yeah.
Rocket Wind: Okay, that's cool.
Intrepid Panda: Okay. Is it fine if I do a quick dry run?
Rocket Wind: Sure. You can do a driver, but yeah, I think my question is, like, I know you, I know you have line 34, right? And like. But j can be like j maybe zero as well, right? So your mean prevails. Cost may not be valid.
Intrepid Panda: Oh, okay. Okay. Yeah. So, okay. Yeah. So in that case, if j is zero, then I can, there is a possibility that the next one is also zero. And it could fix that one up, right? Yeah. So I have to assign it a value that is non zero. So some other value. Right. Basically any other value. Or I can just get, I can just assign it to some very high value.
Rocket Wind: Like you can use infinity, or you can check j here, and then I.
Intrepid Panda: Can remove this criteria. Sure.
Rocket Wind: You can do a like, simple dry run. Probably just use our test case, or you can create your own.
Intrepid Panda: Yeah, I will use this one. So, iteration. Iteration one. Okay, so first let me see. Prev is five. Okay, now I equals to one. My cur cost becomes seven, three, four, and one. And for j in range, this. So now minus rev cost is infinity. Let's see. Min pref cost is infinity. J is now zero. Okay, so now k in range. This, like, now k is zero. So this, this won't go in because both j and k are same. So then k becomes one. K becomes one. Min prev cost is this prev of k. So previous of one is three. So obviously three less than infinity. So min Prev cost is updated to three. Then k becomes two. We check four, but four is greater than three, so it won't get updated. Sorry, we have to check it. Check in prev. Sorry, Prev. Right.
Rocket Wind: The pre was not the current.
Intrepid Panda: Yeah, current, yeah. So one, two. I think one, I checked correctly, three. Right.
Rocket Wind: The values are the same. Right now.
Intrepid Panda: Yeah, yeah. Right now, yeah. So k becomes two. So four. Uh, four is still greater than three. So this won't get updated.
Rocket Wind: Right.
Intrepid Panda: Then I would go here at the end. Five is still greater than three. It won't get updated. So then it would come out of this loop and it would do. Current cost of J. So j, in this case is zero. So that will be seven plus 310. So this gets updated to ten. Now J becomes one and this becomes I assigned previous is equals to current cost. So this becomes ten.
Rocket Wind: Not really. Right. You haven't, you haven't done the chain loop, right?
Intrepid Panda: Oh, yeah, yeah. I haven't. Yeah, because I'm still inside the for loop, so I haven't done that yet. Yes, this 2345. Okay, so min prev cost is this. Now I still won. Okay. I think what I can do is like this, j was zero, now j is one. So current cost equals to cost of I. So that is seven cost of I. Yeah, I think current cost is still the same, which is ten, three, four and one because. Yeah, that hasn't been. But I updated current cost. Yeah, okay, that is fine. I updated current cost. That is fine. And then the minimum previous cost becomes infinity again because that is how we initialize it. Now for k in range zero to four, j is now one. So for the 0th one, it will consider this time, because zero not equals to one. So minimum previous cost is minimum of infinity and previous of k. So previous of zero. Right. So that is two. So here it will be two. Then it will check with three, four and five. Since two is the minimum, it will keep that come out of the K loop. And then current cost of J, which is j, is going to be one in this case. So currently it is three and it is going to do five over here.
Rocket Wind: Yes.
Intrepid Panda: So now j becomes two, current cost is ten, five, four and one. And min prev cost is infinity. Then I will come here, I will compare zero and one, because j is two. So basically I won't compare four. So out of two, three and five, the minimum is two. So this will become two again. It will come out of this loop. So current cost of J, so J is to. So this becomes four plus this minimum cost. So this becomes six.
Rocket Wind: Right.
Intrepid Panda: And the last iteration will be j equals to three. Current cost is ten, five, six and one. Min prev cost is infinity. In this case, I won't look at this one and all the other three. The minimum out of them is two. So this will get updated to two. I will come outside of this K loop, current cost of three. So that is currently one added two and I'll add the min previous cost to it. So that becomes three. And I will exit from the J loop. And then previous now becomes the cur cost. So previous becomes ten, five, six, three, and I now becomes two. But since our array is only. Yeah, so basically I has gone out of bounds now. So we will stop and return the minimum of three.
Rocket Wind: Sure. Cool. I think you saw this perfectly. Since we still have like about 20 minutes, let me give you another one.
Intrepid Panda: Okay.
Rocket Wind: Yeah, I just pasted here, and before I can go through this for you. So this time we have a list or array, and it contains a permutation of numbers, one to n, meaning each integer from one to n occurs once and exactly once. And you want to solve the array. But the only operation you have is, like, to select a number and put the number to the end. In other words, the only operation is like, you move a number, an arbitrary number to the end. So when you move the number, all the numbers in the positions behind it will be like just a shift to left because the array cannot have a hole. So you are trying to use the minimum number of these operations to sort the array. Like, basically, after sorting, it should be exactly from one to n. Let's see. For the first example, the input array is 51432. And at the first step, you can just move the number three to the end, and it changes into 51423. And then you move four to the end and it changes to 51234. And finally, you move the largest number of five to the end, and it's sorted into one to five. And in this case, you need to return three because three is the minimum number of operations you can use to sort it.
Intrepid Panda: Okay. Okay. Okay. So the operation is to take a number and put it at the end and all the other numbers move to the left. Okay. That, that is the operation. Okay. And the goal is to do minimum operations to make it sorted. Okay. Okay. So let me write down the constraints. Okay. So the array will always contain numbers from one to n. So, right. Length of array is so length of array. If it is one, then only there will be one. Can the length. So it. So length cannot be zero because it is given that it will always contain from one to. So that at least has to be one.
Rocket Wind: Sure. Let's assume it has at least two, because line is trivial. One is just written zero, basically.
Intrepid Panda: Okay. And any upper bound or arbitrarily large.
Rocket Wind: It should be arbitrary large. But let's just assume one, meaning like six, power of ten.
Intrepid Panda: Okay. And the values can, they can be positive, negative, zero.
Rocket Wind: No, it's a permutation, one to n. So it.
Intrepid Panda: Oh, yeah, yeah. Sorry. Yes. So. Got it. Okay. So the values will always be from one and less than equals one. Okay. And each of these values will always be present.
Rocket Wind: So, right.
Intrepid Panda: Of the values in the range will be there. Okay. There won't be any repetition. Right.
Rocket Wind: Right. It's exactly like to end.
Intrepid Panda: No repetition. Okay. And. Okay. I think that should some of the constraints. Okay, so the first thing that is coming to my mind is going from left to right, or having, having two pointers, one at the start and one at the end. And if the start value at the start pointer is greater, then put that start pointer value at the end and increment the start pointer to the next one. Actually, no, keep the start pointer there because then one will come over here and the end pointer stays at five. And then if the right, if the start is actually less than the right, then increment the start. And keep doing this while the start is less than the end or the right, the left is less than the right. So if I try to do that in this example, what will happen? So five and two. So five is greater. So then I will move five at the end. So this will become 1432 and five. And my start is. Left is here and right is here.
Rocket Wind: This may not be correct. Five is too large. If you move that to the end, like, you probably have to move lots of numbers because you need to move five again later.
Intrepid Panda: So. But since five is the greatest number.
Rocket Wind: Yes, it's great.
Intrepid Panda: Okay, okay, okay. I get what you're saying. So some, there is a possibility that the right will move on to and then I will compare four to two and then four will go be behind five. Yeah. Okay. Another idea that's coming to my mind is since we know the numbers, we should definitely know what position they should belong to, right?
Rocket Wind: Correct.
Intrepid Panda: Five is going, definitely going to belong to n minus one position, which is index four. This is going to belong to index zero. This is going to belong to index three. Now, the least number of ways to move a number from index zero to index. So if I see three. So three is currently at index four, but it needs to be at index three over here. And this needs to be over here. The operation is only that we can pick it up and put it at the end. So, but we need to put it at the end such that no other smaller number is going to be put at the end after it. So the order of putting at the end matters here if we want to minimize this. So, for example, deciding to put five at the end first is not a good idea because then good chance that I will put four or three behind five, which will destroy the order.
Rocket Wind: Right?
Intrepid Panda: So pick the number that has picked the smallest number that is out of position and put it behind. Would that work? So in this case, the example that you showed me what you did was 51432, which was converted to 51423. So you basically took this number and put it behind. So you went from the right and identified the biggest number that was out of position and put it at the end.
Rocket Wind: How to define output position?
Intrepid Panda: Out of position is. So a number n must belong to the index. N minus one. And the current index will be whatever it is at right now. Right. Like so for example of three. So three. So three should belong to. Belong to two. But at 0123. But at three.
Rocket Wind: Yeah, but two is also out of like auto position as you define. Right. For the first.
Intrepid Panda: Yeah. Two is also out of position. So what I'm thinking is the first number. The first number from the right.
Rocket Wind: Why not?
Intrepid Panda: Yeah. So what I'm trying to do is the greatest, the first number from the right. That is more than. So if I start at two, I want to check if is this the one that is highest at the end. Because I don't want to put smaller numbers behind this. So if it was the highest at the end, then that would actually be. So what if it was 1435? What if it was one, four, three and five? So in this case, this five is already the highest over here. And then two, three and five. So in this case, five is already here. Or if I can go from the left. And so if I see that five is already in its place, then the next number is three, is 0123 is not in its place.
Rocket Wind: Four is nothing in the place as well.
Intrepid Panda: Yeah. Four is also not in its place. But that is the next, I think.
Rocket Wind: Two, three, four, like all the middle three numbers are not in the place.
Intrepid Panda: So what if I did, for every iteration, what if I identify the greatest number that is not in its place? So in this case, the greatest number not in its place is four.
Rocket Wind: But in our case, like in line 64, the first number is five, right?
Intrepid Panda: Yeah. Here. Yeah. No, I was just thinking out loud about my approach. And I don't think that approach will work. The other one, that was, I was saying before where pick the largest from the right. So I'm. Yeah, go ahead. Now I'm thinking that I might be able to pick the largest element that is out of place now. Yeah, I'm thinking on these lines, so that in this example, that can be four. So that is the largest out of place. Then put that at the end. So what that would give me. That would give me 1235 and four. Okay. Now the largest out of place would be five. So.
Rocket Wind: This is correct. But for our sample, the first sample, test case, you already figured out we shouldn't move five, right? Based on your description, the lattice one out of order, which is. Which is five.
Intrepid Panda: Oh, yeah. The largest one out of this is five. So it becomes 1432 and 51432 and five. So in this case, then four would go. Yeah.
Rocket Wind: Basically, I don't think, like, I don't think we should use the position. The reason is that if you. If you move one number right, the position will be changed. So, like, all the numbers behind it will be shift left. So the position itself is not a stable. Like, it's not a stable metric because it can be changed. And even if a number is in the correct place right now, it doesn't mean it will always be there because, like, when you move number, all number will be, like, shifted to fill the hole.
Intrepid Panda: Right. Yeah, because position is. Here.
Rocket Wind: Let me ask you some questions to see whether, like, you have more, like, deeper understanding on this. And first, like, very easy, like, very simple question. Do you think we need to move number one, like, for optimized case.
Intrepid Panda: In this test case?
Rocket Wind: No, for all the test cases. If we want to get the minimum number of operations to solve, do you think we have a case to, like, we need to move number one?
Intrepid Panda: I believe that number one should always be shifted left by moving other numbers.
Rocket Wind: What I mean is. Yeah, it can be changed. What I mean is, do you think we need to move number one?
Intrepid Panda: Like, take it from a position and put it at the end? No, I don't think so.
Rocket Wind: Right. Use the operation to move number one.
Intrepid Panda: Yeah. You, like, move some other number such that one gets shifted towards left.
Rocket Wind: Right. What I mean is, do you think we need to pick up, like, pick number one to move to the end?
Intrepid Panda: No, we shouldn't.
Rocket Wind: Okay. For. For the. Because number one is very small. Right. So if we move number one, we probably have to move all the numbers because.
Intrepid Panda: Yeah.
Rocket Wind: Otherwise not solve them. And second, like, for each number, like, do you think we need to move the same number more than once?
Intrepid Panda: No, we shouldn't. If we are moving the same number more than once, that means we have completed a full circle. Right. Like, and that means that we have completely missed the optimal way of doing it.
Rocket Wind: Right. It's not because of circle. I think. I think it's because, like, if you have to move the number the second time, and then you can just save one time for the first time, because, like, the second time, when you move that, no matter where the number is, you just move it to the end. So even if you don't wait for the first time, it doesn't matter, you will have the same effectiveness. And, like, here is, like, no, like at most, once for each number. So the third question is very important. Like for if we have to move a number x, what do you think the numbers other than x, do we need to move them or not?
Intrepid Panda: If we have to move a number x, what do you think on the numbers that are larger than x? So to clarify this, do we want to move a number x which has larger numbers in the array?
Rocket Wind: This is like, the question is, if we already decide to move x, we haven't asked how we make the decision. Like, suppose we already decide to move number x. What do you think about all the other numbers that are larger than x?
Intrepid Panda: Then we'll have to move them too, because since they are larger, they have to be towards the right of that number, the number x. And the only way that can happen is by taking them and putting them.
Rocket Wind: At the end, right? This means we have to move all the numbers that are larger than or equal to x, right? If we decide. So if we have a conclusion on this, basically it means that so for numbers from x to n, we have, and for numbers from one to, like, x minus one, we can give them a mole. And our goal is to find the largest x like we need to move. Basically, the larger the x is, the smaller the less number we need to move. And you can think about it from another direction. So the larger the number x is, the more number you can keep unmute. So basically you can, like, you know, we don't need to move one, number one. We don't need to move that. What about number two? In what case you have to move number two. And if you have move number two, then you have to move, like all the numbers from two to n. Then if you don't have to move number two, what about number three? In what case you need to move number three and in what case you don't, if you like. Similarly, if you have to move number three, the answer is just like n minus two. If you don't need to move number three, what about number four? You can just think about numbers one by one. For each number, you make a decision, like whether you need to move that the first time you find, like you need to move this number. That's the answer. Because you need to move all the numbers, like larger than that. For our example. For example, for the first example, right, the decision we make is to move number three. Then what we really move, like adjust the three, four and five. For the second example, it means like x equals to two. So we decide to move number two. Then we need to move, like all the numbers larger than or equal to two, which is. Which are like two, three, four and five. So the key point is here is like how to find x.
Intrepid Panda: How to find x. Yeah. So for one thing I noticed for three, here is the left of three is greater and the right of three is LEss than that. But for any other number, I don't see that.
Rocket Wind: What DO you think? Like if you want to move x, basiCally, if you want to move x, it means that one, the numbers from one to x minus one are already in order. That's the reason. Right. Then like, what do you think like the, the list looks like in this case?
Intrepid Panda: Like why left, left half of the list is sorted becaUse. No, not necessarily. So the, we, we want to move numbers from one. We don't want to touch numbers from one to x minus one.
Rocket Wind: Right. There, these numbers are sorted. There might be like some other numbers in between.
Intrepid Panda: So for three, we don't want to touch one and two. One and two. One, two. X minus one. Why? So one has to be on. So we are going to move x to n numbers. So that way what will happen is one, one will get pushed towards the left. Difference between. So here n is five and x becomes three. So two and. Yeah. And minus x numbers. Okay.
Rocket Wind: Like the difference between like the neighbors or whatever, because the, like the neighborship the neighborhood or like the position, like they are not the stable relationships. Because when you move them, like, all the neighborhood and positions will be changed.
Intrepid Panda: Yeah, yeah. Because if we see that we moved three. Right. So the whole positions changed.
Rocket Wind: The question here is why we like need to move three. We don't need to move two.
Intrepid Panda: Yeah. So if we want, have to move all of them one to x minus one, we can keep them unmoved. So, so if we were, if we were thinking that X is two, then we would only have to move one number. No, sorry. We would have to move, we would have to move two, three, four and five. Four numbers. And if we move four numbers, then what? Can we find the distance of one from the number? Because one has to go to this, this index. But yeah, you're right, those positions are not fixed. So if I see, if I find what distance one lies from three, so in this case it's two. And so when I move three, I'm going to be moving three to n. So I'm going to be moving three, four and five. So I'm going to be moving three numbers. Okay. But three, since one is on the left of this, I'm putting three here, 5143. And two. Two just got pushed here. So one needs to move one position towards the left to come in the correct place. No, I don't think. Yeah. Then in that case, four would have been a better option. But it's not.
Rocket Wind: Okay, I think, like, let's stop here. I can give you the answer. I think in line 85 and line 86, we should consider, like, what does the sequence or what does the permutation look like if we only need to move x to a. Basically it's something like this. We have one somewhere and we have two somewhere. So all the dots might be some other numbers, and you have x minus one somewhere. And it's something like this. The largest number you can find in this order. It's not position, it's just order. The numbers you can find, or you can take this as like subsequence, the numbers you can find, the largest number you can find in this increasing order, starting from one. It's like x minus one. And x is somewhere, like in the dots, not in the last position, like not in the last brackets, because if you find x after that, you will make it longer, basically. So basically, x is like in some position before x minus one, something like that. And if you really, like, take our example, it's kind of the reason we don't need to move two is like two is on one, right? So we have the subsequence of one, two, and we don't have three on two side. So we need to move all the numbers that are larger than or equal to three. In other words, if we delete a number like five, four and three, the number, the numbers remain, like I just increase in order. And for the second case, it's similar. We don't have two, we only have one. And what's left, we don't have two. So we need to move all the numbers that are larger than or equal to two. And like, if I give you another example, like, for example, 1524 x three, six, let's see, something like this. And we don't need one, two and three minus here. And on one side we have two, on two side we have three. So we can keep three numbers. We don't find four on threes, right? So we need to move like four, five and six.
Intrepid Panda: Four, five and six.
Rocket Wind: Basically, we just delete them. Like click the. Click the array or click the list. That's the reason I wrote, like, what I wrote in line 90. And if you like, we agree on this. The code is very simple. Like, we just say from the. Yeah, we just save a counter. And then if x equals to counter, we just plus counter by one. And here, basically, counter is the x. Like, counter is the x we discussed before. We need to move from counter to nice. So which is less minus counter plus five. It's something like that. That's the reason I think, like, the third hint is very important. And basically we need to figure out, like, in this way, as I suggest you, like, what does the, what does the subsequence or what does the permutation look like if we can keep them unchanged.
Intrepid Panda: Okay. Okay. I understood what you. What you're saying.
Rocket Wind: Yes, it's something like this. And to give you feedback, I think for this interview, I will give you a hire because of the first question. So typically for Google interview, we all have, like, it's possible that you only have one question, but in that case, that question might be like a hard level question. And I think that kind of setup, like, not very popular recently because it's a little bit kind of biased or it's a little bit dangerous to decide everything based on only one question. So the more popular setup is kind of. We will have more than one question. The first line is a level question, for example, like, what we have in this interview, and it will solve that perfectly. We can give you another question, and the other question might be a follow up of the previous one, or it can be a total, totally new question. It doesn't matter. And for the first question, like.
Intrepid Panda: The.
Rocket Wind: Sailing performance, the sailing rating we can give you is kind of higher because it's very rare to give you a strong hire based on only one question. Especially that question is in the minimum level. And that's also the purpose of the second question. And for the second question, we are trying to improve your rating, meaning if you solve that perfectly, we probably can change your initial rating from, like, from higher to strong hair or from like, weak hair to hair, whatever, depending on your performance on the first question. But it's okay that you cannot solve the second question. Like, we just keep the original rating. We don't make your. Basically, we don't make the rating worse based on the second question, performance. So it looks like the second question is a bonus. And, yeah, I think you saw the first question, like, perfectly. And, like, I'm not sure whether you, like the question is indeed the dynamic of programming. I'm not sure whether you consider about that or you just come, like, you just work out the solution without thinking. Like, without thinking. It's a dynamic programming.
Intrepid Panda: I mean, I saw that. I can use the previous results. So, I mean, I had an idea of, I may be able to use like, a DP array and all that stuff, but then I thought that this approach is like, simpler. And it came, this approach came first to my mind, so I decided to go ahead with that.
Rocket Wind: Okay. Indeed, for this question, like, some candidates gave me, like, the result, not result, the solution for recursion, recursion code. And then, like, I was just told, like, this is just a brute force with memorization. Like, in that way they don't, they didn't even consider this as a dynamic programming. And what you mentioned is just a kind of dynamic programming. Like, I'm not sure, like, you want to like, go more deeper than, like, then the solution of the first man, since you already got a correct solution.
Intrepid Panda: Yeah. You can give me feedback on my thought process and the code.
Rocket Wind: Like, your feedback is totally okay. Like, sorry, your code is totally okay. Like, I will give you a hire based on. So I don't see any concerns based on your solutions. I just wonder whether you want to, like, how to say that. Whether you want to think you want to discuss about more on the, like, dynamic programming perspective.
Intrepid Panda: No. So I actually want to ask you some questions. So regarding the second question, what pattern or what, like, type does it belong to?
Rocket Wind: I don't want to say, like, I don't want to say this is a brain teaser, but it's very difficult to, like, classify this, like, this kind of question into some classical algorithm. So if we, like, really need to do that, probably it's kind of like just a kind of a request which is like, verified. Everything can be array or set. So we have lots of questions like this one, but we cannot classify this question into, like, some classical algorithm, like greedy or like the dynamic of programming, whatever. So I don't think there's a, like a good label or good calculator for this question also.
Intrepid Panda: So for example, like, if you were given this in an interview, like, what kind of thought process or what trail of thought would you start with to tackle this kind of a question?
Rocket Wind: I think what you did is like, there's nothing wrong with what you did. So it's very difficult to describe how to approach this one. But basically we need to figure out what numbers are really need to be moved, but we need to consider, like, how to do that. Basically, as I mentioned, the neighborhood is not stable and the position or the index is not stable. We need to find something that can be globally used. They are not, at least they are not neighborhood. They are not the position. I think for the second question, my expectation is after giving you the three hints in line 18 to 88, especially after the last hints in line, like 90, if I wrote something like that, like, the candidate probably can, like, work it out because the only thing we need to figure out is how to define how to determine x. And, like, go going through the examples, like why we need to, for the first example, why we can keep two. And like, just think about when, when we, like, just write out what numbers we move. Right. For the first one is three, four, five. For the second one is like 2345. And then we know, like, why we need or why we need to, like, ammo the previous numbers, we can figure it out. And, like, that's my expectation. I didn't expect the candidate just work it out directly. I think for the second question, it's okay to use some hints and which may not really affect your ratings because you already solved the first question. So I, yeah, I think that that's the reason the second question works. As a bonus, if after some hints, the candidate works, it works it out. I think it's still possible to get a strong hire based on, like, the first question.
Intrepid Panda: Got it. Got it. I got it. Yeah. Yeah. I agree with you that after the 8788 hint, yeah, I think the thing that I learned from it was always use the hint and the given example and try to identify the pattern. So if I would have done that, like, if I would have seen in the first example which numbers are exactly being moved. So I would have clearly seen that the numbers that were moved were only three, four, five. And why is that so? Because one and two are in, what do you say? Like, they are. The sub sequence is in order. Right? Like one, two is the subsequence. The only subsequence that is in order. The other subsequence, which is 345, is out of order, which needs to be moved. And then that becomes your x. The minimum of that is three. That becomes your x, and then that actually is your answer. Yeah.
Rocket Wind: Please go ahead.
Intrepid Panda: No, sorry, you go. I was just done.
Rocket Wind: Oh, I think I hinted you about, like, we need to find number x and we can consider that in other direction. Like why is not moved? What about two? So in what case we need to move to and in what case we don't need to move to? And if we don't need to move to, what about three? Like, in what case we need to move three and in what case we don't need to move three? So, like, that's a correct direction to go. Like we just consider number from the smallest to the largest one and one by one to see for each number whether we need to move that. And like at that time, I think you still work down like what is that? The first, the largest number that are not in the order and not in the correct position, I think. And like you work on the, which is, I think which is the first example, right? Not for the example in line 63, I think.
Intrepid Panda: Yeah, yeah.
Rocket Wind: And at that time I think I already gave you the counterexample. Like our sample test case five is a number you need to move based on your algorithm. Although you'll find like, although you already find the correct test case of line 63. We already have the counter example in line 54.
Intrepid Panda: Yeah.
Rocket Wind: Do you have any other questions to ask me?
Intrepid Panda: So like normally in Google interviews, what are some of the important topics that I should cover? Like I know BFS, DF's, graph, dynamic programming, these are important, but any specific ones that you'd like to tell me?
Rocket Wind: Indeed, when I was asked about this question several times and like what my answer was just like dynamic programming, graph plus binary search. The reason I mentioned Banner search is because we probably won't give you a like straightforward banner search question. We may give you like a question that is complicated enough, which takes a banner search as a substance. Like we don't have to do a simple binary search directly, but it might be like intermediate step for a complicated question. But what you mentioned makes some sense. We do have very popular interview questions with dynamic programming and graph. I think the reason is that also for Google interview, if you reach the second question, typically the second question is the code is very simple. So if you figure out what to do, the implementation is very simple. That is because after you're solving the first question, we probably don't have much time. We probably have like 15 minutes or 20 minutes anyway. That may not be like sufficient to work out like very complicated implementation. Instead, we'll give you a question like you need a lot of analysis to figure out what to do. But after figuring out what to do, the implementation is very simple. Like that's the property of questions like this. And also for the second question, it's probably okay that you like, you don't have the full implementation because since you solved the first question perfectly, we know that we have the signal that you can turn your idea into the correct implementation. So we don't have concern or we already evaluate your implementation ability, so we don't need the fully code. And what you can do is kind of, you can describe the algorithm using some comments or like even with some pseudo code, whatever works for you. So we don't really need the full implementation for the second question in most cases. And like go back to our original question, the reason we have DP and like graph questions, I think it's because for DP, it's kind of the second, like, it's kind of the second question, like the category of the second question in some sense, because for DP question, typically the implementation is not very, it's not very long and you need to analyze it like the structure, the overlap, the sub problems and the induction, whatever. You need to do some analysis to work out the final implementation. Like the gap between the, between the idea, like not between the idea, the gap between the question itself and for the idea is like a little bit large, but the gap between the idea and the implementation is kind of small. So it's kind of, we try to evaluate your ability to, like to design or to analyze the algorithm. And for graph question, it's. On the other hand, most graph questions in interview are very straightforward. They are not very difficult. For example, just something like the classical algorithm, like minimal spending, training, DF's, bfs or whatever. And like when you, when you read the question, you probably already know how to do that. You don't, you don't need to do like lots of analysis on the question, but the implementation might be longer than a DP question. So you may have like for example, for DP question, the length of code might be like, let's say 50 lines of code, or even like less than 50. But for a graph question, typically your code might be like 18 lines of code, or even longer, 100 lines of code. So I think the purpose of the graph question is we try to evaluate the ability for implementation. So basically, CP and the graph are two categories to evaluate the different abilities. One is for like the state structure and the algorithm, like design or event algorithm, like how to analyze time and space complexities. And for graph question, we focus more on like the implementation, whether your code is correct. So whether you can implement like a much complicated code. Although the idea behind that might be simple. So that's the reason we have these two big categories.
Intrepid Panda: Understood, understood. That's a very good explanation. Thank you so much for that.
Rocket Wind: No problem. Although the, like, the two categories are still very wide, right?
Intrepid Panda: Yeah, they are very wide. But I understood your point, like, because even while practicing, I noticed that graph questions, I, when I read the question, I'm able to know that, right? Okay. I need to use union find and then maybe change union find slightly over there and then I can get the answer. And it takes some time to implement it. But DP questions are like, I get sometimes stuck on them, but once I'm able to figure out what to do, the implementation is just like probably ten lines in 15 minutes. Yeah.
Rocket Wind: Right. The DP question is more like, like our second example here, like you in some dimensions, right. In terms like the length of the code and the idea behind the code, basically. And like graph question is just kind of straightforward.
Intrepid Panda: Yep, yep, yep. I totally agree. And that's actually a very good analysis. I'll remember that. Thank you so much for that.
Rocket Wind: No problem. Do you have any other questions?
Intrepid Panda: I think no, you covered a lot. Like, thanks a lot for that. And the second question was really good. I think I learned a new way to think.
Rocket Wind: Yeah, it's a real Google interview question, although I don't think you will encounter the same one because I think it's already banned, because it's already published, I think. But it's like, it's probably like seven years or six years ago. You may encounter this question. That's a real Google interview question. And the first line is not real. The first line is like, kind of like, I can only say the first line is just a category. Like, we know Google may use tv question and I just like create one by myself, but the second one is kind of real.
Intrepid Panda: Oh, wow, that's really nice.
Rocket Wind: Yeah, no problem. Yeah. If you don't have any questions, we can stop here.
Intrepid Panda: Yeah, I think, yeah. I'm very happy with the overall interview experience. Thank you so much for taking time to interview me.
Rocket Wind: No problem. Thank you.
Intrepid Panda: Yeah. Have a nice day.
Rocket Wind: Bye, you too. Bye.
We know exactly what to do and say to get the company, title, and salary you want.
Interview prep and job hunting are chaos and pain. We can help. Really.
