Java Interview with an Apple engineer

Watch someone solve the max contiguous subarray problem in an interview with an Apple engineer and see the feedback their interviewer left them. Explore this problem and others in our library of interview replays.

Interview Summary

Problem type

Max contiguous subarray

Interview question

1) Given an integer array nums and two integers left and right, return the number of contiguous non-empty subarrays such that the value of the maximum array element in that subarray is in the range [left, right]. 2) Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.

Interview Feedback

Feedback about Steampunk Dolphin (the interviewee)

Advance this person to the next round?

How were their technical skills?

2/4

How was their problem solving ability?

2/4

What about their communication ability?

3/4

As we discussed, please practice the topics and problems from the notes. Summary feedback: you communication skill is pretty good, you think out loud and if you understand the approach then you are able to communicate clearly and efficiently, but in general I'd recommend you to practice more, as there is some gap in technical skill (lack of knowledge in the fundamental algorithms and data structures, e.g. Backtracking, Topological sort), and as the consequence the problem solving skill (since to be able to find the right solution need to know the fundamentals). And try to use the following script when you approach an interview problem: 1) Understand problem (walk through a few inputs yourself and ask clarifying questions to make sure that you understand the problem) 2) Come up with a brute force approach 3) Evaluate time and space complexity of the approach, and confirm with the interviewer that it's ok 4) Walk the interviewer through the approach, try to write down the steps of the algorithm and how the state will be changing with each step (depending on the problem here you can either have a textual description of the algorithm, or pseudo-code, or just show how the data will change, etc), but make sure that you and the interviewer are on the same page. 5) Code the solution, ideally if the step 4 is done correctly, then you shouldn't get stuck at this step and just code the solution pretty smoothly 6) Test the code manually

Feedback about Mutable Alligator (the interviewer)

Would you want to work with this person?

Yes

How excited would you be to work with them?

4/4

How good were the questions?

4/4

How helpful was your interviewer in guiding you to the solution(s)?

4/4

Thank you for taking the time to give me feedback about where I need to improve.

Interview Transcript

Mutable Alligator: Hello.

Steampunk Dolphin: How are you?

Mutable Alligator: Hi, good. How are you?

Steampunk Dolphin: Good. Is the volume? Okay, can you hear me? Okay?

Mutable Alligator: Yeah, okay. Okay. Can you hear me?

Steampunk Dolphin: Yeah, yeah.

Mutable Alligator: All right. Great. All right. So we are going to have our algorithmic data structure interview sessions, and it lasts for 45 minutes. So yeah, so before we start with this, tell me about your experience and about your goals.

Steampunk Dolphin: Sure, so right now, I'm in school, I'm a master's students, and doing Master's in environmental science and microbiology, I have an undergrad in computer science. And, you know, I decided to do a little bit of research. And so like my, my career plans, my goal plan is, you know, to get a, get a get a job as a programmer in tech, and yeah, I've been studying, preparing myself, you know, brushing up on, you know, the data structures algorithms, and have an interview with Google coming up next week, so, you know, doing the best I can to prepare.

Mutable Alligator: Got it. Okay. Sounds good, all right. So, we will start with me asking you like a real interview question that they usually ask and real interview and then we will see how it goes. So let's start with this one.

Steampunk Dolphin: So, given an integer array nums and two integers left and right, return the number of contiguous non empty sub arrays such that the value or the maximum array element in that sub array is in the range left right. Okay, so, for our first example, we have the numbers we have the array 2143 and left equals two right equals three and the result is three because there are three sub arrays that meet the requirements to two to one and three. Okay, so, let's go to read this again just to make sure that I understand questions asking. So, we have the array and so, two integers left and right and we want to return the number of contiguous non empty sub arrays such that the value of the maximum array element in that sub array is in the range left right. So, because we have left two and right equals three... So, basically we want to select so in in the sample here in the given sample, we want to select the sub array, the sub array such that the maximum array element is between two and three.

Mutable Alligator: Yeah, so basically, basically out of all this sub arrays that we can have 2 2 1 2 1 4 1 4 3 then one, just one and one four, etc, until we get only three. So for each of these sub arrays, we have to consider what is the maximum element here. So example for this sub array is two and we can check that is this maximum element is between this left and right. It is the case then it means that it meets the requirements and we're going to increase some like count of this arrays and so there are like three such sub arrays out of all the sub arrays that we can get from this input, there are three separate requirements. One is to not one is to one and the last one is three.

