Python Interview with an Amazon Engineer (Boundary Traversal)

Python Interview with an Amazon engineer

Watch someone solve the boundary traversal binary tree problem in an interview with an Amazon engineer and see the feedback their interviewer left them.

Python interview with an Amazon engineer: Tree boundary problem - YouTube

Interview Summary

Problem type
Boundary Traversal Binary Tree
Interview question
Print the boundaries of a given tree.

Interview Feedback

Feedback about Dystopian Abacus (the interviewee)

Advance this person to the next round?
Yes

How were their technical skills?
4/4

How was their problem solving ability?
4/4

What about their communication ability?
4/4

Discuss couple of other approaches if you can think of them, their tradeoffs

Walkthrough an example after finishing coding, (which you did)

Volunteer to provide space and time complexity

Offer to write unit tests covering various edge cases

Feedback about Rocket Samurai (the interviewer)

Would you want to work with this person?
Yes

How excited would you be to work with them?
3/4

How good were the questions?
3/4

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

Would have liked a little more guidance in the first problem given that the problem description is a little vague but overall was great.

Interview Transcript

Dystopian Abacus: Hello.
Rocket Samurai: Hi.
Dystopian Abacus: Hi, can you hear me?
Rocket Samurai: Yeah, I can hear you.
Dystopian Abacus: Yeah, so can you like briefly tell me about yourself so that I can adjust my interview?
Rocket Samurai: Yeah yeah, so I am just getting back into coding. I was a software engineer, a full stack engineer about two years ago, and then I stopped to move on to a different opportunity that didn't involve anything technical or coding, and now I'm trying to get back into it and, yeah and so I have some interviews set up in the following week and then coming week a few interviews that I'm prepping for and I've done one of these practice interviews and I'm hoping I'm doing a bunch more and I also just picked up Python as a language last week, and I'm trying to, you know, learn that for whiteboarding, because I know it's less verbose. I was doing Java mostly and it was also years ago and so you know, I was like why not just start from scratch and start the language that will be better for the interview process, so I'm using Python right now and yeah, are you familiar with Python?
Dystopian Abacus: Yes, yeah. I mean, I don't code that much in Python, but yeah, I can understand.
Rocket Samurai: Okay, just because I might have syntax questions and stuff as I do this.
Dystopian Abacus: Okay, sure, no problem. Do you want to do like a medium, easy, or a hard problem?
Rocket Samurai: Ah, I mean, I don't want to do an easy one. I'd be interested, I mean, if you have a hard problem, that's interesting, I'm happy failing at it, but like trying to work through it if you want to try that. If I can make some progress on the problem, whatever you think, pick whatever problem you think is good.
Dystopian Abacus: Okay, sure, I guess like we'll start with medium and if you solve it quickly move on to, like if you think you have you can do it pretty easily or quickly, then we can move on to a hard problem. Sounds good?
Rocket Samurai: Yeah, and it will take me a while to code anyway because I'm new to Python, so maybe we should just do the easier yeah.
Dystopian Abacus: Okay, so like if we are given a binary tree, right?
Rocket Samurai: Oh sorry, can I ask one other question? Yeah sure.
Dystopian Abacus: Yeah, do you like actively interview at your company? Can you just give me like a ten second overview of what your background is?
Rocket Samurai: Sure, yeah so at my company, like I used to work for Amazon, but now I'm working for another startup within Walmart and I actively interview, like I've done like 30 or 40 interviews in total and I've also done like maybe like 10 to 15 interviews even on this website as well. Yeah and I've been working in software for like maybe like 10 years minimum.
Dystopian Abacus: Wow yeah, that's a lot. I was only working as a software engineer for like a year and a half. I'm fairly new to all of this, and that was years ago anyway, yeah but yeah, yeah.
Rocket Samurai: Okay, just give me one minute and I'll close the door, one second. Okay, so if you are given a tree, right, let's use that. Right, so this is a tree. Let me adjust it so that it looks somewhat tree-like.
Dystopian Abacus: Yeah, I get it.
Rocket Samurai: So the bottom ones are like every two child goes to one above, right? So it would be s and I are children of d and j and k are children of e, f is a child like this, yeah. That makes sense?
Dystopian Abacus: Yeah, that makes sense. Can you give me a second sorry, hold on?
Rocket Samurai: What is it, sorry?
Dystopian Abacus: Can you just give me give me 30 seconds? I just need a hold on. Okay, sorry about that. Okay yeah okay so we have a tree and each node has been, yeah yeah.
Rocket Samurai: Each node has two children and you can... this is not a balanced tree, and by balance... so it can be that there might be like a few missing nodes here, okay.
Dystopian Abacus: The depth of the left and right nodes are not necessarily the same.
Rocket Samurai: Yeah right, okay. So yeah, so it can be like this and the output I expect here is a b d right, because we are going along the boundary and we want to go along the boundary from left then to the bottom then to all the way to the right, so that's why the output is a b d h i j k n o, right? And I've just put dots inside everything. And then after o, we have g c. Does it makes sense?
Dystopian Abacus: Yeah that makes sense, yeah.
Rocket Samurai: So you're given the node of the tree, root node, and then you're asked to print like the node values at the boundary, yeah.
Dystopian Abacus: I was just thinking just to do a sort of a breadth first traversal of the tree and you know, as you're doing the breadth first traversal of the tree, the first and last nodes that you collect at a given level in the tree are going to be... you can collect them as like in a couple of like arrays and then you can just take that bottom level and you can tack on the initial portion, which would be ABD, and reverse the last portion, GCA, and tack it on at the end, that's what I'm thinking. So you do a breadth first thing, you have a, if you have a whatever, like a queue, what I guess you use for breadth first. I guess for depth first, you just tack it on. You pop it out, you put it in the like, let's say we have three different where we have like.... Oh I can just.... traverse over the first leg of the triangle, I guess, and an array for the last leg of the triangle and equals this... Equals this... and then you have a let's say like BFS after search queue, which will be this. You can just you do an array implementation of this or done implementation whenever, and you push in the top node and you say a, okay. And you put that into the first leg here and you pop this up, and you put in B and C as it's children, and I guess you might need to keep track of the level that you're at because you want to know... so maybe you create like a this character at the end here which would like some none type at the end of the mark, but you're at the end of a given level, and so at this point you pop none and A off, put B C, whatever none at the end, this is not completely formal at this point obviously, um, and you would B in... First put B there and you put C here. And then you continue along with this, pushing, you know, and then. Let's see ABD. For the next one, it would end up being P and G here and at the final left here of the breadth first... And then you would just say okay return. I don't know how you can concatenate arrays in Python.
Rocket Samurai: What are you asking, to do what? Can you hear me?
Dystopian Abacus: Can you hear me?
Rocket Samurai: Yes, yes. You were asking, I mean...?
Dystopian Abacus: This is pseudo code anyway, so I can figure out how to concatenate and then like reverse of last leg. Something along those lines.
Rocket Samurai: So you are saying you would do one BFS traversal of the whole tree? And how do you know when to add elements you visit to the first leg and when to add it to the last leg?
Dystopian Abacus: So first of all, you would add A to the queue. You'd be like okay, so there's nothing at this level. So we're gonna put none in here... or maybe we'll put none here or something. I forget. I feel like I've done this at some point. And then as you pop off the elements in here, once you get to none, you know that you've. You know, you pop off because... Oh no nevermind, nevermind, because you're not popping off, you're taking from the... it's first in first out, so I guess I need to use not some... I guess I can us... I think it's Deque, which is this Python queue implementation, which has the use for that. You would do A and then none or some marker character here to mark the end, and A in this case, it's a special case because it's also in the first and the last leg, but we're just going to consider this based on your example here, we're just going to include this in the first leg, so we're going to just seed this first leg with A at the beginning. And then we're going to, you know, we're going to take A off the front of this, because, you know, we're going to continually just take off the first part of the array and we're going to put its children at the end. I'm going to B and C here. Right, okay? And we're going to see, okay, we see that this character means that we're at the next level, so we're going to pop that off and now we're going to say, okay, we're at the next level, so we increment some where we say, the character following that, B in this case, is going to be added to the first leg and so I guess you kind of need to... yeah, so here would be the first leg and sorry when we would do this, whenever we consume that character, we'll put it right at the end of the current level, and so we'll consume B, which and will put at the end, will append D and E at the end here, and then C, how do we know to put it in the last leg, we'll keep track of like every element and then if we hit this, like a previous element, we'll keep track of some sort of previous element variable and then if we hit a unit marker for the end of our of our level, then we'll add that previous element to the last leg list and when we consume that again, we put this at the ends... or sorry, we put the C, the F G first, and then we put that character at the end and that's how we keep track of levels. Se keep track of the previous element. Yeah and then by the end, we'll just have a populated list of the first leg and last leg and then we'll just yeah, concatenate the three arrays like that.
Rocket Samurai: Sounds good to me. And what about like the case where we have f right, because we also have f in the output? So h i j k f and then n o. Right?
Dystopian Abacus: Right. Yeah. I guess I ignored the f. I thought that it was just a b d h i j k n o, I didn't see the f. That is an oversight. Yeah, um, okay.
Rocket Samurai: Because f at the bottom, so that's why we want to include it.
Dystopian Abacus: Right, well, maybe what I could do instead of doing. So how do I do this and keep track? Maybe I'm thinking a depth first search, sort of um would work better for this actually. Let me think. Because if I do a... let's see... a pre-order traversal where I... let's see. I can just populate this list... Let me see. So I'm going to hit these leaves in sequence if I do a certain depth first search, so I can do a b d. Okay, so I think it's a fairly simple.... Um, it's fairly simple to do to just get the... I can do this in separate... I'm trying to think about how to combine this into one function, but it's easy to just get the leaf nodes in order. I can just do a depth for a search which will hit I first and then it'll hit J and then recurse up back to B, which will then go down to E and J and then K and then I'll go all the way back up to A which will then examine it's right node, which will go to f and then go... so that should get those in order, that's like a simple depth first search, which just checks if a given note is a lead and then appends it to some global list that were looking at and then... You know, separately just kind of traverse the boundary. Yeah I can just separately kind of traverse the boundary.
Rocket Samurai: You mean the left and right boundary?
Dystopian Abacus: Yeah, because I think that it'll be honestly better to do that introducing some complicated logic or some logic into the actual function to check... I feel like it might be more complicated to check actually whether or not we're on the left or we're right leg, we could just do that kind of separately and it would be the same time complexity. Yeah, so maybe I'll just do that. I'm sorry about going down this route. I didn't see the F. I thought that was omitted from... I thought it was just doing like the the triangular sort of like outline of this whole thing, but okay.
Rocket Samurai: That's fine, yeah.
Dystopian Abacus: Okay, so do you mind if I start coding?
Rocket Samurai: So what is your strategy for the bottom one, you said you would use a DFS and then for the left and right, what would you use?
Dystopian Abacus: Again, I would just use a DFS, I would just keep traversing just as left or as route as I possibly can. Yeah that's it, so I just keep on traversing the right node because I think... sorry can I ask, because we need a look at a couple different edge cases here. So if this were, that would not work. If this were N O here, right?
Rocket Samurai: Yeah.
Dystopian Abacus: Okay, let me think. So this would just still be a b d h i j k n o g c a.
Rocket Samurai: Yeah.
Dystopian Abacus: It would be, okay. Let's see, let's just take these away. Let's do something like this. Okay, so this would be a b d h i k g c a again?
Rocket Samurai: It's h i k f g c a because think of it like a rubber band around the tree, like a tight rubber band, which bends around the corners. And you only print like... even rubber band I think is a bad example. I would say like anything which is like a leaf node and outside right? Which doesn't have any.... Let's say like if you look at the left side, right? Those are all part of the boundary right? And I think left and right are pretty simple to reason about, like what is a boundary? For the left side, it is a b d h for the right side it is a c g and for the bottom side it is a little tricky because of these cases right, where you can have one child or no child because it is not balanced, so in this case you'll have h i k f right and then g.
Dystopian Abacus: Oh and and then g, sorry I thought you said f e before and that confused me a little bit. So then yeah, I think my algorithm will work, because I can separately just examine the left and right leg or the first and last leg left and right leg or whatever of the tree and that will get back and then I just need to do a depth for a search to get each of the nodes in order and that should get me there, I think. I can't think of edge cases where that wouldn't get me there. I'm trying to think of... Yeah, let me just try it, let me try it out. I think that should work. Well, let's see, so let's define a function here which is going to say boundary, which is going to take in... so what is the input of this function?
Rocket Samurai: Root node.
Dystopian Abacus: Oh it's just a root node, okay. So, and it's a root node and that like should I define a class here for node or should I just assume that there's an implementation?
Rocket Samurai: For now you can assume that, and then you can write it later if you have time, yeah.
Dystopian Abacus: Okay, so we have a node here. And we want to... Let's see... yeah we want to first process, we just want to check if the first node, so if node.left, if this is a... not node dot left, and not node dot right. Like these leaf nodes will have... yeah this this should work I think. Basically let's say... I mean, I guess we could define this boundary, we can define a like an output array. let's say boundary we do this boundary. Boundary is going to be an array that we're just populating here equals this array and if we get to a point and we're going to define this function, let's just going to be the DFS in here, we're just going to take a node. And we're going to check. Not node dot left and not node dot right, so if it doesn't have any children, then I want to just append it to my boundary, so boundary dot append node. So if this is a leaf node, then I want to append this node to the boundary.
Rocket Samurai: Do you mean by boundary array, do you mean like the overall boundary, or just like the bottom or the right of the left boundary?
Dystopian Abacus: Yeah. This is just the bottom boundaries. I guess I can do floor boundary, okay, yeah and then you know else you need an exam and we want to first examine it's left node and then we want to go to it's right node we want to call the DFS, you know. Let's see, you know, let's actually do this, let's do elif not node dot left. We're going to do something here. Then we want to do DFS on node.left. And we want to boundary.append, we want to return here. It doesn't matter where the return value is. Let's see. So we're saying if there's no left node and no right node associated with this node, and we want to append this node we know it's a leaf node, we want to append this node to our boundary list, or floor boundary and we want to return. Cool. I guess I don't even need this. Actually don't even need a return value in here because I guess there's default return. Cool. So if no dot left, then we call DFS on node.left. Oh yeah, sorry. Yeah, so I feel like this should be, this is a simple enough. I feel like this should give us our floor boundary. And that we want to... let's see. You want to define right because...
Rocket Samurai: Yeah, this makes sense. So because you have completed print boundary right for floor boundary, can you like run through an example, like can you test it out?
Dystopian Abacus: Yeah, do you want me to write out or let's take an example that we wrote down below. Let's do this right here, let's just take a look at this. So in this case, we would get A. Node would come in here. We would say, oh sorry we need to call DFS. The node itself here and we're gonna say, okay, yes, so DFS gets the node. If not node.left, so node.left, the left and right are properties on this node. if it doesn't have node.left and it doesn't have node.right, then we're going to call floor boundary and append a node. We don't want to append it to our floor boundary, that's good, so if node.left, in this case, is b, which is good. It does have node.left and then we call DFS on node.left, which is then the b node is passed into here, which is going to go through the same thing. It has a left and a right node. Cool. Let's see. Yeah and then it will check it's left node. It'll say DFS node.left, in which case that's this d here. d is going to do the same check, it's going to do node.left, DFS, node.left, which is going to be h, which is going to say okay, h in this case, if it doesn't have left and right, which it doesn't in this case, we're going to floor boundary, then append this node good, and then we're going to you know, we're going to check these even though we don't have to, we can just put a return statement in here. And we'll return up to d which is when going to return up to here to line 13, which is then going to check it's node.right, which is going to call DFS on node.right, which is also a leaf node, so that's going to append i to there, which is then going to return, which the function call for the d node is I'm going to return after all of this. And we go back up to b, which now we're up at line 13 for B again and we're going down to it's right node in this case an E. And so E, if not node.left and not node.right, no because it has a node.right.
Rocket Samurai: Do you see a bug on line 10.
Dystopian Abacus: Or boundary dot append. Do you mean node.value is what we want? I was a little bit confused about if you wanted these values in the output array or the the nodes themselves, but I guess we can just do value here yeah.
Rocket Samurai: Can you start with the other one, yeah the left one, not the right one.
Dystopian Abacus: Yeah, so at e, we go down to node.left where it doesn't have node.left in this case, so we go to node.right, we call DFS on node.right.
Rocket Samurai: We are good with this example, you can start with the other function.
Dystopian Abacus: Okay, okay cool. So let's see. So we call DFS on some node here, that's fine and then we want to do a couple more things. We're going to define like right boundary which is going to take a node. And return something. We're also going to define left boundary, which is also just going to take node and it's also going to be something in here. Each of these is going to have a separate array. I guess we could just do these in order where we do the right boundary first, and just have boundary and just append to this boundary here, which would be fine I guess. But let me just do it, let me do it this way first and then I can... it's not that much of an optimization, okay. Okay, so print. Sorry, oh DFS... let's do DFS right. Yeah, that's... Left and we're gonna have.... Do a similar thing here for each of these. And it's just gonna... Let's do left boundary. Left first and then we'll do right. Okay, so we have this in place and this we're gonna check, we're gonna do something similar in here. Um, let's see. Let's do something similar, what we're going to say if not... we're just going to say if node.left, oh so I'm confused. Oh, sorry. Um, yeah, so this might not work. I might have to do a combination of depth first and breadth first, I guess, which kind of sounds annoying, but now I'm thinking you could have a tree where you go a and then b and then maybe d is omitted here, right? Right and so you have this and this, in which case, what would the output be for this?
Rocket Samurai: Uh, it would be a b e k f d c.
Dystopian Abacus: Oh e would be included in it.
Rocket Samurai: Yeah.
Dystopian Abacus: Because I need to do a combination depth first and breadth first, so the depth first thing happened there and the breadth first I need to use the code that I was doing before to get the beginning and end of a given level of the tree, does that makes?
Rocket Samurai: I mean, why do you have to use both, can you give me an example that like why would you use both?
Dystopian Abacus: Let me think. Oh I guess we can just keep on prioritizing going down the left part of the tree and then if we don't go down the left part of the tree, we go down the right and we keep on trying to go left but we go right and I think we'll actually maintain being at the left boundary of the tree, so we can do that I guess, so maybe I won't use the the breadth first. We're gonna first check if there's node.left. I guess now I'm a little confused. What if I had b and then another a b c here.
Rocket Samurai: So I guess you were gonna make if you see a left, you prioritize that, otherwise you go to the right.
Dystopian Abacus: Yeah, I'm just trying to think of just maybe another edge case that I'm not thinking about which is, let's say we had this which is ABC, let's just put whatever j in here. Yeah. And this and j. So in this case, the left side of the tree is going... so the boundary in here is going to be a b c k j l f g
Rocket Samurai: Yeah.
Dystopian Abacus: Okay, okay because then it... okay. Okay, um. Yeah, so we can just prioritize going to the left for the left boundary, if we have to go to the right then we go to the right, and we append the values as we see them. If we can go left and go right, this is the problem... how do we know not to. So if we go to b and then we go to c, which is prioritizing going to the left, we append c to our left boundary and then we go back up to b and then go to e. I guess we then... if we're going to the right...
Rocket Samurai: But why do you have to go back up? When you are going left and then if you don't see anything on the left, then you can just go up or down by going to the right.
Dystopian Abacus: Right, I'm saying I'm going a b c, down to this level. In which case, this doesn't have children. This is just.
Rocket Samurai: So you think, this is...? So in that case, k wouldn't be printed.
Dystopian Abacus: Oh okay, yeah it was more... okay good, never mind. I thought, yeah, we needed to space these out a little bit more, maybe here like that is what I was thinking. Okay, yeah, okay, sorry just to be clear, in this case it would be a b e k j l f g c?
Rocket Samurai: Yup.
Dystopian Abacus: Okay, it wouldn't be... k wouldn't be involved in the left boundary. Yeah because you already printed its child, which is j. So it is not part of the boundary because j is part of the boundary, right? If there was no j, then maybe k, but there is.
Rocket Samurai: It just visually looks like it could be included in the boundary if you were drawing like, you know, if you were just drawing the boundary around, a tight boundary around the whole tree, that's why I was thinking that, but yeah.
Dystopian Abacus: That is like the confusing metaphor. with
Rocket Samurai: Okay, okay so I'll just assume you go left and if you don't go left, you go right and that's fine. Okay, let's see. Yeah, so if node.left in this case, then you want to... well first when you hit a node, you left boundary dot append node.value in this case, okay, and then if node.left, you will call DFS left. Yeah, that's left. And if node.right. DFS left of node dot right, because that's insured to be the left boundary because we have no left of its parent, so we go down to that, we then... okay, so in this case we have a b and we only want a b c in this case, so we go a is at the top. We say left boundary dot append node dot value, which is a. We check if it has a left node, in which case it does, and so we call DFS on its left, and if we call it on its left, we don't want to then call it on it's right, we only want to call it on its right if we don't see anything on the left. I guess we can just do... So if node.left, then we call DFS on its left, which case b would come in here. It would be appended to the left boundary. We would check its left, again which would be C which is good. We would call DFS left on c. We check if it has... we would append c to our left boundary, good. If it has a node.left, which it doesn't, if it doesn't have a node.right, it doesn't. And then we return up the tree, and that's fine and we've printed out the left boundary, does that work if we have... let's just eliminate c for a second and we would want... so in this case we would want a b e k j l f g c, right? Excuse me. Hello?
Dystopian Abacus: Oh sorry, I think I was on mute.
Rocket Samurai: Hello?
Dystopian Abacus: Hello, can you hear me?
Rocket Samurai: Yeah, I can hear you, yeah.
Dystopian Abacus: Okay, so I would think that a b e k j l f g c.
Rocket Samurai: So in this case, we would have a, which would come in node.left, is b. Good. We would go to node.left. Good. Node b does not have a left node, we would go to node.right, which then would be e, which would append e to the left boundary, which we would look at its left node, which is k and in this case... And then oh... so I guess we're going to double up on a couple nodes, so we would just want to check if it's a leaf node in this case, which is going to be this same check here.
Dystopian Abacus: Okay.
Rocket Samurai: We don't want to double up on the leaf. After that, our DFS. Right boundary is pretty similar to this. I know that we can do this with more conditional logic. Like added parameter. We could do one boundary, one left and right boundary function, and then have a parameter which will, you know, dictate right or left but I'm going to do this to make it simple for me right now. If you node.left and node.right, we return, and then we want to do replace this. Here. Good. Append node.value. And we're just going to switch these up, right? Right. Right. Sorry, right if that's right. Then return. And at the end, we want to return. I guess we don't even need to reverse because we can do a post order in this case, which would give us a reverse list I think. So we could do something like this. So then we'd just do right boundary. And I think that might work.
Dystopian Abacus: You're only adding node after your recursion, right okay.
Rocket Samurai: Yeah for the right boundary. And then I'm doing a pre-order traversal for the left boundary and a post order for the right boundary and then I'm just doing a leaf check for the DFS function up here, so yeah, okay. Does that make sense?
Dystopian Abacus: Makes sense. Do you see overlap somewhere? That you might be printing a node twice.
Rocket Samurai: Oh, overlap in terms of the output of the function might be... well the only overlap that I thought was if it's a leaf node, because on my boundary we're going to be... Because g is going to be included in the floor boundary, and so we don't want it also included in the right boundary and we kind of omitted that by checking if it's a leaf node here.
Dystopian Abacus: But there's something else.
Rocket Samurai: Oh, but okay, the first node, just yeah, we don't want a in the final.... Yeah, so I'm going to return this or I'm going to do this and I'm going to pop off the last element. We say this results pop and there you go.
Dystopian Abacus: Okay, cool. Okay looks good to me. What do you think is like the time complexity and space complexity?
Rocket Samurai: How are we defining the input size? Are we defining it as the number of nodes in the tree?
Dystopian Abacus: Yeah.
Rocket Samurai: Well, that's... I mean it's linear in the size of the tree, and that we need to examine each node because, yeah, I don't know a better way of getting the floor boundary besides doing like a full DFS search on this, on the tree, so it's linear in the size of the nodes, in the in the number of nodes in the tree. And then it's yeah, and then the adding on the DFS left and right are just kind of minimal in terms of the whole traversal of the tree, so it's linear in the size of the tree.
Dystopian Abacus: And what about like the space complexity, so that is the time complexity.
Rocket Samurai: Yeah the space complexity I guess would be O(log n), given that we have a call stack, which can at most get to the max depth of the tree, and the max depth of the tree... I guess the max depth of the tree... oh I guess we said this is isn't balanced, so actually it's gonna be linear, it's not gonna be log n, because the worst case situation for this tree is that we have a linked list, you know, and so yeah and so it would be traversing a linked list and having to keep track of the entire linked list in terms of, you know, having a a call stack that is the length of the linked list and so yeah linear for time and linear for space is what I'm thinking.
Dystopian Abacus: Okay and if you were... I think you have already like covered all of the cases, but if like somebody asked you like, how would you like unit test this, what would you do then?
Rocket Samurai: How would I unit test it? I was thinking, how would I unit test? Yeah I would just try to capture all the edge cases, you know, I've written... you know, I would just trying to capture all the potential edge cases and I would also have a unit test that would, you know, generate random binary trees and see that it uh... but yeah, I haven't thought that much about it.
Dystopian Abacus: Basically like you would come up with all the various edge cases you can think of, construct those trees, comparison with expected output, yeah. Okay.
Rocket Samurai: So do you mind, can we maybe talk about the harder, problem because we have 15 minutes?
Dystopian Abacus: Yeah.
Rocket Samurai: Sorry about the misunderstanding, the problems a little confusing.
Dystopian Abacus: Yeah it is. And I think I gave you a bad analogy, the rubber band.
Rocket Samurai: So let's say we have like... have you heard of this problem?
Dystopian Abacus: I probably have heard something... I mean, I would like to... let's talk about it.
Rocket Samurai: Yeah, okay, so you are given like a length is equal to five and you're given prices of different lengths, right? So let's say length one is equal to two dollars. Length two is equal to maybe three. Length three is one dollar. Length four is maybe five. Length five is equal to maybe four, right? So if you're given all the lengths and all the prices, what kind of combination would you cut the cutter rod so that you can sell it for the maximum price overall. Right, so you can cut the rod in this scenario, like you can cut it by just using rod of length one. So if you just have your cuts with rod of length one, you can accomplish total length of five by one plus one plus one plus one, which will give you the total price of ten, right? And then if you do two plus two plus one, that will give you a total price of six, plus two, which is eight. So what is the maximum price you can get from this product by cutting it in a certain configuration right?
Dystopian Abacus: Well, what I'm thinking is that it's just a pretty... it's a pretty simple dynamic programming problem, where I'm just going to take... I'm gonna have... it's gonna be a linear time complexity in that, I'm just gonna recurse and say okay, let's say we have our prices here. So I guess this is like a dictionary that we're given. So I'm gonna say like rod length here and we're gonna get like a prices dictionary in here, right? Okay, and then I'm going to loop through the individual prices of the of the rod and I'm going to recurse and say for... Well let's just do this in pseudo code. So I was gonna loop through and say and for each price in the dictionary, I'm going to keep track of that price, and then recurse and say I want to find the maximum of the rod minus that length that I'm currently at, plus the price that I would get for that length, and then I would also keep track of... I would just memorize, so I would only ever have to catch one of my sub problems once, so I would have this memoization, which is going to have as key values rod lengths and prices, so prices here as values. And the prices would be the max price that you can get for a given rod, given the dictionary of prices that was given in the problem. And so I guess I can even write this up, let's... maybe I'll do that. Let's say we have this memoized cache here, and we have this here. And we want to say for price in prices. You can loop through the keys in a dictionary like that, right?
Rocket Samurai: Yeah. At least in JavaScript you can.
Dystopian Abacus: Okay. I'm gonna check if rod length in memo, then we just want to return that rod length and then for price in prices, we want to get the max of... so let's see. What we want to do is we want to keep track of a max here, let's say max price. I can make this more elegant in Python but I'm not that familiar with Python right now, I'm going to do this pretty simply. So for some max price is... let's say zero in this case, because I don't need negative prices, it's always gonna be prices. So for price in prices, we're going to say max price equals max of max_price and let's see, we want cut rod of rod length. We're not going to the prices, we're going through the rod lengths, so for rod lengths rod length. This is confusing. So for length in prices, because it's the length that we're getting at the keys in here, we're going to do, for length in prices, we're going to do cut rod of length, it's not pretty right now, and I guess we can pass down prices. But we don't need to. Yeah, so let's say... Yeah, can we just imagine that prices was just global here or I could just write a wrapper function around here, so prices just exist out here and then we have this. And I would put this all in like a... I could do a wrapper function, which is like, whatever. And then we have this memo with these prices, which is already here in the scope. We define cut rod here. And cut rod just takes the rod length because we have this prices and scope here and we have this memo cash and scope here. We check if rod length is in memo. If it is, we return prices of rod length. Max price of 0 for length in prices, we want to max price equals max price, so we want to say the current max price and we want cut rod of length minus... Current length rod length minus lengths and plus... prices is the dictionary we call for the prices of other lengths of rod length. And then we want to return max price. We also have a base case that we haven't hit here, which is if rod length is zero, we want to return zero, and if max price is this and we want to add max price to our price cash, so we want to say memo of rod length equals max. Something along those lines. Does this make sense? And then in here in the wrapper function, we want to return cut and rod of rod length.
Rocket Samurai: So you're basically like picking up a particular price and then you are detecting the length for the price and recursing on that, and then you're keeping track of the max price. And memoizing.
Dystopian Abacus: Oh sorry memo, sorry, this is what I want.
Rocket Samurai: Yeah. So but will the memo just have a key of a particular rod length?
Dystopian Abacus: Yeah. So for a given rod length, the return value for that is going to be... the only time that it gets put in the cache is after examining it's possible, you know, examining all possible, you know sub problems underneath, you know. So we're gonna for each thing, we're always gonna call... so this cut rod function is only gonna be called once for each rod length because, you know, we're saving the results of our past function calls on that. And yeah for each rod length, there's going to be a maximum dollar value that you can get from that given rod length. Yeah, something sorry, there's a problem and there's another sorry... if rod length is less than zero, then I want to return like infinity or something.
Rocket Samurai: Will it ever go below zero?
Dystopian Abacus: Yeah, I'm thinking if it gets down to a point... oh no, yeah, it will it will, because it'll get down to a point where maybe my rod length parameter here is two, but it'll go through the prices in here the rod lengths in here and it'll subtract five, it'll say in here, rod length is two on this length, which is five, so we're gonna get negative three as our function and when we when we return that function call, we don't want to incorporate that into our max price calculation here, because that's not a valid solution.
Rocket Samurai: Yeah okay. So in that case, you'll return negative infinity?
Dystopian Abacus: Oh yeah, that's what I meant.
Rocket Samurai: Okay cool, looks good. I think we have like four minutes, you did pretty well for both the problems, do you want any feedback?
Dystopian Abacus: Yeah I would just, let me just say that the time and space complexity is linear for... it's linear for time complexity for this. And it's gonna be..,
Rocket Samurai: It wouldn't be linear because you're comparing all the different possibilities here.
Dystopian Abacus: Oh sorry, because in each of these we're yeah... but so it's gonna be O(n*m), where n is the rod length and then m is the number of rod lengths in our prices dictionary. Yeah, yeah, then it's gonna be... it looks like... linear space complexity because all we're dealing with is the call stack, so it should be... yeah the call stack at max is gonna be the length of the rod, if we just consecutively take one unit length off the rod, so the first call essentially... the first work effectively, the first traversal down the left boundary is gonna be the longest and we're gonna yeah... Okay yeah.
Rocket Samurai: Yeah, sounds good to me. Other than that, everything looks good to me. Only like minor suggestion would be like maybe you should talk about like some kind of unit testing and you should like volunteer to provide like space complexity and time complexity, so that like the interview doesn't have to ask you for it. That gives you like a minor like a sort of like a brownie point because just you provided it on your own. Other than that, you were walking through all the problems as you solved them, so that was a good thing and you were able to solve the problems pretty well, both of them. And it didn't look like... maybe like the print boundary one, there were like some edge cases and you discovered them on your own, as well, so overall it is very good.
Dystopian Abacus: Yeah, okay good. So are there... I also have questions, so I'm just getting started doing this preparation stuff. Are there any resources that you would point to as like...
Rocket Samurai: Everybody goes through LeetCode and Cracking the Coding Interview and if you want, if you had to warm up on like your algorithms, just in case if you want to, I don't think you need to, but if you want to there is a good course on Coursera, Robert Hendrick and that is for algorithms. And then there is one more you must have heard Grokking the Systems Design Interview for design interviews.
Dystopian Abacus: Yeah I had that sent to me by the past, so I've done another one of these interviews and the other guy also sent that to me. But I don't know if... I guess I only have like a year and a half experience and so I've been talking with people and I haven't been doing this for two years anyway, so I may be applying for positions or I am applying for positions that I don't think that I'll be getting many systems design interviews because I'm not going for senior.
Rocket Samurai: Yeah but most of the interviews did have like any big tech, will have at least like one system design.
Dystopian Abacus: Even for relatively junior positions?
Rocket Samurai: Yeah for any tech you have, you have, even with the Amazon I think you have like at least one system design. Sometimes they skip it, but most of the time you have it, so you might as well like to just to be on the safe side and these two resources are great, like whenever you have time I think you should go through them, that will help you a lot.
Dystopian Abacus: Okay, sounds great. You'll give some written feedback too, right? If you... yeah.
Rocket Samurai: I don't know what to write, you did pretty well, so I don't have much feedback anyways. Like only thing I would say like to mention was like volunteer to provide as much information, like also discussed like if you have various approaches to a problem and you don't have time to go to everything, so you might as well just like mention like I could have done it this way, but I did not do it this way because of so and so trade-off, right yeah so that yeah. And if you have like, try to solve the problem like quickly, so that you can solve more problems like you did today, right? So that if they are comparing you with other candidates and if you did solve more problems than them, then obviously you have a better chance at continuing.
Dystopian Abacus: Okay, okay perfect. Yeah, thank you so much.
Rocket Samurai: Yeah, have a good day.
Dystopian Abacus: You too, thank you.