Python Interview with an Amazon engineer

Watch someone solve the validate binary search tree problem in an interview with an Amazon engineer and see the feedback their interviewer left them. Explore this problem and others in our library of interview replays.

Interview Summary

Problem type

Validate Binary Search Tree

Interview question

1. Given the root of a binary tree, determine if it is a valid binary search tree (BST). 2. Given an m x n 2D binary grid grid which represents a map of '1's (land) and '0's (water), return the number of islands. 3. Given an array of points where points [i] = [xi, yi] represents a point a home to deliver to and an integer k denoting number of deliveries to make, return the k closest points to the warehouse (1, 3).

Interview Feedback

Feedback about Clandestine Borogove (the interviewee)

Advance this person to the next round?

How were their technical skills?

4/4

How was their problem solving ability?

3/4

What about their communication ability?

4/4

You did a really good job with this interview. You mentioned being at the point where you couldn't code in an interview and spent a lot of time working on it in between interviews and it really showed. If you performed like you did here with the graph questions I would recommend a higher during the debrief. That being said, you mentioned you struggled graphs and really worked on them (which def showed), so I'm curious if I'd see the same data with other types (i.e. the k nearest neighbors question I asked at the end). That's when you really need to focus on your approach to the interview. If other interviews evaluate those areas and think you're doing well as well, then I don't have no doubt that you'll find your next job fast. Great job!

Feedback about Indelible Raven (the interviewer)

Would you want to work with this person?

How excited would you be to work with them?

4/4

How good were the questions?

4/4

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

4/4

Interviewing with Kevin was exactly want I wanted today. His questions were great and feedback was awesome. Kevin gave me good tips on what I need to improve on. I am strong believer in 'room-for-improvement'. Thank you Kevin. I will certainly work on problems other than graphs and trees. Really appreciate your time today.

Interview Transcript