Steampunk Dolphin: Okay, cool. Okay. Okay, I think I understand. So let's let's see, what are the constraints of this. So what are the possible some I'm assuming left is the lower bound and right is the upper bound? Would we ever have a case where left is greater than or equal to right?

Mutable Alligator: No. Not in this case.

Steampunk Dolphin: So left, lower the left value is always lower. Right. Okay. What are the... Okay, so what size is the number array? Around what size? Is it? Like? I mean, does the size doesn't matter? I guess it could be. It could be large, right? Yeah. Okay. What, what kind of values? Do we have any array? Do we have positive numbers? We have negative numbers?

Mutable Alligator: I mean, we may have, but we can assume that the only positive. Actually, that's that's the only positive numbers.

Steampunk Dolphin: Okay, so only positive numbers now. Okay. So, one thing, something that I was thinking about is that maybe what was something that we can do is we could like maybe go through each element in the array one by one, starting at the first element, the index position zero. And then based, basically, what we can do is for each element, right, we consider as we as we go from left to right, we can we consider all the possible contiguous sub arrays that end at that index, and then maybe that could help somehow. So for example, let's say we start at two. Right? So let's start at two and our very, very first, you know, the starting index zero, we only have a single element that could be formed, which is two and then we check is we got the max element, which is two. And we noticed that two is in the range, right? Because there's between is between two and three, right? So that that counts. So we have two, and then as we move to the right, we grow the array by one. Right, then we have we have two one. And the maximum element here still two so two one also. One thing that also, that's also like I notice is that basically, if as soon as, as soon as we find an element that contains a valid value that's within the range, basically, you can, you can expand. Well, that's not true. I was the standard, I was gonna say if that, um, that you could expand the element. Once you find any element that matches the range, I was gonna say, Oh, well, you can you can just expand it. Right. And but that's not true, because as you expand that, you might hear another element that's greater greater than the match element and that could be out of the range. So brute force I guess brute brute force would be brute force away It would be like consider every possible subarray right. So you could do and every possible subarray and check the elements for brute force or the or you could do is have like a double for loop or double for loop and inside the for loop. We could iterate through the through the selected sub array and then find the maximum element of each.

Mutable Alligator: Okay and what will be like a time complexity of this.

Steampunk Dolphin: Time complexity will be well... Depending on you, at the very least, it would be O(n^2), right? Because, you know, you could you need to have like a sub array. And then once it's like you have, like, let's say if you if you have to build the array every time, every forming every subarray, yeah, that would that would also add to the complexity. I was thinking, like, could we, you know, can we start with a brute force? And I feel that, once we do the brute force approach, maybe I could, I could, like shorting that find, find a workaround.

Mutable Alligator: Okay. That sounds like a good idea. Yeah, we can, can start with a brute force.

Steampunk Dolphin: So, alright, so I'm going to have my function and get sub arrays and then we're going to get on... Sorry, I said, Okay, if I if I do this in Java, yeah. Alright, so I have my function signature. Okay. And what I was thinking is, we have two pointers. So our floor index equals zero. Index... And that's equals zero. And that's less than... And so double for loop, and then inside, or can do is so right index equals index. Subarray. And that's equal. And index plus plus. We can do maximum element equals max value. We're actually this this could be we can look at for loop elements. And then so once we have the maximum element, we check if the max element is within the range. So if max element greater than equal left and max element less than or equal right. And then we could have a vote. All right is long good. So once we once we have said this, we consider every possible sub array. And we can do at the end is return. Okay. So how can we make this better?

Mutable Alligator: Yeah, probably going to make it better. What is the time complexity of this approach?

Steampunk Dolphin: So yeah, so this is so though for loop O(n^2), and this is this is n, so, that would be I think that's, that's even like worked on square. That's O(n^3).

Mutable Alligator: Oh, also. So one more thing is that so here... Are you sure you have to that you need to start from zero here. What? Problem?

Steampunk Dolphin: Sorry, what was the line?

Mutable Alligator: Line 34? I show that it is correct.

Steampunk Dolphin: I'm sorry. Yeah, that is that is a typo. So we should start. Thank you should start off start in that.

