We helped write the sequel to "Cracking the Coding Interview". Read 9 chapters for free
Python Interview with a FAANG engineer
Watch someone solve the unique shapes in a matrix problem in an interview with a FAANG engineer and see the feedback their interviewer left them. Explore this problem and others in our library of interview replays.
Interview Summary
Problem type
Unique Shapes in a Matrix
Interview question
1) Given an array of unique non negative integers, find the smallest non negative integer not present in the array 2) Given a root TreeNode, Verify if a binary tree is a Binary Search Tree
Interview Feedback
Feedback about Laser Rabbit (the interviewee)
Advance this person to the next round?
NoHow were their technical skills?
1/4
How was their problem solving ability?
2/4
What about their communication ability?
3/4
Strengths - Candidate asked about requirements - Was able to break problems down into smaller chunks - Was able to take hints in questions and develop on them - Was able to code things with minimal help - Had rudimentary understanding of space and time complexities Areas of Improvements - Knowledge gap in fundamental topics - Didn't cover edge cases in most questions - Needed hints in a number of cases Advice for Future Interviews - Go through main data structures - stacks,queues,deque etc - Cover main algorithms - Binary Search, Trees, Dynamic Programming etc - Gain a better understanding of space and time complexity Open Notes 11th March, 2024, Coding, 6yoe Asked about what defines a shape Didn’t know about BFS/DFS but was able to break the problem down Moved on to a new question then Array question - Asked about sorting Was able to come up with sorting solution Too many comments Was able to code it out but had a bit of difficulty Missed two edge cases Was able to correct it when pointed out When asked to come up with a map solution, required hints but was able to come up with it Sorted variation Discussed the BST question
Feedback about Digital Avenger (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
All good thank you!
Interview Transcript
Digital Avenger: Yeah. Okay, so before we get started, I'll ask one or two questions. That sort of helps me calibrate the interview a little bit better. Is that okay?
Laser Rabbit: Sure.
Digital Avenger: One thing. Is there anything specific that you're looking for? Is there anything specific like that? Any specific topic or anything like that?
Laser Rabbit: Not really. So I'm about to start the process of hunting for jobs. So what I wanted to do was have this session just as a sort of reality check in terms of where I'm at now so that I can understand how I'm doing now. Then go away for a month and do some leak code and practice and other things and come back after a month and do another one. So just sort of get me warmed up to this whole sort of engineering process.
Digital Avenger: Okay, cool. Yeah, that was going to be my second question. Do you have any specific interviews lined up, like at Amazon, Google or something like that?
Laser Rabbit: No. So most of the companies I'm applying to are finance, so think of like banks and hedge funds, that sort of thing. So that's what I'm targeting.
Digital Avenger: Okay. Yeah. So, like in the spirit of full disclosure, I worked at Amazon, so I can only advise about that process. Maybe a little bit about Google, but nothing else.
Laser Rabbit: That's fine.
Digital Avenger: Okay, we'll get started. First of all, like any specific language you have a preference for? Because I don't particularly mind any, you can select whatever you sure?
Laser Rabbit: I'll do this in Python.
Digital Avenger: Okay. Python. Python three. I've selected Python for you.
Laser Rabbit: Okay.
Digital Avenger: Yeah. So what we'll do is I'll provide a question, go through it, ask me any questions you want, anything you're not clear about, any clarification you need, anything where you have a doubt, ask me anything. Then you sort of come up with an algorithm. We'll go through it. If you both agree on it, you code it out. Makes sense.
Laser Rabbit: Okay, true.
Digital Avenger: We'll do this till around 50, 55 minutes. The last five minutes I like to reserve to sort of highlight some of the salient points I saw throughout the process. Obviously I'll be providing a detailed written feedback post the interview, but generally I like to sort of point out that this is an important point that you should look at. This is an important point you should have for posterity and stuff like that. Okay.
Laser Rabbit: Okay, sure. Cool.
Digital Avenger: So let's. Yeah. Oh, one final thing. And this is something you should expect. Doesn't matter if it's a finance company, it's a tech company, anything like that, expect. Especially given that this is not a video interview. But even in video interviews where you see the interviewer, you see them looking down, you see them looking on a different screen, you hear the sound of their keyboard. Don't get distracted most of the times, and most decent interviews will inform you directly. But even if they don't, they are listening to you. They're just typing it out. Taking notes is a part of most interview processes at most companies. Okay.
Laser Rabbit: Okay.
Digital Avenger: Yeah. So I've pasted the question. Please take a look.
Laser Rabbit: Okay, so I guess my first question is in this context, what is defined as a shape?
Digital Avenger: That's a stan first question. So what we are defining as a shape is a collection of ones joined together so that joining is an important part. Otherwise, each one could be its own independent shape. That's not what we are going with.
Laser Rabbit: Okay, I guess I need to understand the question a bit further because how I'm looking at this, I'm seeing three, but this should provide us with two. Okay, which sets of ones are the shape?
Digital Avenger: Okay, so these two are definitely a shape. You see line 15 and 16, last column. Yes, same with line twelve and 13, last column. These are two shapes and they are the same. They're congruent. That's how we're defining the uniqueness aspect here.
Laser Rabbit: I see. Okay.
Digital Avenger: And then obviously we can come to the first column and the second column shapes, but. Okay, we'll come to that. But first, if you have any other questions on that.
Laser Rabbit: Okay, this matrix, in terms of the algorithm, what's the input that we're checking for? The Unix shape. How would it be inputted to us?
Digital Avenger: Okay, let's not worry about the input a little. Let's park that question for a minute. Okay, you see what the third shape is? This whole first column, it's connected to the second column, row 14, which is connected to row 13, 2nd column, which is connected to this one. So this entire thing is one shape. That's how we have three shapes. Right. And because these two are same, two ones pointed downwards, that's why we have only two unique shapes. Now, as to the question of what form the input will be provided, generally speaking, and in most questions, that is not a big thing. Like, assume the input is generally provided as whatever you want it to be. Because your task is not to receive the input from the user, your task is merely to give out the solution. So in this case, assume you have to write a function where the input is coming as a method parameter in form of a 2D array.
Laser Rabbit: Okay.
Digital Avenger: What are you thinking about? It's generally a good idea to sort of talk out loud. To think out loud. So basically, if you're thinking about something, if you have something coming up in your mind, even if you think it's a long shot or something like that, even if you haven't fleshed out your theory, it's okay to do your spitballing out loud.
Laser Rabbit: Okay, I guess. Okay, so I guess just on a high level, how I'm thinking of this in my head sure would be to go through this 2D array sort of row by row. Okay, so for example, let's look at the first row. We've got one.
Digital Avenger: Yeah.
Laser Rabbit: So what I'd be doing is I check the given row that we're at at the moment, and if I find a one in that row. So how we've got, like, this one here.
Digital Avenger: Yeah.
Laser Rabbit: Then we keep that index, and then we check the row beneath it to see if there's a one in that same index.
Digital Avenger: Okay.
Laser Rabbit: And then if we find another one here, then we'll check the next row to see if there's another one there. But we know there's no one there, so we know that. Okay. These two make a shape. But then I guess the tricky part that I need to figure out how to do is these two ones have a shape, and then these two ones have the same shape as these two ones, so that they'd be the same thing effectively. So how to, I guess, sort of track the uniqueness of them is the next bit that I need to figure out.
Digital Avenger: Right.
Laser Rabbit: I guess maybe I can just get started with the enrollment.
Digital Avenger: Okay. Coding. I don't think it would be the most productive thing right now because we haven't sort of the main thing that you did. You broke down the problem into two separate parts, which was nice, getting a shape and then sort of deduplicating the shape, but getting the shape. I feel we are not in a very strong position to do that yet. For example, I mean, these two are simple shapes, so it's fine. What about this? How would we capture this entire shape?
Laser Rabbit: Yeah. Okay, I see a point.
Digital Avenger: Let me ask this, because I feel like if you're not making too much headway, this question is not one of those where you can. There are some fundamental aspects that you need to know. Given that this entire session is more of a mentorship thing. There are fundamental aspects that you. Algorithms that you need to know before you tackle this kind of question. It's a build up on something that exists. Are you familiar with DSS or DFO?
Laser Rabbit: Yeah, I've come across that before, but. Okay, I take a point.
Digital Avenger: These are two things. And I'll provide a list of things that topics that you should take a deeper look at. So this is something that's required because that's how you capture a shape. Both will work, but they're tied to their reduplication as well. Yeah, point B. These are required. Without this, this question becomes quite difficult. Okay. Yes. Let's progress to a different question. Hang on. Look at this one.
Laser Rabbit: Okay. Given an array...Okay.
Digital Avenger: Do you understand the question?
Laser Rabbit: Yeah, just a question. So in terms, I guess for the context of this question, will the array always be sorted? Excellent.
Digital Avenger: No, I've sorted the array just as an example. But no, there is no guarantee that it will be sorted.
Laser Rabbit: Okay. I think I have some ideas in my head.
Digital Avenger: Sure.
Laser Rabbit: Okay. I think the first thing I would do, the approach I want to take, we need to sort the array. So the first thing I would do would be to one, sort the array first.
Digital Avenger: Okay, sorry, I'll just put on. Oh, that's fine. We are not running anything, so don't worry too much about that.
Laser Rabbit: Okay. Then the second step that I would want to do is I would want to iterate through the array. Right. So let's say we look at the first number, whatever the first number is, we'd want to check if the next element in the array is equal to that number plus one.
Digital Avenger: Okay.
Laser Rabbit: And then keep doing that. And then the first time where we see where current element plus one does not equal the next element, then current element plus one is the answer.
Digital Avenger: Right. That makes sense. So you start with sorting. Then you start at the first number. I'm recapitulating what you just said just to confirm that my understanding is right or did I miss something?
Laser Rabbit: Yeah, sure. So I would want to iterate through each element in the array. And then for each element in the array, I'll check if the next element is equal to the current element plus one.
Digital Avenger: Right. Okay. Why don't we write the code for this one? Doesn't sound overly difficult. Assume most libraries have a sorting function, so you don't really need to implement any of that. Like full confession. I'm not an expert in Python, so I'm not sure what library Python uses for this, but Java has a simple function. I'm assuming Python would also have it. So we can just use that.
Laser Rabbit: Sure. It's usually something like list sort.
Digital Avenger: So let's say.
Laser Rabbit: We have, I'll just put some.
Digital Avenger: This is another thing want to point out. In general, it is expected that you always write a method. So the ask is never to sort of start writing code directly. It's always to write a method that takes most of the input as function parameters. Okay, that's to the general standard.
Laser Rabbit: So first up would be sport. The, and then next step would be to iterate through the list. So let me think, I'll do something like current, make it the index.
Digital Avenger: Okay.
Laser Rabbit: I was trying to think of the way to do this. Okay, we can. Okay, so let's go back to using this example. So I would want to look at index. So this would be indexes 0123, right. Okay, so I'll do something like current element equals our input list index. Makes sense. I was gonna.
Digital Avenger: Don't worry much about the edge cases. First let's write the meat of the logic. We can worry about edge cases overflow later.
Laser Rabbit: Okay, sorry, say that again?
Digital Avenger: I was just saying like if you're worried about maybe index overflow or something like that, or edge cases, I was saying let's not worry about those right now. Let's first write the basic conditions that we need to fulfill. We can worry about those later.
Laser Rabbit: Okay, sure. So the current element we're checking is. What I'm doing is I'm going through each element and then basically seeing if the next element is equal to the current element plus one. And if that's not the case, then we're returning next element, which is basically just the current element plus one. So in this example here, we're checking. So two plus one equals three. So we're checking the next element, but the next element isn't four. So then we return two plus one, effectively, which is three.
Digital Avenger: Okay, makes sense. Works for the base case. Now let's talk a little bit about the edge cases.
Laser Rabbit: Okay, so I guess one of the edge cases could be the list is empty.
Digital Avenger: Okay. I mean those are, sure, those are base edge cases. Like those are input related. Input list is null or empty. Assume those are sorted, like sorted. In a sense, those are taken care of. What other edge cases you feel your solution would fail in?
Laser Rabbit: So I guess another case is. Okay, so we've already determined that they're always going to be non negative, so we don't have to worry about negative numbers.
Digital Avenger: What do you think the answer should be in this case?
Laser Rabbit: In that case, four.
Digital Avenger: Right. And what do you think?
Laser Rabbit: Okay, I see your point. So if, if all the numbers in the array. Okay, so the smallest element would be at the end of the array. Okay, I just need to think of how we can do that. We can do that in the check here. So.
Digital Avenger: If.
Laser Rabbit: Okay, I need to change this check bit. If.
Digital Avenger: We just need to place some conditions. Right. Check completely. Sorry, go ahead.
Laser Rabbit: I was going to say something along the lines of checking if the index is the last available index of the element of the array.
Digital Avenger: Yeah, that's a reasonable check.
Laser Rabbit: Something like f equals length of insert left minus one. Since we've already defined next element here as the current element plus one, so then in this case we'd already have that value. So we can just return that next element value.
Digital Avenger: Right. Okay, this takes care of these two. Now let's talk about another case. What do you think the answer should be in this? You see the input?
Laser Rabbit: I would say either zero or four. But in terms of. Okay, so when we're finding the smallest non negative integer in the array, I was kind of basing it, I was kind of using the baseline as being the first element in the given array. But then I guess for something like this, two, three.
Digital Avenger: It would be zero. Yeah, it's zero. Let's assume there's no baseline. There's nothing like that. So the answer should be zero. So can we accommodate that?
Laser Rabbit: Okay, so it'd be something like current. Okay, but we're going. Okay, so we've gotten the current element. So if current element is not equal to zero, then we zero.
Digital Avenger: Okay. Do you see a problem with this?
Laser Rabbit: We'll keep hitting this outside.
Digital Avenger: Yeah, the first element is zero, but this will run when 2nd, 3rd, 4th element also runs. So at least one of them will be non zero, which will automatically make it return zero. How about we put it outside? Or maybe just add another check here. We only need a certain element to be zero. Right? Which element should be zero?
Laser Rabbit: The first one.
Digital Avenger: Yeah. So why can't we put a check for that as well?
Laser Rabbit: Yeah. Equals input. Actually, if input list first element at zero is not equal to zero, then we return zero. So then that way we're only ever hitting response. If this passes, then we know that the first element is zero.
Digital Avenger: Then we can do the rest of it. Absolutely. That makes sense. Okay, so I think now this has a working code. This is cover edge cases. This covers everything. Okay, before we proceed, what's the space and time complexity of the solution? Are you familiar with the concepts?
Laser Rabbit: Yes, I'm just a bit rusty. So I think in terms of the time complexity. So the worst case scenario is that we have to loop through every element in the list, but it's linear because if we do get to the end of the list, I'll only have a one. So it's directly proportional to the number of elements in the list. So I would say that the time complexity is o of n. Okay. Oh, actually, but I guess that doesn't factor in the time for the sourcing algorithm.
Digital Avenger: Exactly.
Laser Rabbit: Oh God. Okay, so if I would need, okay, so I guess that's a point for me if I'm going to use built in libraries like this to understand, because.
Digital Avenger: This part I'll just point out, in most cases, generally speaking, most library functions also sorted this way. The general expected time complexity is this n login. Okay, Java has this way. I'm reasonably certain Python would also have it this way because you use reliable algorithms and they all sort it and login.
Laser Rabbit: Yeah.
Digital Avenger: So what would be the total complexity of the entire solution?
Laser Rabbit: Um, so I guess we could say it would be o n, log n plus o of n, but I believe on log n is the worst one.
Digital Avenger: Right.
Laser Rabbit: So we would say then this is.
Digital Avenger: On log n. Right, that makes sense. What about space?
Laser Rabbit: Okay, that's something I need to look at. So I mean, I guess the benefit of this is that we're doing this check in place so we're not copying it into a second data structure.
Digital Avenger: Right.
Laser Rabbit: I would say something, I'm not sure of the syntax of it, but I think it would be something like n.
Digital Avenger: Okay. Why assume that input is generally not included in your space complexity issue? Input resides outside. So are you using any extra space? And is that proportional to the length of the input that you've received?
Laser Rabbit: Not really. It's just we've got a couple of variables.
Digital Avenger: Right.
Laser Rabbit: So since we have a couple of variables, but we don't have another full on structure where we're copying, so I guess it would be relatively low.
Digital Avenger: Yeah. Okay, so that's generally called sort of constant. You just generally put o of one.
Laser Rabbit: Okay, got it, thank you.
Digital Avenger: That's constant. Yeah. Okay, so yeah, we've done well here. Let's move on to a bit of a change. So we got time as in login, we got space as of one. In this particular solution, let's say the ask has changed a little. My ask here is, can we do something about the time? We can take more space if required, but I need the time to go down a little. Would it be possible. Um, think of a solution, think of a different solution, or think of a different approach where we could reduce the time even if it takes more space for us.
Laser Rabbit: Okay, so I guess the first thing that comes to the top of my mind is when we were initially looking at the time complexity, I had identified two elements. So the n log n was for the sorting, and then the o of n was for the iteration. And we had identified that n log n is worse. Therefore, we call the time complexity of that n log n. So I guess if we wanted to improve upon the n log n, we would have to explore whether it's possible to do this without sorting, right?
Digital Avenger: Correct. So far, so good.
Laser Rabbit: How can I.
Digital Avenger: How do you do this without sorting? Okay, so think of it in this way. You're almost on track here. Think of it this way. What is sorting helping you do when you are checking whether next element is this or that, what is it helping you accomplish? It's helping you accomplish a check that ascertains whether this particular element is present or not, more or less, and that's why you're doing sorting. Is there something else that can tell you in a much quicker format whether a certain element is present or not?
Laser Rabbit: Okay, so I'm thinking along the lines of using a dictionary or a map.
Digital Avenger: Yeah. How would we use it?
Laser Rabbit: I guess the first thing I would do is I'd create a map and then populate that map with all of the elements in the array. So it would be a set of key value pairs. So the key would be each number in the array. Then the value could just be, I don't know, true or something.
Digital Avenger: Yeah, that's fine. It could be a random thing. Yeah.
Laser Rabbit: And then once we have that map, we can then sort of rapidly check for the existence of certain numbers. So, for example, I could create a loop that runs from zero, and then each iteration of the loop increases the number by one. So we'd have checked for zero. Does the key zero exist in the map? Does the key one exist in the map? Does the key two exist in the map? Until we find the first number that is not existing as a key in the map, that we return that number.
Digital Avenger: Excellent. Yeah, that's it. That's exactly it. We could just use. Are you familiar with sets? Like, we have maps, we also have sets. We also have arrays. Link lists, but yeah, so set, you don't even need to set the value. It's like a map. Okay, values. So in this case, as you said, we only need the keys.
Laser Rabbit: Yeah.
Digital Avenger: Obviously in any actual sense, it makes no difference. And point of fact, in Java, set actually uses a map. So it's a bit of a funny thing there.
Laser Rabbit: Okay, got it.
Digital Avenger: I think you'll be able to code it out because you sort of told the right solution. Okay, let's change the question a little bit more this time.
Laser Rabbit: This one. Okay. I guess if the array is already sorted, then I think we can just stick to the original approach. But then we'd ignore this sorting and then just start checking from zero one. I think I'd do something similar to what I was saying before, where we have. Wait, no, I'm sorry. Let me think about this again.
Digital Avenger: It's not a trick question. You were more or less on track in the beginning.
Laser Rabbit: Yeah, I think it would be similar to this. So we just sort of do like an iteration, like a loop starting at zero. Hello.
Digital Avenger: Yeah, makes sense.
Laser Rabbit: Oh, sorry, something happened to my screen.
Digital Avenger: Oh, sorry. Did it toggle the whiteboard? Do you see a white screen or something? Yeah, go to the bottom left. There should be a toggle whiteboard option. Click on that, please.
Laser Rabbit: Okay, got it.
Digital Avenger: It happens.
Laser Rabbit: Okay, so I was thinking was just, if we can assume that the array is already sorted, then we just do like a standard iteration. So we start at zero. So we just check, does element at index zero equal zero? Then does element at index one equal one? Then the first index where we find that it's not matching, we just return that index.
Digital Avenger: Makes sense. Okay, now what's the time complexity of such a solution?
Laser Rabbit: The worst case scenario of that sort of solution is that we loop through the entire array once, so it will be directly proportional to the size of the array. So it will be linear.
Digital Avenger: So o of n. Okay, good. Now let's type that out for a second. We have an offense solution. Now my ask is, is there any way we can improve on that? Reduce it, basically.
Laser Rabbit: And then reduce the solution that was already of n?
Digital Avenger: Yeah, obviously, I mean of n because we have taken out the sorting. So as you said, it's linear, it's of n. Now the ask is to reduce it from of n.
Laser Rabbit: Okay.
Digital Avenger: I'll ask something here. Are you familiar with binary search?
Laser Rabbit: Um, is that the one where we sort of like half the array each time?
Digital Avenger: Yeah, that's the one.
Laser Rabbit: Okay.
Digital Avenger: So if you're not well acquainted with that, this would be much more difficult.
Laser Rabbit: Yeah.
Digital Avenger: So binary search would help you accomplish that. The main person. The question is what is the main thing that you check to compare? But, yeah. So if you're not familiar with that, this would not be a big thing. Okay, so that takes. Hello, can you hear me? Sorry, I disconnected.
Laser Rabbit: Sorry. I was just thinking about it. Yeah, that makes sense.
Digital Avenger: Okay, give me a second. Let me pull up another problem then.
Laser Rabbit: Okay.
Digital Avenger: I don't have visual for this, so let me just type up the question. This is a pretty standard kind of question, but I feel this is not a bad question to discuss in ten minutes because there are some key points in it I find interesting. Are you familiar with trees at all? Sort of create a quick node class for you as well. So what you should expect in each of your nodes is still giving an error. But yeah, as I said, python is not really language. But yeah, basically you have a tree node valve left, right. Given a root, you are given a root node. The method looks like something like this. You deaf? You employed?
Laser Rabbit: Okay, if I remember correctly, with a binary search tree, for any given node, or the value in any given node, the node left should be less than and the node right should be greater than right. So if we're looking at a particular node, let's say that node has a value of ten, the left node should be something less than ten, and the right node should be something more than ten, and that should exist throughout the entire tree. And if that exists throughout the entire tree, then we have a binary search tree.
Digital Avenger: True. Okay, there is one more issue, and this is something. Nest a little. It means that, let's say the current node is ten. Anything to the left? It's not just that the immediate child to the left should be less than ten. The entirety of the subtree that will spawn on the left side should be less than ten. Okay, same with the right. So obviously analogously, but same with the right. Okay.
Laser Rabbit: I think for this, I imagine we'd be using DFs for this depth first.
Digital Avenger: Okay, sure. Preorder in order, post order. They're all more or less the same. That particular order of traversal is not the main thing that's going to impact our solution.
Laser Rabbit: Okay, sorry, my memory is foggy on BST because I remember it has a bit of a recursive element to it, doesn't it?
Digital Avenger: Yeah. So that's with most trees. So. Okay, let me paint out a tree here. This should be. Yeah, something like this. You start at five, you have three, seven, six and eight, and you are given five. Obviously in most cases, in most three questions, you have to use recursion, because recursion is the easiest way to process all of the data. We could try writing something recursive that calls the same method again and again.
Laser Rabbit: Yeah.
Digital Avenger: Let'S create our own method. So this is the input method that only has root. We may need more things rather than just root right in our recursive method. And we can always call our method from the initial method. So let's create another method where we can vary the number of parameters and stuff.
Laser Rabbit: Okay.
Digital Avenger: For valve. So what are we checking? Val is, I'm assuming the value. So value has to be compared against stuff, right? Yeah, node is fine. We'd also need something else, right. We can come back to obviously and change the method signature. But I'm just asking, we'd need like the entirety of 3143 left sub three has to be less than five. And when you actually go right from three, so it has to be less than five but greater than three. So assume instead of four, we had another subtree here, an entire subtree here around four, four would have been a big subtree. Now in this entire four subtree, every element has to be greater than three but less than five. Right? Because at five you come down, so it has to be less than five. Three you go right, so it has to be greater than three. And this process will keep continuing every time we go down. So we know the constraints at every element, the route that we take to come down, that defines some constraints for us, doesn't it?
Laser Rabbit: Yeah.
Digital Avenger: And we would need that for every node. So we can add that to the message signature as well. Right, the minimum and the maximum between which a particular node should lie.
Laser Rabbit: Yeah.
Digital Avenger: That was right. Minval was right. So what was the issue there? Let's check for current node. If it lies between these two.
Laser Rabbit: Okay, we'd want to call this function again.
Digital Avenger: Now we need to check the others, the entirety of the subtree beneath the current node. Those need to be checked as well. At this point we can call using recursion, right? Are you familiar with the syntax of recursion? Basically call the same function?
Laser Rabbit: Yeah.
Digital Avenger: Simply check kind of like. So you call check again, what values would you call check? How do you check the subtree? You go left and you go right.
Laser Rabbit: Okay, so we'd pass in the node left.
Digital Avenger: Right. Now is it the same min value and max value or is there one value that will change?
Laser Rabbit: No, we've got to change it because now if we're looking at the left, the left always has to be less than its current parent. So the parent of node left is node.
Digital Avenger: Right. So node Val, we want to put the value. What about Max? It's okay if we can't make any reductions about it. We can just put it Max up because you can't really make any deductions about Max. We also need to run this for write.
Laser Rabbit: Yeah.
Digital Avenger: It'S going to be exactly the same, or same as left. Or should we change something?
Laser Rabbit: Oh no. One of them is supposed to be men ones.
Digital Avenger: So everything to the right has to be greater than the current value. So that supplies us the minimum value, right?
Laser Rabbit: Yeah.
Digital Avenger: Yeah, close enough. Give me a second. Manual marks.
Laser Rabbit: Also.
Digital Avenger: We reversed the values, but other than that, yeah, the node valve should be on the other side. In left, you define the maximum value that can be attained. Now, on the other hand, you define the minimum value. Okay, so I would ask the space and time complexities, but especially for trees, they go even more. So can you tell me what the space and time complexity of this would be?
Laser Rabbit: So the time, I feel like it would be something worse than oven because for every node in the tree, we then have to check its left and right nodes. I was going to say something like login or n login.
Digital Avenger: So n login will be greater than n. Anyways. Okay, take a look at the map. So are you checking the entirety of the map? Let's say, sorry, map tree. So in the sense that if this proves false, you don't check the entirety of the subtree at all, you check nothing, you return immediately. But say if it's a perfectly valid binary search tree, there is no issue. Then how many nodes do you end up checking?
Laser Rabbit: Every node in the tree. In the tree.
Digital Avenger: And how many times do you check every node?
Laser Rabbit: Once.
Digital Avenger: Right? We only check each node once. And the worst case, we have to check all the nodes. So if there are n nodes, what would be the time complexity? Right, okay. Yeah. So space is also there. I mean, you'll say that space is constant because we are not using any variables. And you're right so far. So the heap space used would be of one. But the trouble is, recursion is built on stacks, basically method stacks. So anytime you call something, so that method one calls something, which is in method two, method two calls method three, method three calls method four, and method one has not been terminated. They're still ongoing. This builds up a recursion stack. So every language deals with that in a different way. But overall, this stack space is the general term that's used the stack space used in that it comes out to. If it's a balanced tree, it would be login, because the depth that you'd go at any one point is not more than login for a balanced tree. Generally, BSTs, even BSTs, there is no guarantee that they'll be balanced or not. There is a possibility where your binary is nothing more than just a single chain. Five, four, three. Because you keep going down left and that's it.
Laser Rabbit: Yeah.
Digital Avenger: Five, three, one. It's just left. Left, nothing else. Rights are always null. So that's just a single chain. So in those cases it's of n. Okay, I think we are overtime, so I'd like to take a few more minutes to discuss a few things, if that's okay with you. If you're busy, I'll understand.
Laser Rabbit: No, it's fine, it's fine.
Digital Avenger: Okay, so let me go over my notes here a little. Okay. So overall I feel you did reasonably well. You were able to come up with things. When I pointed them out, you were able to think about things. But I feel there is a fundamental lack of knowledge here. There is a gap in the things that you don't know about, which is relevant because no matter how good of a thinker you are, interviews have a time limit. You can't come up with an original solution. Like you can't come up with binary search in 1 hour. Even if you do, you wouldn't have time to implement it properly. Knowing things matter, sir. So if you're just starting out, let me now go above, I'm on line seven or something, come to that. I will write down a few topics that I, how do you do that? Few topics that I feel you should cover in depth. Binary search being one of them. Link list arrays. You're already done, let's go with the queuestacks. But yeah, these are basic data structures. Let me two pointer. These are handy things. Graph VFs, basically DFs. This you can leave for a bit later. Okay. Okay, I'll put this for a later tag. The above one is what you should get cracking on immediately. If you are only vying for quant positions or something like that, I'd suggest dynamic programming should also get upgraded to first group. Yeah, binary search is quite important. Like I have interviewed for Goldman Sachs, I cleared it. I know they ask binary search quite a bit and it's a standard binary search. They even use it for numerical approximation.
Laser Rabbit: Okay.
Digital Avenger: There are questions where you use it to approximate a few things or figure out based on trial and error, rather than actually figuring out from a point of view what value would fit best. You put in a value and see if it would work or not. That's it. What else?
Laser Rabbit: Okay.
Digital Avenger: I'll also give you a link code. I would start with neat code 150. Not the blind 75. Blind 75 is for people who already have a solid grasp on the fundamentals and who are just looking to refresh.
Laser Rabbit: Okay.
Digital Avenger: Refresh as in they want to get back. They want to practice so they have a feel for coding in real time. Again, I feel here we could work a little bit more on building up our foundation. And so that's just my opinion.
Laser Rabbit: Okay.
Digital Avenger: Yeah. So this is, once you have it, go through neat code 150. This should only be done like, after you've studied these topics. I think you can find geeks for geeks problems, problems from lead code. There are books, topics, courses, whatever. There are tons of free resources, so I wouldn't advise paying for anything. Okay. Yeah. What else? There are books I can recommend where you can read up these topics on. Also, neat code also has a list of topics. Practice has a bunch of topics. It's a topic by topic practice. So you get to learn that. Okay, this is a topic I need to read upon. These are some of the practice questions. Yeah, something like that.
Laser Rabbit: Okay, got it.
Digital Avenger: Give me 1 second. Let me just quickly see if there is any specific thing that I want to call out. Backdrop. Yeah. Trees is also one thing I highly.
Laser Rabbit: Recommend.
Digital Avenger: Because the reason I'm recommending trees is because in compositions, et cetera, you don't have to code a lot. So what the expectation is that solution might be a little difficult, but it doesn't involve a lot of coding. And binary search, two pointer entries, these kind of things. They don't really involve a lot of coding. The number of lines that you'll spend in code will be very less.
Laser Rabbit: Okay, got it.
Digital Avenger: But the solution could be a little convoluted. It will be five lines of code overall. That's it. So something like that. Like this BST solution. There is one check, null check. Then there is a check if the current node satisfies the thing. If it doesn't, you just return false. So these are two lines. Then the next three or four lines are just left and right. And you do a simple ampersand and bitwise and that's it. So these things actually come in handy quite a bit. So these in particular, let me put it in order. This is the order that you should go in. These are like not the order you should go in, but this is the importance, order. Okay. Operation like binary search is very important. So it's two pointers and trees. These are highly, highly important.
Laser Rabbit: Yeah.
Digital Avenger: Link list queues. Obviously you should know as well as dynamic programming, but, yeah, FSGFs comes later.
Laser Rabbit: Okay, got it.
Digital Avenger: Okay. I think that's more or less all I have for you. Anything else I can do for you?
Laser Rabbit: No, that's all right. I found the session super useful, so thank you.
Digital Avenger: Okay, sure. Well, good luck.
Laser Rabbit: Thank you.
Digital Avenger: Okay, cool. I'll provide a detailed feedback after this. And yeah, we'll both get the opportunity. So anything you feel I could do better, please don't hesitate. I'm always happy to learn. Okay.
Laser Rabbit: Okay, sure. Thank you.
Digital Avenger: Thank you. 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.
