Count Triplets

Watch someone solve the triplet array 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

Triplet Array

Interview question

Given an integer array arr, An interesting triplet is defined as 0 <= i < j < k < arr.length such that arr[i] < arr[j] < arr[k] Please check whether arr has at least one interesting triplet.

Interview Feedback

Feedback about Whirlwind Alligator (the interviewee)

Advance this person to the next round?

How were their technical skills?

3/4

How was their problem solving ability?

3/4

What about their communication ability?

4/4

Good points: 1. The idea of preprocessing. 2. Communication Improvements: 1. Practice more on DP. 2. Give simple definitions/clarifications on the variables (i.e maxAfter/maxAfter2) to make interviewer understand your code correctly. 3. OK to ask for hints after some time (i.e 20 min)

Feedback about Rocket Wind (the interviewer)

Would you want to work with this person?

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

I needed(ish) a second array to solve the problem, and when I came up with a second array they hoped I'd use it the way I needed to, but I had different ideas. It took until the end of the interview before I explained it well enough for them to recognize it was what was needed.

Interview Transcript

Rocket Wind: Hello? Hello? Can you hear me?\nWhirlwind Alligator: Oh, hey, sorry, I need to figure out why my headset is not connected to the speaker.\nRocket Wind: I can hear you. Is it resolved now or not?\nWhirlwind Alligator: Sorry, could you say it again?\nRocket Wind: Yeah, I can hear you. I was wondering if you still have the same issue.\nWhirlwind Alligator: There we go. I think I got my Bluetooth set up.\nRocket Wind: Okay.\nWhirlwind Alligator: Hey, nice to meet you.\nRocket Wind: Hi, nice to meet you. So we have a Google Mock interview. Before doing that, could you set up, like, describe your expectations on this interview?\nWhirlwind Alligator: Yeah, I have an interview coming up on Thursday for a senior engineer job at Google, and I believe that the screening interview is coding in Google Docs.\nRocket Wind: Right.\nWhirlwind Alligator: Whatever we can do to get as close to that as we can, I appreciate.\nRocket Wind: Sure.\nWhirlwind Alligator: Also, just any tips that you can throw in along the way.\nRocket Wind: We can discuss it after our Mock interview. We will have about 20 minutes to discuss that.\nWhirlwind Alligator: Great.\nRocket Wind: Yeah. By the way, do you know your target level? Is it L four or L five?\nWhirlwind Alligator: I believe it's an L five.\nRocket Wind: Okay, cool. By the way, what's your program language?\nWhirlwind Alligator: I'm more comfortable in C sharp.\nRocket Wind: Okay, sure. The reason I'm asking this is about, like I probably need to change the description a little bit for the program language, but it doesn't mean we need to use IDE. You already mentioned we only use Google Doc for Google Interview. I pasted the question. Could you see whether it's clear enough to you?\nWhirlwind Alligator: Yeah. Okay, so find an interesting triplet. So given integer array. An interesting triplet is where zero is less than or equal to I, which is less than J and K, such that okay. So the indexes are in order and also the values are in order. So please check whether array has at least one interesting triplet. Okay, let's see. So the brute force way here is basically just check all the combinations, but then that ends up being about an N cubed.\nRocket Wind: Right.\nWhirlwind Alligator: Question here really is how do we do this efficiently?\nRocket Wind: Yes.\nWhirlwind Alligator: What would I do? So how would I handle this if I was just doing this by hand? Negative two. And then move on until we get something bigger and then something bigger here. But still, this N cubed algorithm, I think I think if I could use a hash map or something like that, maybe go through and store the number of values that are greater or less, maybe just storing. If we go through this, we could have like a minimum after array where we go through this array backward, and the first one doesn't matter. Like, you have five. The minimum after that is three, and then you have one. The minimum after that is you have five. I guess, well, you might compare it to negative one also. So we need a negative minimum that's going to be bigger. Maybe we just need a max. First one would be negative infinity. Second one because that's all there is, negative one plus three and negative two. So looking at three. So then that way we can get it down to an N squared algorithm where when I is negative, pointing at negative two and then we come through and we see negative one is bigger, also three will come later, then we know for sure that there will be a triplet. That should work. Making this is order n that doesn't increase N squared. What do you think? Is there going to be something better than N squared.\nRocket Wind: Max after o n? Sure. I think N squared is acceptable. There's definitely algorithms that are better than N squared, but we can optimize it later if we want.\nWhirlwind Alligator: Sure. So if we have just a Boolean function here called has interesting and we're taking in this array, if the array is null, then return false. If the length is zero, then certainly false. Or just simply puts less than three. Otherwise we can say I starting at zero, it's less than the length and then increasing and then J which is less than length and increase it and then also not. So first before we go in there, we need to make the X after array. So integer array, I guess we might be able to go through do this kind of thing twice where we're looking for something less than the max the second time.\nRocket Wind: Right.\nWhirlwind Alligator: So if you do the max after array or maybe even just to him minimum. Okay, so let's see. So this is going to be an integer array. And so we'll say all of the indexes in the array. We want to start at the end and then go forward. We need some max that we hold for the check the array. So first off, if it's the first one just from the outside here, let's is reader and one that came before, then we want to use that for the new max appear and otherwise we can use let's see if we want to look like that. Otherwise that should create create this array like that. And then we can do is I guess if if we can go through again and we can find a position where the value at i. So here is where this would be true. So the value at I is less than a second value and that would necessarily mean that also less than which is also less than max after. Then we can return. True.\nRocket Wind: Sorry for interruption. First question for the max after, does it include the current i or not? Basically, what's the definition of max after here?\nWhirlwind Alligator: Basically if you're looking forward, then it has the maximum number. Looking forward, I feel like I'm just not going to end up using this last position. But then for like when we're looking here, we know that the maximum that's in this array that comes after is three. And that remains true for all of these because three is the maximum number.\nRocket Wind: So for let me probably let me change the array. I just want to make it clear, right? So if it's something like that, what's the max after value?\nWhirlwind Alligator: So this would start, we can just put something there and here's where the real work comes in. So it would be looking here and here and say, what's the max? And here it would look here and here. Say, what's the max? Five. Here it will look negative one or five.\nRocket Wind: Okay. Basically in the index two, right, you don't put five there. It doesn't include this index. It's just really after that.\nWhirlwind Alligator: Right?\nRocket Wind: Okay. Then I understand.\nWhirlwind Alligator: So it's like a post kind of array rather than a prefix. Then we could use here. I guess this array would return it false. But if we wanted to make that second one, we would just fill in with eight to three. Again here we would say, what is a number that's less than this and is one of these numbers I guess it might make sense to use? Is there something what's the changes? We need to change this too. What is less than this? Less than the true max. So the second highest number, that comes later. So then here basically is again because we're not deep enough. Then here we have new max. We need something that's less than this, but the maximum that's less than those is one of these. So it'd be negative three. And we'd have to make sure that it also comes after this one. Because in this case, the algorithm I was thinking would give an incorrect answer. Negative three or no, this is less for. If this were three, this would be an incorrect answer. Negative one. Three and five looks like a good triplet, but it's out of order.\nRocket Wind: So what are you trying to target? You are trying to target like square or linear?\nWhirlwind Alligator: Linear. I'm trying for order and algorithm here where we would go through the array three times, maybe twice.\nRocket Wind: Sure.\nWhirlwind Alligator: Sounds what?\nRocket Wind: Sounds good to me.\nWhirlwind Alligator: Okay, so then I guess when this changes this value here, then we have to start over. It would be like negative infinity so that we're keeping track of what's less than this. What is the maximum that's less than that? Then as we continue on here, we can say five, build the max. Negative five is equal. So we've got to continue and say negative infinity is less than that. So if this ends up being negative infinity at the end, let's see if that works up here. So we have infinity first two and then this one. Since this one, since this equals this and we're just carrying on. So we're going to have to check. No, this one should work here. This third one saying, is there something that's less than negative three greater than this in here? And there is. So we say negative five, but that fails this check. If negative one is less than negative five. So we continue. So then here, say here's three and here's negative five. So is this one less than three? Yes. Greater than negative five? Yes. And then we check is negative two less than negative one? Yes. And so that means that this is the triple A. So I think this should work. So we've already got this array. So now I think I've got the algorithm down for the second one. So let's go through again. Create here we want this to be mid value and then max up to so we already know that the total length is at least three. So we can go ahead and address the last two as minimum number. And then for this we were looking at is if the array value at plus 10 is less than max value, and if it's greater than the max after two value, then say max after two I equals array value because we're looking at what comes after. So I plus one. So then if that changes, then we also need to check if we have the triple. So if the array at and we already know that max after two is less than max after it, so we don't get checked out, right? So this is the second highest number that follows. So if that fails, I believe we just copy the number. So here, so here, for example, this was not less than this five was not less than the max after value. So we just copied negative infinity. And then here negative one was less than five and greater than negative infinity. So this should be negative one. And that still fails to check two versus negative one.\nRocket Wind: Sorry, question here for the other max after two do you mean to why in line 61, why you loop the arrays in this order? So why is in the like natural order instead of rewards order here, and also I plus one might be out of range, right?\nWhirlwind Alligator: So, yeah, we need this to start at minus three, which is how this one started at minus two because we're Already taking care of these two.\nRocket Wind: Even like this. I mean, the boundary is one question. The other problem is like if you loop in this order, okay, it doesn't work.\nWhirlwind Alligator: And we have to go backward through it. At least that's the way that I was doing. The algorithm.\nRocket Wind: Is larger than max after two, I plus one is smaller than what are the three numbers max after two and max after which one is smaller?\nWhirlwind Alligator: So, for example, we're looking at this position. So array at I plus one is negative five. Is that less than max after of three? And it is and then is negative five also greater than negative infinity? And it is. So then we use the array value for the current position, max after two. That's what this is doing.\nRocket Wind: I mean, could you define max after two? Line 67? I add a line, like I add a comment like max after I basically it is equals to maximum value of array plus one. array plus two, until array minus one. Right. And what's the definition of max after two?\nWhirlwind Alligator: So max after two is a little more complicated. It needs to be, plug in my code where it's not resetting, but it needs to be the second highest, which comes for highest max I is the maximum of these where I is less than source for value of max after i. Does that make sense?\nRocket Wind: Yeah, I'm trying to understand this. So if array plus one is less than max after I plus one, that means that is not the largest value. And if this value is also larger than okay, I understand your point. If it's also louder than that one, this means this one is a new value. So max upper two.\nWhirlwind Alligator: Seems like there could be a loophole here where what if we had the array?\nRocket Wind: By the way, is your code completed? So basically the else part in lie 79 is empty. Right? It's intentional to be empty. Or it's not completed right now.\nWhirlwind Alligator: It's not complete yet. Okay. But if we had the array where it was one, two, three, and here was five, clearly the answer is one, two, three would be the interesting triplet, right?\nRocket Wind: Right.\nWhirlwind Alligator: Would be five, three, three and max after two would be infinity here. So here when we get to one and we should be finding there is a valid instead, we find one is not less than negative infinity and so it fails. So there's a loophole in catching what could possibly be the next triplet here. I'm not sure if I can actually get an order in. It might be that I just need to do like a depth first approach where we create the max after array and then we go through and we say, okay, let's say I is the first value and then we don't really need the depth first. We just go through and it's N squared. Say for I we check. Is J greater than I? Yes. Is max after greater than J or the value at J? And so in this case that would be a no. So then it continues on and says, is J where it's pointing to two greater than i, where it's pointing to one. And that's true. And the max after is greater than J, so that would work. I just feel like I can't nail down the order N algorithm. Instead of all that we would have to go through, we'll have to make another for loop. So J is starting after I. We can get a little fancier with two minus one. So are you still there? Some sort of connection issue?\nRocket Wind: Yes, I'm still there. I can hear you clearly.\nWhirlwind Alligator: If the array at I is less than the array at J and array at J is less than max after at j then return true, and then if we go through that whole thing without finding anything, then we return false. Sure. So that's pretty simple. But is there any way to optimize that?\nRocket Wind: And this is n squared, right?\nWhirlwind Alligator: Right. Yeah, because this is going through half of a square.\nRocket Wind: Right because you have two loops here, right?\nWhirlwind Alligator: Yeah. Is there n log n? Is there n, order n algorithm?\nRocket Wind: Probably. Let's stop here because for a real interview, the effective coding time is more or less the same as this one. We will have like two or three minutes for briefly introduction. And the last two or three minutes, you probably can ask the interview questions. Yeah, that's a real interview, right? I think you already have the basic idea, but what you gave like the max after two is very difficult to maintain, right?\nWhirlwind Alligator: Yeah.\nRocket Wind: Why not do it another direction? Like since you have max after, why not create a min before? And it's similar, like what you need to calculate. Right.\nWhirlwind Alligator: If we have min before, then all we have to do is check. Okay, we can't start at the first one, but we can check at five. Is the min before less? Yes. Is the max after more? No. But then here is the men before less? Yes. Is max after more? Yes. That just works.\nRocket Wind: Basically why you gave the max after solution, it's very fast. I think it's probably only five or ten minutes. And then when you wrote max after two, the definition might be just min before, it might be just a different name. And when you really write the code, I think it's very difficult to maintain that. I thought you were going to the way you like to maintain mean before as well. At that time, it's very difficult to give you hints. Like if I told you it's just like to tell you the solution because the idea is exactly the same, right? The same as max after, right? Yeah, I'm okay to the n square solution for this question, our set up is like for n square solution and linear solution. This is only kind of initial reading. It doesn't mean the final rating. This is probably a hire it also depends on the time, right. The code style. So there are also other factors, but the initial rating might be like hire and weak hire here. And if you solve this question, we probably give you another question. It may relate to this one, like a follow up, and it may be a new question. Basically, there might be another question to try to raise the bar to decide whether we can give you a hire rating, like strong hire or leaning strong hire or whatever. Yeah, let me think about it. Do you want to discuss the solutions for this question? Indeed, it has a very simple linear complexity solution with constant space. With constant space, right. We don't need arrays.\nWhirlwind Alligator: Trying to think because if well.\nRocket Wind: I think I can hint you like there's a I think you already know the DP, the dynamic program algorithm of LIS, which is the longest increasing subsequent problem. And for this question, this is classical dynamic programming. Dynamic or programming algorithm.\nWhirlwind Alligator: I'm thinking if we would start at the first one, say, okay, now we have that's the min before and we start at the last one. We say that's max after that would be just two variables, not arrays. And then we go to the next one and say, okay.\nRocket Wind: You can do something like that. But it might not be two variables. You still need at least one array. Only one of them can be a variable because you need to get the two values at the same time. So you cannot I mean, one of them can be updated during the loop, but not the other one because you cannot get the two values at the same time.\nWhirlwind Alligator: Yeah, I was thinking, you said a constant space, which would mean no, I can give you some raise length in.\nRocket Wind: Anyway if you want, you can search online or I can give you the solution directly, depends on your decision. So for the linear time concept space solution, it's derived from the n log n solution for Dynamic Program for error question, which is calculate the length of the longest increasing subsequent. But our question is very special. Like we only need subsequent. The n log n solution is basically the log n part is the log lens or length of the increasing subsequent, since our subsequent lens is only three or less than three. So the log part is indeed a constant. That's the reason we have another linear time solution. And this solution only saves the last element of the sub sequence okay. Of lens one and two. So we only save two variables. Basically, we only save the last element. Yeah, that's the reason we can have a content space linear time solution. If you want, I can give you more details. Otherwise you can search it online. Try to understand the n log n solution for the LIS problem.\nWhirlwind Alligator: Okay, yeah, I'll look into it.\nRocket Wind: Okay. Then we can discuss other things. So, do you have questions to ask me?\nWhirlwind Alligator: So you said this would probably be good enough to get through the screen, right? Yes. What about the actual interview? Also, do you think Dynamic Program may make up a high percentage of these interview questions from Google?\nRocket Wind: Yes, based on my experience, I think these three categories are very popular in Google search. Typically, I seldom select this kind of category because this is kind of simple. And the second category is DP, which is dynamic problem. The third category is graph. The last two categories are very wide, so everything can be DP, everything can be a graph. And I think for DP it's kind of very tricky. But if you understand that the code is very short. And on the other hand, for the graph, typically the question itself is very straightforward, but the implementation might be longer than a DP question. So typically if we want to evaluate the algorithm or the structure ability, typically we use a DP question. And if we want to evaluate the code or the implementation ability we use a graph question. So these three categories are very popular in Google interview based on my experience.\nWhirlwind Alligator: Okay, yeah, that's good to know. I think dynamic programming might be my weakest subject in there, so I need to practice that.\nRocket Wind: Somebody told me like yesterday I talked to interviewee who told me that I was not very strong, I was weak category on the questions. And I think what the interview means might be a dynamic programming. Talk with him. It seems that everything can be more wider than dynamic programming and yeah, it's very difficult to define a category of array. We probably cannot even call that as a disruptor, just a built in type. So it's very difficult to define which question is related to LIS or not. At least it should contain all the dynamic programming questions. It may even include the graph questions because typically we use two dimensional range. Right. We use linked list or whatever, so raise very wide range. So I think what the interview means might be just a dynamic programming or a more wider category. Yeah. So any other questions?\nWhirlwind Alligator: I don't know, I think I'm pretty good. I mean, I know I need to work on my systems design, but that's outside of the synergy.\nRocket Wind: Yeah, I think that's the special part of our five verify we have a system design interview. Yeah, you still don't have I think.\nWhirlwind Alligator: As far as coding goes, I'm good to go. Thank you for your help.\nRocket Wind: Thank you. No problem. Bye.