Mutable Alligator: Okay. So now we can like, try to make it better?

Steampunk Dolphin: How can we make this better? So go back to our problem. So we want the maximum elements. So within so let's say when we consider every possible sub array, we need to find a way to get the maximum and minimum element right in faster time. So maybe, maybe we can find a way to get it in constant time. Maybe we could have some kind of make use of an auxiliary array to keep track of the maximum values that we see so far. Right? So let's see here. So we have to, I almost almost hit the back button. So we have 2 1 4 3. So basically, what I want to do is every time we consider this, we consider a sub array, let's say we're here, right?

Mutable Alligator: So what if we have something like this where every point we have, we get the maximum array so far? So what when we're to the maximum element is two when we're one, a maximum element is still two, when we are for the maximum element is four, and we were three the maximum element is still four. Okay, so, what if we go to the front of the right, so if we go from the right, maybe this will lead to something if we leave to the right, then the maximum element is three. And this is four when we're here, this is four, this is four. So this is this top element here is the maximum elements of going from the right. This one is this point from running from the left. And this is fun to write this helpful. So let's say just consider considering, let's say if we consider any subarray. The maximum element would be for maximum elements there, too to one. Yeah, I don't see, I don't see how this, how this helps.

Steampunk Dolphin: Yeah, I don't think like this particular thing helps much, because for example, we can also have situation when our input is something like that 12412343. Other, and then you will end up with having a lot of fours. Here, like, you will, or four, four, and four here for the max from the maximum from the left. And the same thing will be from the maximum from Right, right. So basically, you want there's no way for you to count what is the number of separates that meet the requirements in this in this gap between this two fours? So it's probably it's, is there any other way to we can do this is keeping track of the maximum element? Is there any other way?

Mutable Alligator: So yeah, so if this let's say, we go as we go through the array as we so let's say, if we go from left to right, we could, we could keep track of maybe like, use a data structure, maybe like a priority queue to like, store the values as we as we go through. And if we, if we use a priority queue, then we could, we can use the priority queue to always know the maximum element that we have as we are going, right, so as we as we, let's say, this, we're going from left to right, we put the numbers into the priority queue. And then we pull or we take a peek at the the elements, so that this is going to be like a massive, like you're always the maximum element will be at the top and you you can pull you can pull the peak at the queue or looking up or you don't want to pull it to see if the the the maximum element is within the range. And if it is, then right this you count that as a good array. And if it's, if it's not, if it's this, that is not good, right? If if you if, if the if the number that is greater than the range, then you know that that number you it really can be in the array at all right? So there's no contiguous sub array possible. That includes that number. So what you would have to do is basically skip a number and then start over from the from the number after, right so. So basically what I mean is you could have, so, you start at two so that's, that's, that's, that's a good number. That one, so, two, one, the maximum how. They still do. So that's good when you reach 4 is out of the range. So once that happens, right, there's no you can, you can no longer continue trying to grow the array. So you have to stop, stop and basically skip four and continue on from three. Right? And then you can you keep doing that, right?

Steampunk Dolphin: Yeah, the only thing is that, I'm not sure how are we going to make sure that we consider all the possible sub arrays in the priority queue?

Mutable Alligator: Right. So all the all the possible subarrays? So that's how good questions. So how do I get? I mean, sorry? How do I make sure that I consider all the possible subarrays, right? Because as I grow the array, let's think about. So let's see, if you use a left... Could this be used maybe, maybe use this as a sliding sliding window approach? We use the sliding window approach, then we can use the maybe the right pointer index to grow the array. And this we increment the pointer.

Steampunk Dolphin: Okay, so if you don't mind, let's, let's try a different problem for now. And we come back to this problem later. So let me give you a different problem. Yeah, we just went to like, explore the weaknesses, what topics into like, reiterate, one of the topics is array. So this is max arrays problem did just had this was an array problems. Now let's try this one.