Clandestine Borogove: Hello.\nIndelible Raven: How's it going?\nClandestine Borogove: Hi, good morning. I'm doing well. How are you?\nIndelible Raven: I'm doing alright. Let me turn up my sound one sec. Alright, maybe that will be louder. So, just kind of curious. Can you say something real quick?\nClandestine Borogove: Yeah. Do you hear me all right?\nIndelible Raven: Yeah, that's better cool. Anyway, Hi, I'm Kevin, I am a software engineer at [FAANG Company] and even further I'm an interviewer for [FAANG Company]. This so this is a anonymouse platform, feel free to share as much as or as little as you want. But what I'm curious about are your goals for this interview.\nClandestine Borogove: Sure. My name is [Name]. I recently gave an interview at Microsoft. And I've given Facebook interviews in the past as well. My biggest struggling point was graphs. So they asked me two graph questions. One was a basic depth first search and the other one was count the number of islands in a in a grid, m by n grid. And I struggled with those I did the second question, but I didn't do the first one. So this time, I really focused on graph questions, a lot of practice them a lot. So I would love if you can ask me, you know, some graph questions. And I'd like to test if, if I've prepared well for them.\nIndelible Raven: Yeah, could you give me a second, I'll look up a different one. Because you just told me the one I usually ask.\nClandestine Borogove: Okay. I mean, I don't mind telling you, providing you an answer for the one that you typically like to ask just so because I've struggled with graph. I've struggled with grid questions in the past. And I've seen it's a very common pattern in the interview, so I thought, you know, I need to prepare for these.\nIndelible Raven: Well it's a different one, it's a little more difficult than my typical, I usually ask a number of island problems. But I hopefully have a different one. The problem is it's been a while so I gotta make sure I remember it. Because I was asked it during Google interviews and it's a really I wanted to say fun one, but let's be honest, that one was not fun at all. Cuz, yeah, if you want to dive into while I look at the different one, if you want to dive into the number of island problems, if you want to see if you gets feedback on that.\nClandestine Borogove: Sure. Could you do you mind giving me just a grid?\nIndelible Raven: Yeah, so do you have a coding language which you want to use?\nClandestine Borogove: Oh, yeah, I switched it to Python.\nIndelible Raven: That's not how you do this, I think it's that? Yeah. Yeah, there's a grid for you. Totally made up. But that'll work. By the way, I'll leave about five to 10 minutes at the end. Maybe a little bit longer if you want to ask me any questions, and then also give you some feedback.\nClandestine Borogove: Cool. Thank you. So for grid type questions. First things, let me ask you how many moves that are allowed? Typically, up, down, left and right moves are allowed, but I just want to make sure if that case is acceptable to you?\nIndelible Raven: Yeah, I usually go with up, down, left, right.\nClandestine Borogove: Okay, cool. So what I'm going to do is in this case, typical runtime, optimised runtime would be O of, capital O of n times N where N is the number of rows, m is the number of columns. So what I will do is define, or let me just give you a verbal algorithm first, what I really want to do here is loop over the number of rows and the number of columns, where the number of rows would simply be the length of the grid. And the columns would be just given by the length of grid zero. I'm calling this typical, this grid as grid. And what I want to do is define a visited set where I want to keep a track, if I've previously seen you know, this cell or not. If I've seen the cell, then I don't want to loop over it again. Otherwise, I'll get into the cycle. If not, then I want to also check whether the cell is in bounds, I never want to get out of bounds. And if all of those conditions are satisfied, and I'm assuming another thing I should have asked you, I'm assuming one is land and zero is water. If that's the case, then I don't want to, I only want to count or increment my count, if I have one. And, you know, ignore a cell if it has zero. Does that make sense so far Kevin?\nIndelible Raven: Yep, that works.\nClandestine Borogove: Perfect. All right. So I'll define a function call islands, count islands. And I'll pass it the grid that you just created for me. And I'm going to define, like I said, I'm going to define a visited set, which set gives me O of one, insertion and lookup time. So that is why this is recommended. And I'm going to like I said previously, I loop over the rows and columns. So for r in range of length of grid. And similarly for c in range of the length of grid. But this time, now I'm going to use the zeros column, that's going to give me the number of columns. And here, what I want to do is, I want to call a depth first search in this case. So I'm going to basically, you know, define another function, I'm going to call it explore and pass it grid, the current call the row and column that I have, and then the visited set that I just created, I'm going to leave it open, I'm going to complete this piece of code later. But I'm going to first define what this function does. And this function is a helper function that's going to help me look up basically satisfy the conditions that I spoke to you previously, whether or not I've seen the cell before, or if the cell is in bounds, or if the cell is not water, then only I want to increment my count. So again, passing the grid, the row and column and the visited set that I just defined. So for visited set, what I want to do is I want to define a tuple, which is going to just come contain r and c which is the row and column. And I'm going to say if position in visited, then I don't want to in visited then I don't want to loop over it. So I want to just simply return at this point, then I want to check if this particular cell is in bound or not. So I'm going to just define a variable called row in bounds. And here I want to check. So it should be the r position should be between zero less than or equal to r less than equal to the length of the grid and grid itself, this is acceptable, then I know for sure I'm in bounds for row. Similarly, I want to define column and bounds the same way exact same thing. Zero less than or equal to c less than or equal to the length. But this time, I'm going to use the zero position for the land. So this is going to help me define and stay within the grid that you provided regardless of the size of the grid. And, and I'm now going to use the, I didn't define here. Let me so if I pass this condition, you know that I've not seen the cell before. Then I want to add the cell to my visited set, because I don't want to get into the cycle of going back and forth between the cells. Now I can call\nIndelible Raven: Real quick. These two lines, is that proper Python? I don't really know Python. I'm just checking.\nClandestine Borogove: This is, this is proper Python. Correct.\nIndelible Raven: What does that do?\nClandestine Borogove: So it's checking. So this is like a three way check, it's checking if r is between is greater than or equal to zero and less than length of the grid. And it's going to assign it to row in bounds. And it's going to so if I say if not row in bounds if I say it this way, or not column in bounds then it's going.\nIndelible Raven: Oh so it's a Boolean, except for if it's true.\nClandestine Borogove: Correct.\nIndelible Raven: Okay, that's kind of cool.\nClandestine Borogove: Oh, thank you. Thank you.\nIndelible Raven: Well that's not a, I'm not used to Python. So I'm not used to being able to do that.\nClandestine Borogove: Okay, cool. I'm excited, you just pumped me up a little bit. All right. So if this is the case, if row is not in bounds column is not in bounds or, sorry where am I typing or my grid at this cell of r, r and c if this is equal to water, so if this is equal to zero, then I simply want to return at this point, I don't want to go any further because none of my conditions are satisfied. Now, however, if I still continue, if that's not the case, then I want to, you know, define, call the depth first search. So call this function again, explore and pass the grid again. And I'm going to do up down left and right. So if I go back up here, and you know, maybe start typing here, these are my number of rows, and, you know, in the downward direction in the left part, from here, this is the number of columns. So columns will be, I know I'm not typing right on top, but columns will go from 012, and so forth. Similarly, row will go from 012, and downwards, so this will be 012, and so forth. So if I increase r by one, I'm going downwards. If I decrement, r by one, I'm going upwards. Similarly, the case for columns, I'm going to call the depth for depth first search, and I'm going to call the same function I defined four times and I'm going to say r plus one, r plus one c, and then pass the same visited set that I defined. This is I'm looking in the downward direction, same thing, just going to copy, same thing. For upward, just have to decrement r so this is now looking upwards. And if I do if I call the function one more time, get rid of r plus one, but increment columns. Now I'm looking at the right position and do the same thing one last time, then I am and decrement, the column by one, then I'm looking at the left position. And in this case, if I have called all my functions, I mean my depth first search four times looking in all the directions that I just wrote, If I get to this point, I want to return true at this point. And here just because I wanted to make sure I passed the same datatype in this regards this, this is going to be Boolean. So I want to call, I want to say Boolean false here. If this returns true, then I want to come back here and finish my piece of code here. So if this returns true, if this function returns true for me, then I want to increment the count. So let me just define another variable called count. And if this returns true, then I want to increment my count. And at this point, I just want to return the number of columns. This should give me the number of islands. And yeah, I think I think this is it. This should give me the number of islands in the grid.\nIndelible Raven: So definitely seems like you have worked on this a great job there. A few notes and then I want to move on to a different question. So first one is you don't have to use a visited set. In fact, what I would do is just override the one and make it a zero in the original array, or the original grid. Does that makes sense? As you traverse, we would just change the ones to zero and that's your visited.\nClandestine Borogove: I gotcha. Okay, sure. We can do that way too.\nIndelible Raven: Well, that saves space. So that's a talking point where you could say hey, in order to save some space on the visited node I would, visited grid, I will just change one to zero in the original grid. So that's a good thing to say, Okay, I, that's one thing I recommend, and another one is this is kind of weird, I would just eliminate the returns and then here to say if, if grid at row column is equal to one, then explore and then just add the count. I would personally do that. I think what you had worked, but I like this way better of saying, hey, only traverse down if it's there. Because I'm, you get all the way to here. Before you ever check if it's equal to zero, in here you could just say if it's a thing then traverse. Another thing I would do is I would focus on clean code, writing more readable code. So like using the for row in range and for column in range. And then explorator might make sense. Yeah. Pls. I would do current position I would do visited grid or something. Row and bounce I would choose has to be more readable. Things like that. Using a separate function was great. Glad you did that. Although I'm not really sure how you would do that. You would do it iteratively, if it's a separate function, but good job on that. Yeah, I think it's pretty obvious you practice and these are minor things and I would have asked about it. But yeah, I think you definitely did a lot of work for this. So nice job.\nClandestine Borogove: Thank you. Thank you.\nIndelible Raven: Any quick questions before we move to another question?\nClandestine Borogove: No quick question. But I'm really tempted to clean up my code with your suggestions. Do you mind if I take few minutes to do that?\nIndelible Raven: Oh, we can. Yeah.\nClandestine Borogove: So you asked me to define for more readability. Row and column. That's one.\nIndelible Raven: One note, I would also do real quick. Here instead of grid zero, just for safety sake, I would have done grid row. And same thing down here.\nClandestine Borogove: Gotcha sure.\nIndelible Raven: Yes, thank you if they're different lengths.\nClandestine Borogove: Gotcha. Gotcha. Sure. Makes sense. Makes sense. Thank you. So what you're saying is, define, do this. And you are saying I do all of this code without even coming to this point. So I'm going to, you know, get rid of this piece here. And\nIndelible Raven: Wait go back.\nClandestine Borogove: Sorry.\nIndelible Raven: So you do want to see if it's visited. But the first time around, I would just say here. I would just say okay, my first time just check if it's equal to one. And then every other recursive call you do want to check if it's visit or not.\nClandestine Borogove: I got you, yeah, okay. Okay. Okay. Okay. Cool. So let me just just for the sake of Cool, thank you.\nIndelible Raven: Yeah. And again, these are very minor. These are not things I would say, oh, I'm gonna fail. So and so because this is kind of like, okay, this is not as clean but it's fine.\nClandestine Borogove: Okay, cool. Thank you. Okay, I don't have any more. Yeah,\nIndelible Raven: I think Cool. All right. Yeah, great job. I want to? Let's just use this that way, you can go back later and look at your code if you want. You know what a binary search tree is right?\nClandestine Borogove: Yes.\nIndelible Raven: Okay. This is kind of my step up question. A binary search tree by definition, it says that the top element, or you have a node, its left child is less than or equal to the current node and its right child greater than equal to the current node. That makes sense, right? And then you just find the tree going down and see you'll have something let's see if I can configure something else a five, space that, one, seven get a max in their unnecessary need to put periods. Three, six and eight. That's a binary search tree right?\nClandestine Borogove: That is a binary search tree correct.\nIndelible Raven: Yep. Cool. And then if I change something to this, it would not be a binary search tree, right?\nClandestine Borogove: Correct. Because I have four to the right of five, which is incorrect.\nIndelible Raven: Yep. So what I want you to do is write a function that will validate whether or not a binary search tree is, well a binary tree is a valid binary search tree.\nClandestine Borogove: Okay, cool. So in this case, my approach is going to be basically, obviously define a class that is going to take the input that you have given me. And the approach is going to be to basically come up with a simple list that is going to contain I'm going to go over either with DFS, or BFS go over the entire, you know, the, all the roots, starting from the root to the left and the right child to the left and the right children append to that list and check if the list is in the increasing order. If it is a binary search tree, the list that\nIndelible Raven: Real quick, could you say that again, please?\nClandestine Borogove: Sure. So what I'm trying to do, what I want to do here is I basically do, let's say, an in order traversal. So in order traversal, will be something like this, where I when I loop over, when I go over the tree, then I want to look at the left child first, the root, or the node next, and then the right. So that's what I want to do in for in order traversal. And in this case, order. And in this case, what this will help me do is if I read the tree in this order, and append the values to, to let's say, another list, of course, I'm using space there, but if I append the values to a list, then I should be rendered a list which is in strictly increasing order. If that's not the case, then it's not a binary search tree. If it is the case, then it is a binary search tree. Does that makes sense kevin?\nIndelible Raven: I think so. Yeah.\nClandestine Borogove: Okay, cool. So I'm going to first define a class, that's going to help me take the, get the input that you've defined for me, so I'm going to create an init function here, that's going to continue to take the values, the individual values of the node or the left and the right children. And I'm going to define left as none. And right as none, and self dot val, we're just going to assign the values to them. So self dot val, equals, val, same thing to left and same thing to right. So now I want to define my functions is binary search is the tree that and I'm going to take the node here or the root here at this point. And first things first, I want to check you know, or maybe I will check. If the node is none, then I want to return but I want to check that in a helper function. So let us let me define a helper function to begin with where I'm passing it a new empty list for it to check. So I'm going to define a variable called result and, and another helper function that's going to do the inorder traversal for me, and so past the root itself, and an empty list that I talked to you about which is going to append every single value into it and and I will complete this piece of code once I've finished writing the helper function that will just give me because I've not memorised it to just give me a better idea about what I need to do in order traversal and I want to pass it the the root itself, and then the result of the empty set that I'm passing it and here, first things I want to check if the node is none. Then I want to return at this point, I don't want to go any further. Pardon me not, node, this is the root. And at that, at this point, what I want to do is essentially, do a depth first search and, and call in order traversal, over and over again. So I want to, like I mentioned left root and right, that's the inorder traversal order. So I will call my function again. And I'm going to now call it on root dot left, and pass the result again, because I need to complete function. And then here I want, because now I'm going to be at the root level, I want to then result dot append to, I apologise, result dot append. And then I want to add root dot val, at this point, and do the depth first search one more time on the right child. So root dot write, and pass my result again, and this at the end, I want to return the result that I just created. So this is the helper function that's going to help me define, pardon me help me append all the values that you that you just provided into here. So ideally, what I should be expecting back from the result, let me just write it here. Based on the code that I just wrot. Result should be equal to because it's starting from left, it's going to there's no left child to one. And the root dot val in this case is one. So it should start with one, the next should be root dot right, so right should be three, so three should be appended, then it needs to come back to the top here, and five should be appended. And then it'll come back to the left again. So left is going to be four, and coming back to the node, or node in this case, so seven should be appended. And because there is no right to seven, nothing's going to be appended. This is what I expect from my result. And you can clearly see, based on the logic that I created, I want this result output to be in strictly increasing order. I, if I the moment I see this four less than this five, or any value, the next value less than the previous value, then I don't have a binary search tree at that point. So and now that my helper function is complete, I can go ahead and start a loop over the results that I just created regard without even knowing what the length of the result function should look like. Is it making sense to you, Kevin so far?\nIndelible Raven: Yeah. So you're just you're generating a list of in order values and then I assume you're gonna check the order itself afterwards?\nClandestine Borogove: Yes, yes absolutely.\nIndelible Raven: Okay, I get that I work, we, I get what you're trying to get, it's probably pretty easy to finish that, what if we wanted to do this in place without extra memory.\nClandestine Borogove: Yeah, without extra memory, then in that case, I am looking for, you know, then I want to increase my depth first search in in a different way, I can do it in memory without using an extra space by saying anything to the left should start from, let's say, node, pardon me, the root value should, is allowed to take anything from negative infinity to five. And this next one right here is going to is allowed to take anything from negative infinity but less than the row root itself. Similarly, and so and so on so forth, the the on the left, you are always allowed to take any value as long as as long as you're checking for binary search, you're allowed to take any value from negative negative infinity, only less than the node itself. And similarly for right, you're allowed to take any value for in this at the top level, from from the root itself to infinity, so it's just the opposite. But when you get to this point, you are allowed to take anything greater than the root itself. And all the way to infinity and the same concept is going to continue to the left and the right side. Okay, so if I have to, this is the part that I may not be very good at, I just need to. So if I need to do that, then I want to define, I'm going to still use the depth first search the recursive depth first search that I've defined the function. However, I want to define a variable called maximum and in root in Python, I can define something like this. And minimum, two variables are defined, which is going to let me give the lower edge and the upper edge for the root itself, so when I'm calling the root, then I want to because I'm doing.I want to call the function left, so this should be minimum. And, and then root dot right, I may not be very clear on this one, and this will be the maximum and root dot right, and then root dot left. Some thing like this, but oh I didn't, I didn't call this function here. So in order traversal. To get rid of this and if this returns true, if this returns true, then I should simply return true at this point, I may be a little hazy on this, this concept here.\nIndelible Raven: I'm a little confused by your recursive calls, maybe can you had a, the rest of your function calls here, your parameter. Because you're here you're calling it with three parameters. And here. So what are these parameters?\nClandestine Borogove: Basically, what I'm trying to do here is I'm trying to think if I can come up with. Basically what I want to do, and I know I'm not doing a good job here, I only want to check, starting from the top, I want to check from negative infinity, all the way this root can take anything from negative infinity to whatever value it has. And on the left of it. Anything again from negative infinity, so the lower bound is going to be negative infinity, but the upper bound is going to be defined by what the root value is. So the upper bound must be less than five. Similarly, the right of it, to the right of it is going to be the lower bound is going to be defined by the root itself, which is five, and the upper bound is unbounded. So it's going to be infinity, which is why I define these two values. But I am quite clear on how to implement\nIndelible Raven: So what, when you're calling here. What are you calling? What are the parameters you're trying to do?\nClandestine Borogove: Oh, that's right. I am not. Okay. Yeah, that's not correct. I just realised I need to check I need to check if my left is if the node is less than the right and greater than the left, I need to check on that. So let me fix this part here. Let me just Okay, so let me check right here if root is none, then return. And first things first, I need to check if my node dot val, or root dot val is less than the left no, greater than the left and less than the right. So I'm going to say if not root dot val is greater than, greater than my left. And, and root dot val is less than the right. Then I want to return at this point, or return false. Actually, an empty, an empty tree is also a binary search tree. So I want to return true at this point. So that is that, identifying left and right, so let's define left and right. And then I want to basically check for the condition I talked to you about the lower bounds and the upper bounds. So I want to I'll define another helper function. So let me just get rid of this one here. We don't need this anymore. I'll define another helper function. But let me finish this piece here. So return and call the other helper function, which is, I'm going to call it is BST, that's going to be my helper function. And there, I want to pass the left child than the left itself, and then the value of the node itself. And I want to do the exact same thing for the right side. So I want to call the function again, and do the same thing on the right side. So node dot right. This is going to be node dot val in the middle, and then just write itself. And this should return either true or false. If both are true, then it will return true. If any one of them is false, then it'll return me false. So now let's define the helper function. So is BST. That's my helper function. And this is going to take, no I'm doing of breadth, DFS on this one right here. So that is what I want to do. And I now my this is my helper function itself. And this is my main function where I pass the root itself. And here, I want to call the function. So is binary my helper function, and then I want to pass the three values that I have. So for the left bound, I am going to pass the variable that I defined, which is the previously defined, which is the negative infinity. And for the right bounds, I want to define the variable or without defining a variable just passing the upper limit, which is the infinity. And if this returns true, if this returns true, then return true. Otherwise.\nIndelible Raven: So silly question. Why are you asking if this returns true, then return true or else return false? Instead of just saying return this?\nClandestine Borogove: Yeah, that's a good point. I can make it. Yeah, that's, didn't occur to me. I can just simply say whatever the true value of this function is, return me that value Correct.\nIndelible Raven: Yeah. So I got a question do you understand what is going on here?\nClandestine Borogove: I do.\nIndelible Raven: Okay, just wanted to make sure. I do want to move on to one other question. I think you are getting pretty good with trees and graphs. So I don't want to do one non graph question real quick, see what your thought process is, because this is a lot data structures and algorithms, I want to evaluate your more problem solving? There's a chat in here somewhere? Oh, there it is. Here's the question I have that I get asked, that's a really tough graph question. I recommend taking a look at that on your own. It's not the question I'm gonna ask, but that's a good one that check. So this is going to be an Amazon focused question. Amazon has warehouses all over the world. And the idea is that the local warehouses can deliver to you quickly if they have inventory, of what you ordered, alternatively, is, if you ordered something and everything was in a centralised warehouse, then they'd have to ship it to you via air or travelling across the country. So they solve that by having multiple warehouses. And then from there, a delivery truck will pick up your stuff and serve it to you from the warehouse. So I'm going to indicate where these are by xy coordinates. And I'm also going to give you a list of houses. Probably you live locally, the state or the country or something, but one, two, negative 7, 1 and 3, negative eight, negative two and 0, 2. Right. And the goal of a delivery driver is to pick up a select number of packages, and then say, alright, I'm gonna take these packages to the house. So, what I, the goal of this question is, is to write a function that will, the driver will pass in how many houses they can deliver to, and the goal will be to tell the driver which local house is based on distance to drive to so the shortest distance away now, so for? So in this case, it would tell him one, one and zero, two. Makes sense?\nClandestine Borogove: Yep, it does. It does. Cool. All right. So basically, in this case, what I want to do is to calculate Euclidean distance. So you\nIndelible Raven: Just assume you have that the distance. So you have define. Point one, Point two and then I think this is the thing. Yeah. Yeah. So the Euclidean distance is already there for you. So you don't need to write it.\nClandestine Borogove: How is this Euclidean distance with what you provided me because this is the x and y position of the warehouse, and I have the individual x&y position of the houses, I need to calculate with respect to the warehouse individual houses how far away they are, and I need to sort them once I know the distance, I need to sort them in the decreasing order, decreasing order.\nIndelible Raven: Right so assuming this is the function, it will tell it how to start.\nClandestine Borogove: Right. So once I know how to once I know once I've calculated the Euclidean distance, which is essentially the difference between let me just write just the algorithm here itself. So distance not writing the I'm just writing the pseudocode square root of x one minus x two and then the square of this piece here. Where x one is the house itself, the x value of the house itself x two is the x value of the warehouse. was plus the same thing for the y value. So and the same applies y one and y two same applies to the and you need to close the bracket. So this is going to be going, to give me the distance, the Euclidean distance between the warehouse and individual houses, I can use a heap function to, I can use the heap library in Python to sort this in the increasing order and or decreasing order and pick the shortest length from there. And I can tell the driver, you know, these are the top houses the one one and the 02. These are the closest houses to you with regards to the warehouse, and you can use these two.\nIndelible Raven: Right? Yeah, that makes sense. Okay, I mean, yeah, that makes sense. You want to what else would you do? Not what else would you do? Any other thoughts to that? Before you would start writing code?\nClandestine Borogove: Any other thoughts? Could you give me a hint that I'm missing? If I'm missing something here, please?\nIndelible Raven: Yeah, so I'm curious. Well, well, first of all, it sounds like you're using a heap to keep track of all the elements, right?\nClandestine Borogove: Right.\nIndelible Raven: So are you sorting on a, you're sorting based on the right, are you keep a track of are you doing like a min heap?\nClandestine Borogove: Yes, I'm going to do a min heap, because min is going to give me the minimum at the top. And so it's basically a sort of a tree type structure, which is going to give me the minimum distance at the top and then the farthest at the bottom.\nIndelible Raven: Okay. Do you want to implement that?\nClandestine Borogove: I maybe I did this problem a long time ago. So I may be a little hazy on this one here.\nIndelible Raven: So this question really wasn't about the code anyway. So I wanted to see what your thought process was. I'm curious, overall, I'd say we could probably end the coding portion here, and we can get to feedback. If you're comfortable with that.\nClandestine Borogove: Yeah, of course.\nIndelible Raven: Cool. Can you give me, well, first of all, what did you think how this interview went?\nClandestine Borogove: I think I've come a long way to be honest with you, Kevin. This is my first interview at interviewing.io. Earlier interviews, the interviewer had to help me a lot, I couldn't even code, any problem, they would pose at me. So this is the first time at least I've coded two of the problems in front of you, with minimum help from you. Of course, you've given me hints and stuff like that, but or you've given me suggestions on how to improve the code, but at least I've come to this point where I can, if you pose a question, I can code and I have a thought process around how to approach a problem. I may not like the last one, I didn't code it up for you, but at least I understand what the problem is and I can, I can come up with a thought process for it.\nIndelible Raven: So, real quick can you go over what your thought process usually is for approaching a problem?\nClandestine Borogove: For approaching the problem, I should be, I shouldn't just jump straight into coding I should come up with a with an algorithm to or at least speak out loud. Basically, what my approach would be what my what is it that I am trying to solve for and how am I going to solve for if there are edge cases that I need to be worried about, or concern or need to code for that should be my approach and thought process. So in the in the first problem here, I talked to you about, you know, what should I be watching out for, cells that i've visited before cells should be inbound and not water or what not? And then in the second problem, I talked to you about what a binary search tree is. What should be the the upper and the lower bounds on the left and the right side? And eventually if I keep going deeper into the tree, what should, what should I be looking for and I missed this part while I was talking, then I realised oh, I need to tell you I need to check for left and the right portion of, with regards to the node itself. Similarly, the last one, but that is my thought process around any problem.\nIndelible Raven: Oh, speaking of that one before I forget line 68, I think? No, actually, no, that's right nevermind. Actually, no, that's not so by definition, it should be less than or equal to and greater than equal to right. So I would add equals here. So the value is not greater than or equal to the left and less than or equal to the right. Okay, so the reason I asked that, I'm curious, I was curious what your, your approach to doing a question was? Well, first of all, if you came to the point where you are having a really hard time, writing actual code and needed a lot of heads. First of all, great job, you've come a long way. I'm not really an easy interviewer. I guess it was a little easier in this, but this is really good on how far you've come. So great job and all your prep and all that.\nClandestine Borogove: Thank you.\nIndelible Raven: The I think algorithmically, especially with graphs, we've done a lot of work with that. And I don't think you have a lot of issues writing algorithms and data structures. What I was curious about was the approach and how you tackled it. And here, you just kind of went straight into hey, we're gonna do the Euclidean distance. It might have been along the lines of what I was looking for. I'm going to give you a brief intro, what I typically look for the, requirements and all that. So I start with asking, Do I really know what the question is asking? So this is where you ask clarifying questions to see if you really understand what I'm asking. Additionally, do I understand the output? The expected output? So this is just providing an example to say, hey, in this case, what I expect so in this case I expect this and so on. Right? Okay. And then I move on to edge cases. So, when in this situation, how would you expect it to fail? Or in this situation like my last one? What happens if the number of houses is less than the ones I can deliver to? Or my capability? Or what if it's not? What if there are no houses? What are your what's your expectation that when you get there an exception when you throw, would you have them deliver half empty or would you have them wait and so on. Edge cases is always important, and then you make sure to write those edge cases. Then next one is what algorithm data structures would I use? So this is where you kind of compare and contrast each solution and say, Hey, this is a solution I would use here. Here's the big O notation and space complexity. Here's another one, here's the benefit. This is a step up. And then what are your thoughts so far on these solutions? And I think you were doing that part pretty well. Yeah. And then I would also think about how am I going to test it? So at the end yes, I think well, unit testing and integration tests and things like that. And some would outputs different scenarios and how you would test your algorithms. This approach is amazon has three different interviews. Logical and maintainable, which is can you write clean code, and maintainable code, data structures and algorithms. So that's pretty obvious what that is. And then problem solving is how do you take a, approach a question on how to solve it? How do you say, here's the initial question, here is my approach and then or here's how I'm gunna approach it, I can ask you what it's asking. I can ask to clarify anything. Assumptions I'm going to do? Talk about edge cases are going to tell you exactly how we're going to solve it and why so on.\nClandestine Borogove: Gotcha.\nIndelible Raven: Yeah, that approach is that's, that's the biggest interview. Usually that's the, I don't expect you to write out the algorithm I expect you to use built in libraries. But I expect you to strategically approach it with a structured approach to your interview style. And that's what I was hoping to hear with last one, we're running out of time. And I'm assuming, based on the experience of the first few, you probably would have been pretty good with that. What I think happened I kind of threw you off by saying, hey, assume that distance box, it's already done for you. This so a lot of people get caught up in how to write Euclidean distance that's like college math, or high school math that people haven't seen in years. So I like to just tell people, hey, don't worry about writing out the math formula. Just assume that that part exists. So I think I tripped you up there. And then it kind of went a little bit downhill from there. I think you needed to work through this part to move on to the rest. I don't know if you have any thoughts on that?\nClandestine Borogove: No, I agree. I needed to this, this part was a little rusty for me. I haven't used I heaps in a long time. So yeah, I needed to, I need to spend some time on this part was a little rusty. Yeah, I agree with you and would you mind just for my understanding purposes? What are the edge cases that I need to be conscious of here?\nIndelible Raven: So the biggest one is what happens when houses is null and empty? And the other one is what happens when I have more houses to deliver to? Or sorry, less overall houses than the capable, capability of the truck? So what happens if this was like eleven? And yeah you asked, all right, what would you ask the interviewer alright what is the customer, or what would the delivery truck be expected to do in this case? When you think about the customer's experience, in the event of the edge case here, and this is something like I'd say, Well, what would you think we'd do? Would you want to deliver with half the truck and be less efficient? Or would you'd you want to wait? Would you tell the driver? Hey, let's wait until we have more houses. Another one is when the number of houses is equal to houses? Why bother going through the whole algorithm? If it's just equal? In that case, we just say, hey, if it's equal to number houses just return houses. Because note I didn't ask you to sort I just asked you get the list. So that would save a bunch of time. Yeah. These are the ones I usually look for one thing I got a little confused on is you said, hey, we're gonna sort this and return k right, which makes sense. And then you immediately moved to heaps, which is not sorting. That's a different thing. It works. There was less of a transition there than I expected. Max heap by the way, is the more efficient one that I would ask you to get to. But\nClandestine Borogove: Which one did you say?\nIndelible Raven: Max heap.\nClandestine Borogove: Max heap I see.\nIndelible Raven: If you, it's more efficient if you only keep track of the K lowest elements as you go. So instead of having a list of a heap of size n, you will only have a heap of size k. And then if, if the heap is full, and you would say, alright, if the current elements distance is less than a maximum of a heap, then pop it off and replace it with this one. At the end, you just return the heap element. Yeah, that's the more efficient one. So heaps in that case is the step up, which is great. Yeah. So oh, one thing I like to mention as well, you didn't do it here. I just like to mention it because I see it so many times. One of my questions is implement square root function and what a lot of people like doing is they say, okay, I can't do negative numbers. So if the value is less than zero, I'm going to return negative one and the problem with that is the square root function is expecting and return a value. So you just returned a valid option. When it's an invalid input, right? So you basically tell the user yep, great. We ran this, here's your answer. Usually, I try to tell people, wouldn't you want to throw like an exception? Wouldn't you want to throw like a less than zero exception or something like that? Again, I didn't see any indication that that's what you would have done, I just like to share that general. Hey, I see this a lot. So heads up. Don't do that. Just as a general tip, do you have any questions? I've thrown a little bit of stuff at you. Do you have any questions? Any thoughts on any of this?\nClandestine Borogove: No, I think you gave me some pretty good talking points. And next steps for me to work on, especially the edge cases are yes, I agree. I didn't think about them. I should have asked clarifying questions. That's something I've read over and over again, I mean, whichever book I've read, but when you're in an interview, I have this, you know, just this urgency to just to jump to the problem. And I agree, I need to take a step back and think about the problem, especially about the edge cases. So I'll be more careful of that.\nIndelible Raven: So in that case, and I've recommended this in the past, why don't you create like a interview skeleton. I don't know if that's the right term but you say, here is the order, I'm gonna go through this interview and run the interview just like that you start out. The first thing on your list is? Do I understand the question, let's ask clarifying questions to make sure that I understand what is really being asked. Especially what is really being asked. Most questions have a simpler question. So the square root function, for example, what it's really asking is, can I can I find a value between zero and n? In a sorted list? Okay, great. That's a how do I? How do I do a binary search? For example? Right, so you ask clarifying questions to really understand what it's really looking for and then great, I got that. Let's move to the edge cases next. Let's talk about edge cases. What happens when it fails? What would the customer expect in those cases, and so on? And then just go down the list? Well, you can just virtually you could just pull up a list of stops. So you're gonna go there one at a time. And then go from there. I've even seen someone do this. I told someone this, was to find. What's the first thing I asked? Count number of islands grid. And then they would say, check if grid is not null, call depth first search or hold on so loop through rows. Loop through columns check if this position is an Island, call a depth first search, return count. And then would literally right out in comments in a structured format, exactly what they're gonna do. And then would go back and then just write the code that did exactly that. Most people don't go to that extreme, but it really helped that one person to think about it that way. So when you structure and follow that structure, chances are you're going to have a lot much a lot simpler of a time being able to work through the interview than if you just try to figure out what what direction to go on the go. Prep is your friend here. Yeah, the more prepared you are, the more structured your format is going to be, the better. I like to tell people and I do it myself. The interviewer doesn't run the interview you do as the candidate. If you run it really well and you start in a very structured way and you end in a very structured way you start with clarifying questions, all the way to that list and at the end you, you test your code, the hell, even if you write actually unit tests that really impressed people when I did that. And you say, alright, great, I've done this interview. Do you have any questions on this? And along the way, obviously, hey, I'm gonna about to do this. But before I did you have any questions on the thing I've already said. You're leaving the interview. And that makes the interviewers job so easy. When that happens. They just sit back and watch and have fun. Yeah, so I don't know if that'll help with the jumping right in or following structure, this general advice. Any questions on that?\nClandestine Borogove: No, thank you for this. This is really very helpful. I think you're right. I need to, I need to do exactly what you just wrote from line 95 to 106. That's, that's what needs to happen there. And of course, think about the edge cases.\nIndelible Raven: Yeah, yeah. I again, I think in terms of the graph stuff. I think you did really well. I wish I had a little more time to ask my non graph question. But everything I've seen so far, I think you did great. So if you can do with the other questions in the other data structures and algorithms that you did today with graphs, and I think you're gonna do great on your interviews.\nClandestine Borogove: Cool. Do you mind Kevin, if I have schedule another interview with you?\nIndelible Raven: I'm sure I don't I don't know how that works.\nClandestine Borogove: I think we are allowed to, I think we're allowed to schedule two interviews, but no more than that. So I'm allowed to schedule one more with you.\nIndelible Raven: Okay. Yeah. Sure. I mean, I have to find questions, because usually, this is one of my questions. And I assume you're probably not going to go home and completely ignore it and say, I'm not going to practice this.\nClandestine Borogove: No, absolutely not.\nIndelible Raven: I would be very disappointed if you didn't go home and figure it out.\nClandestine Borogove: I just feel, I did that question a long time ago, and I just need to go and dust it up. That's all I need to do. But\nIndelible Raven: Yeah, so yeah. So for the practice hold on, I'll come up with a couple additional questions that I can work here. I have one. It's kind of a warm up. It's more the logical, maintainable side of things. So it's technically an easy question. But the reason why it's easy is because I want you to be able to go through and actually think of not well think about your approach, but also your readability and maintainability, and things like that. So there's a lot of this is amazon why would anyone ask this question? It's too easy. But the reason we ask is because we want to you to write a clean, maintainable code and think about how it's going to maintained in the future. So that's one of them. So that'll be an easy one. I'm not going to tell you that now. You're going to interview with me again, and I'll ask you a different one.\nClandestine Borogove: Yeah, okay.\nIndelible Raven: By all means, if you want to schedule, I don't know how that works. But I think if there is an option to schedule one with me, and yeah, by all means.\nClandestine Borogove: Okay, cool. Thank you so much for your time today. I really appreciate all the input and feedback that you provided to me, I will definitely work on these. This is something I need to, I need to do not asking clarifying questions is something I've been, a feedback I've provided, I've been provided before, but I needed to first, you know, be I needed to come to a point where I can at least write any piece of code in the past four interviews, I had not done that. The interviewer had to write the code with me. And at least I've gotten to that point. So I definitely call it a progress.\nIndelible Raven: Yeah. And I'm curious that that's because you've been practising graph questions, and I've asked graph questions. I would actually be curious how you how that works out if it wasn't graph. Yeah, and if you got to the point where most questions, you can start writing a lot of code, and that's awesome. That's a great job. I guess that's where other interviewers come in as well. So I would also say just don't strictly focus on graphs. That's why I wanted to start on this last question, but we kind of ran out of time yeah. So make sure that what you did today with graphs you can also do with everything else.\nClandestine Borogove: Yeah, I will. Thank you. I appreciate that.\nIndelible Raven: Cool. Any other questions?\nClandestine Borogove: Would you, you know, as an interviewer, would you or maybe I'm not ready for the next step yet?\nIndelible Raven: Oh what do you mean?\nClandestine Borogove: Like for an on site?\nIndelible Raven: Oh, so would I move you on site? Yeah, based on graph stuff? Yes, sure. In fact, if you did this, so if you did this, and I asked graph questions. And if you've performed this way, I'd actually give you a yes on site. So I would have said, yeah, let's hire. Then again, when it comes to graph questions. In terms of Amazon, that's the data structures and algorithms question I'm less. I'm less focused on how you approach the problem versus can you solve the data structures. Can you, given the question can you come up with a good solution to data structure and all this. And yes, then I would pass. In this case, that was true. You came up with a pretty good solution. I think you were a little rusty with the is binary search tree, but I think you eventually got there was pretty normal help. So yeah, I would have said, let's hire as well. So both moving on site and hire. So I think that was great. If this was problem solving, I would be asking different questions. I don't think I would have said yes, but you might have been really close. I think if you clean up your structure on how you approach interviews, I'd think I'd have a really hard time saying no, I think solving, the way you did is great. Good, clean yeah is pretty good. As long as you can approach it properly, then. Yeah I think you're pretty well set.\nClandestine Borogove: Thank you. Thank you, Kevin. I'm just pardon me. It's, it's just great to hear what you just told me. So thank you.\nIndelible Raven: Yeah I think your prep is working. And I think what you are doing in terms of data structures or in terms of graphs, what works there. I would say keep doing yeah. I it's a great job. Yeah, if you do schedule something with me. I guess we'll tackle the non graphs and see how you do but yeah. Any other questions?\nClandestine Borogove: No, no other questions? Thank you so much.\nIndelible Raven: Cool. Awesome. It was a pleasure talking with you.\nClandestine Borogove: Likewise, thank you for all the feedback you've provided. Kevin, really appreciate it.\nIndelible Raven: Yeah, no problem. Have a great day.\nClandestine Borogove: You too. Thank you.