Mutable Alligator: Given in pair, so parentheses, write a function to generate all combinations of well formed parentheses. Whoa, okay. Okay, so the goal is we want to, we want to get parentheses, right, we want to return a list of strings. And these strings have to be well formed parentheses. So example, we have n equals three, we return all combinations of all combinations of parentheses to have three pairs. Okay, so I think I've done a similar question to that. It's like the, the things is Cracking the Coding Interview? Question, right? DP? So the way that I'm thinking of doing this, so I've done I've done a question that's similar to this is like, like number of paths, like basically, you have a 2D grid, forgot to what the problem is, and like, you couldn't you can't you can't you, you couldn't go you're like you're, you're on a 2D grid, right, and you and you have the option of going either down or down or right. And you can't cross like the diagonal. Right? And so that problem was was basically equivalent to finding the number of parentheses and the number of possible pairs of parentheses for a given n, right? And this field is similar to those in the sense that we can, we can use that approach also to generate the parentheses. So what I was thinking is you could have so n is three, right? So you could have, you could have eight, eight to the red is really, really meant. The whiteboard is so much easier to add a 2D grid, right, which is dimensioned of n plus one. And basically, the way that I would work is that it lets you start at the upper right, upper upper left corner. And every time you go down, you add a parentheses, you add a left parentheses, and when you go to the right, you add a right parentheses. And basically, what will you would have is a way you could have if a, a bunch of strings or basically string builders containing the the partially formed strings at the end at the bottom, the bottom right, the the bottom right corner, you're going to have the list of all strings that are...

Steampunk Dolphin: Is there a way to do this in a in a recursive manner?

Mutable Alligator: Good question. So recursive way could be...

Steampunk Dolphin: Can just, you can just say, or like Yeah, right.

Mutable Alligator: Recursively could be maybe... So this base case of the recursion could be when you reach n equals zero return an empty string. And when you have an n equals equals one, return a single pair. And then also be done. But basically, you have to consider all other all other possibilities. All other possible sub arrays. So you could, you could build...

Steampunk Dolphin: So you've never mind. Let's write down something simpler for on also recursive. Let's say. Let's say we have a binary tree. Maybe if you saw this on the standard solve, the previous one. Yeah, let's just pretend we have a binary like this. Or five, let's say six, seven, and can be can be printed in this way. 112123445367 basically return the function tree that is given some tree node variable.

Mutable Alligator: Oh, yeah. So that you could you could do a depth. Yeah, yeah. Okay. So you could do a depth first search on it, right. So you, you could, yeah, yeah, we could, yeah, we could do that. Yeah. Okay. Cool. So, so basically, yeah, like so... Okay, so I'm going to... All right, the way that you work here right. So, for three, you can do basically if tree equals null return then do three. Wait, this is a pre order, pre order traversal. So you can do something with the current one, and print tree.

Steampunk Dolphin: Okay, and what if you want to change the order to something like that? Four to 51637?

Mutable Alligator: So 44254 to one, so in order to switch the print line. So, go down the left subtree first, then there's no and then go down the right subtree.

Steampunk Dolphin: Okay, yeah, and what will what will change in the output if we change this one and paste it here? Right, what is it output?

Mutable Alligator: That would be post order post.

Steampunk Dolphin: And what will be the output?

Mutable Alligator: So the output would be so you do prints for four, so be four 5267314 two one. Yep.

Steampunk Dolphin: Okay, that's good. Okay. Me. Let's go to the next topic.

Mutable Alligator: You we use this right for water to dissolve the parentheses in a recursive way we could. We could use recursion, right? It's like traverse traverse? Does this like traversing a depth first? The first, sorry, I can't pronounce that depth first search on the screen. And then you go up to a given depth right word depth equals the number of pairs.

Steampunk Dolphin: Yeah, we can do this. You can. If you want you can do this. Yeah.

Mutable Alligator: What's that? Sorry. Can you hear me? Was that? Yeah.

Steampunk Dolphin: Yeah, I just said that. Yeah, if you want to do this, you can still do this. Yeah. So this parenthesis.

Mutable Alligator: Okay. Yeah, yeah. So. Okay, so we're gonna, we're gonna do it here. Okay, so for parenthesis, so what we're doing is basically we are recursing down a sub tree, right? So. So anytime we go, anytime we go to a left, go down a left node that could that could be represented by we are printing a left parentheses, right? Anytime we go to the right, or we're printing a right parentheses. Would that work? So, first?

Steampunk Dolphin: Yeah, before we start coding this, maybe like describing what is your approach?

Mutable Alligator: Yeah. Okay, so, we we do. So, let's have an example where we have a smaller sub tree. So for example, let's just have 123. Right. So basically, you start at one, and then you go, you go to two. And before, before you go to two, you print a, or you generate a left parentheses. And then once you're done with that, you come back from two, two is a leaf node that has no children, so you're not going to print anything, you go back to one and then go two, three. And when you go to the right, you do generate this, before we dive in, go into the right child, you generate a a right parentheses. So the result of having having this industry 123 it would be... If you have if we have a data structure, you go from one to two, you generate a left, left parenthesis then two to four generate left.

Steampunk Dolphin: But then four is right, this leaf leaf nodes, so you go back to to go to the right. You generate a right five. While you nothing else to do here that go back to one and then three with the right. sets. And then you go back to seven, seven. So that that gently generates one. One pair. So how, how are the other ones generated?

Mutable Alligator: Yeah, I guess you can. You can just brackets right. Going to be just empty, I guess. So basically, yeah, so we will be able to, we're able to generate brackets. Yeah, so it just really depends. You also have one more input parameter is the number of pairs bracketed. And you just need to guess that's exactly kind of like a tree traversal it just rather similar in the similarity between these two problems is that both of them are using like recursive way of traversing, but the you are traversing for the first in the first problem you actually traversing some a fixed kind of tree that is also given. But here you by traversing you actually, you, you pick either you kind of attached a left bracket or a right bracket, and at all the levels of traversal until you reach the end until you reach the length of the string equals to this multiply by two basically, actors have n number of players brackets.

Steampunk Dolphin: Okay, so you so you basically started to root and then you continue every time, every time you go you, you go down into one of the sub trees left or right you append either left or right bracket. And as you do that, so, your the stop condition will be when the length of the string is n times two, right.

Mutable Alligator: So your tree grows continue to grow to gross like, depending on the n, basically.

Steampunk Dolphin: Right. My so the so the concern I have is like let's say if you're you're like going all the way to the all the way to the left, right? For example, if you use keep adding left parentheses, and then you reach you have n by n, but n times two on left. Right, how do you? So how how to check the string that you're appending?

Mutable Alligator: If this is the question you need to do some, you will end up with, let's say if your n equals to three, right, you eventually will end up having something like that. So which is invalid? So you need to do validation.

Steampunk Dolphin: Yeah, okay, so you can just. Yeah, like, yes, that's what I was thinking to keep track of, you know, how many left and right parenthesis, you have just got to make sure that they're, they're the same, you only you only, like, add this, you know, you only save this if this actually asked the correct number of each.

Mutable Alligator: Yeah, so you Yeah, drag. A few ways of doing this. One way is to you, you're going to collect a string, we check if it's valid or not. Another ways, you're actually going to kind of stop collecting, stop collecting open brackets, until you reach the point until you reach like this point, right? There is basically a more optimal way of doing this. Once you reach this, once you're selected picking a bracket for position, what are the positions 0123? Right? Once you know that you have you already have like, all of them are the brackets that you collect before they all are open to pretty much means that now you cannot collect more open brackets, you can only collect closed bracket brackets. So yeah, so this is another way of doing this, which is more optimal. So before we jump into this, I would suggest you to do it as a homework. Maybe you can explore one more topic. Just Yeah. Yeah, let's do this. Yeah, so let's just pretend you have 1234. Kind of sort sorted array. And we want to and we have a target, let's say it's element four, the end they want to return the right most index of this target. Otherwise, the rest of just return minus one how would you do this?

Steampunk Dolphin: So we have we have an array with is the array sorted, sorted, sorted and we have a target. And we got what we want is look for target look for the target and find the right most index of this target is that it says otherwise return minus one. Okay, so I think we can do binary search on this. Right. So we have the target the array sorted, we were looking at first specific target. We could we could use binary search in order to find the right most so this also this is I actually kind of was studying this study and this the other day, right. So. So for for this binary search is, it's not enough to just look for a specific value, right? We're not looking for for, we're looking for the right most targets. So you actually need or we actually need to do is look at have, as you're going through the doing binary search on the target, you're looking at your middle middle element and the one to the right. Right. And then you got to figure out whether, if you found a target if you found a target for right, whether it's you you check whether it's the last one either when you reach the the end of the array when medicals hi or the the target the number two the immediate right is, is it's a different number. Right? So the approach is do you want to be okay with with me, like coding this up?

Mutable Alligator: Yeah, sure.

Steampunk Dolphin: Okay, cool. So okay, so cool. All right. So we want to write most in this of this target if it says otherwise return all thank you. Sorry about that. Otherwise returning a little one. So we have a target then the ABS reports are negative one. Okay, we're going to have our, our low, lower high, low and high and so left, and that's equals equals minus one while equals those who... and what we've got to do is... So we've found mid is the target. So, in that case, we have a couple of things that we need to shop need to check if if we are in the right end of the array. So if mid we return minus one, because definitions as well will be the rightmost element. So if we're not at the end of the array, if not, then we can check the rightmost element that nums net plus one equals not equals target. So that's the other condition where that we need this is the rightmost element. So if it's not, then that means it's not the it's not the right most elements. So. So, okay, if that's not the right most sorry. So if it's not the right most, the right most one target then we need to go towards that. So else left index equals mid. Okay, so that's, that's when the condition when when we actually found a target. So now if we, if we didn't find target, then we do the regular binary search with the left, all right? So if nums mid less than target. So it nums mid is less than target, we need to go to the right. Right, and that's equal. Okay, so now, let's see, do I got this right? That I made sure. This is right, left in this less, right? So let's do... let's debug this. Let's walk through this code. So target is four. So then we have our biggest mistakes. So 1-234-567-8910 1112 1314 1516 1717 elements. So we have left in this equals zero right into this.

Mutable Alligator: So yeah, sorry for interruptions. Yeah, so I think it actually worked. So I just wanted to point on one edge case. Like, if, for example, if we have good work if we have only one element.

Steampunk Dolphin: So sorry. So if we have so yeah, so that's if we have this word, this will not work. So this, this is equal, less than or equal.

Mutable Alligator: Using equal less than and equal to, you know, anything you want. We're can believe. Yes, I have. Yeah, compare with the last one. Yeah, if it is. Yeah, if it is the last one, and because of target, and that's pretty much it, you return. Otherwise, you know, you check if it is actually you've still equals a target, but the next one doesn't take a target. Yeah. chosen means that you found the one that target you otherwise you just go to the right. Okay. Yeah, that's it looks. Yeah, looks correct. Okay. Yeah, so basically, we run out of time, let me just go through some feedback. So the first problem is something I asked in the real interview. Usually it's a position here, software engineer. That's why it's a question. The question is pretty, the problem is pretty challenging. So I would recommend you to practice solving this. problems. Start with me, just give you two. So this one tries to solve this few problems one is that to some, then three sum and four sum, they'll a similar problem problems. Yeah, so basically, and just in your free time, I guess these practice solving more problems on arrays. Arrays, and while this particular problem is pretty challenging it have multiple ways of solving it. And apart from n squared also has an intersection. Yeah, so just do your homework. Now, then. The second thing we were trying to solve probably on recursion was backtracking. So yeah, so try to, to practice the this topic, I would recommend you to. So understand this problem. Yes, it's also a similar problem. It's a DFS class backtracking. Problem. And also another interesting problem to solve is actually a couple of other problems that frequently asked during the interview. This one and and second, try to solve them. Also try to like code. The, the, the solution that you're discussing, let me actually copy copied some code call it here. Yeah, so this, as I finish with the parenthesis, then solve the mystery problems. recursion, because binary is, looks like this. This topic, you know, pretty well, anything you can just like? Like just practice on medium, medium level problems on leetcode on binary tree. topic. Yes, it's often pretty frequently asked on the interview, the interview is, especially at Google. Well, not just in Google, but all the other companies as well. Yeah, so then. So for a binary search, I think, yeah, I think it's pretty good. For for practice, I would also recommend you to solve a very famous problem. So very frequently asked it, so find element number data, sorted array. Which if you heard it is, yeah, yeah. So and then the second thing is you can practice solving the same thing, but for duplicate there is a second version. So we have not a part from this, I would also recommend you to do we like did not talk about any like graph theory, problems. A theory has appeared, talking about if you went when do you have a phone screen, by the way?

Steampunk Dolphin: It's next week.

Mutable Alligator: Next week. Okay. Yeah, so graph theory, I think it's a I would bet that graph theory is something that most frequently asked at Google, they ask a lot of graph problems.

Steampunk Dolphin: Yeah. So, breadth first search depth first search.

Mutable Alligator: They usually... Yeah, they kind of generally the problems that they give is a combination of multiple other problems. For example, if I try to practice this too, so this first one is problem itself includes some DB combination of graph theory plus DB ATP, and this one, room cleaners also like graph theory plus plus some backtracking. interesting problems actually. Yeah. So also, we did not talk about topological sort topic at all. Very logical, logical source. Now, topological sort tiered is I have a problem. Oh, yeah, this one. Core scheduling is also very famous problem. So, practice and learn how to do this sub logical sort sort by how to detect this detect cycles in a directed graph. Yeah, so this project was short supply, learn how to do this. Those like topics are related basically. Yeah, because topological sort, basically. Have you heard of the topological sort?

Steampunk Dolphin: Yeah. Yeah. It's like, you know, well, narrative. So I'm guessing it's like, a way too. Let's, I guess you can use it to sort numbers or like, arrange, arrange nodes in a directed graph?

Mutable Alligator: Yeah, something like that. Basically, it's the, let's say, it's your typical like problem, you have some dependency graph. And you need to, like, for example, dependency graph, you need to, like, print out the way how we're going to traverse this graph. For example, when you do some you feel compile from some projects, right, you have some dependencies there. Like, you have one, let's say your project might require one library, and this library might depend on another library. Right. And it means that, for example, you have a project project that depends on library a, and then library a itself depends on library B. So what means that you need to first... Firstly, you to build the library be pretty much everyone depends on it, right? And then you build a and then only then you start like, within the project, you know, so this is like, problems, this topological source of so this is important. And on the on the, on the other hand, that can be scenario, that project depends on library a, it depends on the know, B depends on. C depends on a again, right? So it means that to build, to build a meaning to build, B, but to build even to build C and but to build C, we need to again, build a so it's like a there's a cycle here. Cycle means like it's an error. Error just means that we cannot like build this project, basically, because we have this cycle of dependencies. The only problem here is that how are we going to detect the cycle? There's an algorithm that is used to detect the cycle basically. So this topological sorting cycle, cycles, detections related topics, basically. Yeah, so just practice this. Yeah, I think that this would be it from from me, I guess, since you have one week left, probably also top 100. We'll go problems from this code. It's also worth like, practicing those as well. Thank you. Any questions?

Steampunk Dolphin: Do you have, like anything? Like feedback, like in terms of like, I guess the communication? Besides? Okay. improve on?

Mutable Alligator: Yeah, in terms of, I guess, like the I would, I would say that the probably. Yeah. For the first thing that you have. So for the first problem, I think that yeah, I think that the most important thing is probably problem solving. Yeah, so you know that there are three categories how we like evaluate here, it's like I want this technical skill. Second thing is problem solving. Third one is communication. Yes, I would say that your communication is pretty good. I think you're pretty openly known communicate. As long as you know how to solve it, you openly communicate and pretty efficiently, you know, but if you don't know how to solve, of course there are communications going to also be like not not like efficient because, like there's nothing to communicate right. You know, And so, so what is technical skill here? Technical skill generally if you know how all this how to you know, by binary search, for example, how to how to do some tree traversal how to do topological sort, you know those technical, technical like kind of data, you know, algorithm fundamental algorithms and data structures, right. And problem solving is when you have when you have some ability to apply this, this data structures and this fundamental arrays and maybe sometimes combine them to solve problems. Right. So, I would say that, you're, you're just like you would, if I were you, I'm sure if you have a chance to postpone this from screen I'm not sure she's ready like strong to scheduled. And if you cannot, like postpone it, but I was recommended, maybe it's practices more or less what I this would be my recommendation those practices a bit more, because array problems is they are pretty frequently asked. Yeah, so, as well as like graph theory, I have not practiced on graph theory, but all the graph theories, not all but all of them. They use a recursive and they are some somehow, like related to backtracking, which was, which was this parenthesis problem, it wasn't backtracking, which is, which is my expectation would be that the candidates will be able to solve it in two minutes, just off the top of their head, basically, because it's a bigger issue for me, like if a candidate is strong, is pretty much a very fundamental problem for this for the recursive and backtracking basically. And so, yeah, so I'm not sure what also level what you're interviewing for at Google. Do you know your level?

Steampunk Dolphin: Yeah, like L3. Yeah.

Mutable Alligator: Yeah, I heard from one friend of mine, who conducts interview with some for like internship, this, he says that it's actually that he finds intern interviews for internships is harder than for other positions, because interns, they don't have much experience yet. And they only they, the only thing they can show or show off is their, like problem solving skill, you know, and the technical. Yeah, he does what he's told me, this friend of mine. Yeah, so I don't know how it's like three days. But I guess it's kind of there is some some Yeah. Kind of makes sense to me. So yeah, I think that think. But just generally, I think, what I just yesterday, I think that this is the this is the script that I usually recommend. I'm going to paste it in below. So this is the kind of script I usually recommend to use when you solve a problem in the interview. Yeah, so I personally 111 97 Yeah. So you're kind of you kind of like under you try to understand the first problem that I asked you Is that you? I think that I had to work intervene to help you have an understanding the problem, maybe it was like, it was kind of okay. To me. But yeah, I think that maybe the petition that candidates will be able to kind of come up with this assertion by himself. Because even though because suboptimal solution and should be pretty, like straightforward, so yeah, and you kind of, you're able, you're able to come up with the brute force, such as just good. And I think that maybe what you could definitely approve is, when you're walking through the approach, you like, tend to, maybe, maybe it's only my perception, but I have a feeling that you tend to kind of jump straight to according before you walk through the approach into your approach and like, you know, understand this approach, and get what confident that's, indeed works and cause good time complexity. Yeah. Yeah, so this is maybe what one thing that you can definitely work on. But as I said before, apart from that, I would recommend you to maybe practice a little bit more just like when when did you start your preparation?

Steampunk Dolphin: Like couple of months ago? Yeah, I haven't, most of the times just like doing going through like the algorithms test book and leetcode. But I haven't done a lot. I haven't done a lot of like, the the, like this, right. The mock interviews, I think, is kind of different. Because sometimes, like, once I'm actually... Oh, like, someone's on the other side, like, my, my mind kind of goes blank sometimes, you know. So it's like, Ah, that's annoying. But that's, I need to I need to practice. I think I need to practice more and be more comfortable, like, you know, doing these interviews to mock interviews.

Mutable Alligator: Yeah, I don't, what is your way of practicing? Generally, it's recommended and what I did myself, I practice by everyday, two hours, for a few months, also participate in different types of contests. You know, and this is like, what really helped me?

Steampunk Dolphin: Oh, thank you. I'm going to try like contest like, those are because those are time, right. Like, yeah, the pressure and stuff. Yeah.

Mutable Alligator: And I also recommend it. Yeah. That answers your question, terms of was that? And the answer to your question, like, initial question was what?

Steampunk Dolphin: Yeah. Thank you so much. Yeah. Yeah, this is great. Thank you. It's a lot of a lot of details. And all of this was really helpful. I think this is good. Thank you so much.

Mutable Alligator: Yeah, you have any more questions?

Steampunk Dolphin: No, I think I'm the practice, you know, like this. I need to practice all this. And, you know, I want to go over that question. I'm gonna like, I'm gonna think about it. The first one. That was an interesting question. I know. You know, there's better solutions, and I'm gonna try to think about that and sort of come up with a solution for home. Yeah.

Mutable Alligator: Yeah, try to come up, try to finish the same square approach that you worked on, you started working on, you started thinking? And then yeah, then start to maybe try to think how we can improve how you can improve to earlier. So solution.

Steampunk Dolphin: Would it be okay to just like, copy and paste these the stuff? The stuff you wrote on? My, my notepad.

Mutable Alligator: I think that you will have access to this. Sure. You don't have to do this. I think you will have access to this. To your to this. Next order not to worry about it. Also. Yeah, so I'm gonna share my contact with you as well. So you can ask me if you have any additional questions you can ask me as well.

Steampunk Dolphin: Oh, thank you. Thank you very much. Appreciate them.

Mutable Alligator: All right. All right. Yeah. That's pretty much it for me.

Steampunk Dolphin: Thank you. You know, like, honestly, this is this is, thank you, you know, very helpful and thank you for taking the time to, you know, give me give me all these discreet advice. Thank you so much, really appreciate it.

Mutable Alligator: Good day and good luck on your interview.

Steampunk Dolphin: Thank you. Thank you. Have a good day.

Mutable Alligator: Thank you. Bye.