Spasmodic Awesome: Hi.
Hot Gyro: Hi.
Spasmodic Awesome: Can you hear me?
Hot Gyro: I can hear you. Yes. Can you hear me?
Spasmodic Awesome: Okay, great. Yes, I can hear you. Yeah, so we'll just start off with an anonymous introduction, and then we can go to the interview.
Hot Gyro: Okay.
Spasmodic Awesome: So are you preparing for an interview anytime soon?
Hot Gyro: Yes, I am. I am preparing for an interview. I don't have a timeframe yet, but I have been kind of talking to some recruiters, setting up phone screens and getting ready on my own. So yeah, that's where I'm at. I'm kind of in the early stages.
Spasmodic Awesome: And is it like, how many years of experience do you have?
Hot Gyro: Yes. I would say five or so working. But in terms of interview prep, I think I am very junior at that. If I were to say how many leetcode questions I solved, I think I solved only about 30. And most of them are the easy one. And after I solved 30, I almost already forgot a lot of stuff that I did. So I always always have to review it. And so I'm hoping to get more practice with this platform.
Spasmodic Awesome: So let's start with one of the algorithm questions. So basically, I also have something around 3 years of experience. And yeah, I just, I just started with this platform. So it just came to my calendar to take this interview, and I prepared for it for a while. So I have a question in mind, which involves graphs, and graph traversal. So would you say you're comfortable with that?
Hot Gyro: Let's try it. I'm definitely not very comfortable. But let's try that. Let's see how this goes.
Spasmodic Awesome: Yeah. So yeah. Please choose your most comfortable language, and then we can go ahead and add the question.
Hot Gyro: I think Java would be it for me.
Spasmodic Awesome: Okay. So, let's just test this. And I think this runs fine. So I just go ahead and delete this. So that when you have a new question, or maybe I can just add my question...
Hot Gyro: Yeah, you can just add your question in the comments there for me, I can reuse some of the existing code here.
Spasmodic Awesome: So this is the question. So yes, you can edit here.
Hot Gyro: Okay.
Spasmodic Awesome: So basically, I have a two dimensional graph that I want to... but I have a few parking, it's like basically a parking lot that infinity represents empty spots. And we need to go to a parking lot. So basically, but the infinity doesn't count... Zero is for cars and minus one is for every obstacle. So you cannot cross an obstacle to reach to a parking lot. So basically, I want to find all the nearest like distance of all the parking lots from a given car. So basically, I want to replace car like zero in the grid with the nearest parking lot distance. So for example, if I have... If I have a grid, which is like this, and you'll get the idea. And we kind of want to replace it with the nearest parking distance. Let's say this one. Give me one second. So this is to demonstrate. With checking you can see clearly now.
Hot Gyro: Yes, I can see. Yeah.
Spasmodic Awesome: So you have.. Yeah. If you have to draw by hand, the output should be... Do you want to give it a try?
Hot Gyro: Oh, yes, I think I understand. The output over here would be 3 -1 0 1. Let me just make this a little easier format here to me. With the 1 2 3, again, three here, two two one minus one. And, and here will be one, minus one, two, minus one. And here, we might have zero, minus. I think that would be... If I understand the question correctly, that would that be the output?
Spasmodic Awesome: Yeah, looks like it. So basically, at every node, you take the minimum of all the distance. Sorry, yeah. Take the shortest distance here. So and yeah, I think, yeah, basically...
Hot Gyro: Okay. I think I understand the question. So I can try to do it. I just want to know how much time we have for this question.
Spasmodic Awesome: I think they give you around one hour.
Hot Gyro: Okay, perfect. Yeah, let me talk about how I would approach this question. I think the input here would be a 2d array. And first thing I think I can think of this is I think there's three states right? For simplicity, I can maybe make this infinite into another number like two, just to simplify the sort of...
Spasmodic Awesome: You can make it a really large number.
Hot Gyro: Yeah, right. Yeah, I understand why it has to be large, because this array could be really large. You don't want to confuse it with the path. But I can make it like a negative number too, like that would kind of satisfy the intention of this question. So what I'm thinking of is given the array, I would have to loop through the array and identify the zero, like what a car is. When I identified the car zero, I would call breadth first search to basically find all the empty spots, and then fill that with the distance from where I am at. And I want to do a BFS, I would have to use a queue. So whenever I visit a node, I would put the neighbors into the queue so that I would iterate. So I'm thinking, should it be a BFS or can it be a DFS. When I visit, I will just update the path. I think DFS would work. I don't necessarily need BFS. I'm thinking about this right now. So just to clarify, is a diagonal consider a path or it has to be horizontal and vertical?
Spasmodic Awesome: It has to be horizontal and vertical. So if I am filling this zero which I have highlighted, I have to... I cannot count something like this infinity, it has to be like every edition of horizontal and vertical.
Hot Gyro: Okay, got it. So, here at this point, I mentioned... so just to backtrack a little bit, I will loop through every position and then as soon as I identified a car position of zero, I will start my traversal. And in my traversal, I will... This one I'm not sure, do I really need a BFS or can a DFS work. It sounds like a DFS would would be sufficient too. So I think I'll start with that. And then in my DFS traversal, I will basically replace any infinite cell with the distance from where I'm at. And then if it's, if that cell already has a distance, I will compare to the shortest, and fill in the shortest path, and I will complete it, after traversing, looping through the whole array. That's what I plan to do. And I'm going to start coding this. And so I will remove all that. And first thing I will do is create an array input. So I will call this array input. And how do I do this? Join to four, I don't even know if this works. Let me just kind of run this and make sure there are no exceptions here. So this will give me my four by four input. And I will fill this in now. So that oh, this becomes hard to do. Nope, I can do this, I will fill everything in as infinite. Yeah, I can do that. Yeah, so at this point, all I'm doing is creating the input so that when I finished coding, I can test it to confirm that it's working. So this is what I would do, I fill basically everything with that, and then update the values manually. So this is that. And this is minus one, which is one, three, and then 2,3,2,1. And finally, up two, three here. And finally I have to three, zero, three, one. Okay. So this would be the input that I have. I know this, this is actually wrong, but I'm not sure why I forgot.
Spasmodic Awesome: Oh, don't worry about passing. Don't worry about passing the input into code, because when we call the function, we can pass it in the main part, or you can just use a function and then we can pass the values in the mean. Yeah.
Hot Gyro: Okay. So, okay, sure, I'll do that later. At this point, I will start doing the I guess, shortest path. And the input would be the front of the map. And that's it. That's all you need to do right? It's an in place operations, in place update on the map. So first thing I do is find the dimension. And the dimension would be that, and this would be array dot length. And we could do some edge cases checks here. But I will skip that for now, just to be aware that you know, it's the it's an app is not certain size, and we don't want to do anything. But for the most part, I will do zero. This is the part where I am iterating through the the map. So at this point, the runtime of the algorithm would be O(n*m). At least for iterating through the map. So linear by the number of positions. And at this point I will say DFS array and pass in the array. And so now I need to code up a DFS. I think a better way to call it would be like explore. So, here I am with this method, and I will traverse... In this method, what I will do is given the position I will traverse the neighbors, sorry traverse around and then identify empty parking spot and then if I see it, then I will update the location of where it is. So, I might have to change the input here. But at this point, what I will do is, yeah, I'm thinking a little bit here, how I plan to do this? Yeah, okay. First thing I do is I check whether the inputs are within the size of the map. So again, I would have to make use of, as I mentioned, it's known as I mentioned, because if the input given to me is out of bounds, then I need to return right away, without doing any checks. So, this is a check. If i is less than zero, or i is greater than equals m, or j is less than zero, or j is greater equals to n, then I'm out of bounds so I just return. Otherwise, we will check if the array is infinite, so that would be integer max. And if it is, then we can fill in, we can update the value and what we will update is the distance from the from i j to here. So how do we do that? So that means that every time we go through the traversal, we should increment the distance, so that it at least reaches this point, we can update that. So, I will need to update this method with the distance. And so, when I call this obviously, this will be distance zero. And I will start at zero and we update this. So, I am calling it, if this is not the value, I think before I do the updates, I need to check the the neighbors as well. So this is how I do the traversal. So I will do array and will be i plus one j and distance would be distance plus one. And I will repeat that thing in four directions. And so this would be minus one, plus one, and this will be minus one, and it will be i. So this is the four directions that I need to visit and every time I will add one minus one. Now when I get to the point where these are all complete. So I do that for each of those. And for each of those, I do that. And when it comes to updating the current one, what I do is I check if it is max, then that means we can update it to the current distance. But if it's not max, then if it is already a number that's greater than zero, then that means it's already been updated to some other value. So now we do the check to see if it is greater than zero, then that means it's already a path for another car. But now we check whether this is greater or less. So at this point, I can assign this to i j ro the minimum of the original value and the current, that's what we do here. And sounds like this is all that I need. So I'm going to try it out to see. I think I'm missing something, but at this point, I just want to try it out. So, I will call the function with the input. And this is in place updates, so I need to print out the result. So let me do the printout here.
Spasmodic Awesome: You are modifying in place, right?
Hot Gyro: Yes, I am. So I want to print out the array as well. So this is what I plan to do. Yeah?
Spasmodic Awesome: Instead of printing it element by element, can we just print the entire array?
Hot Gyro: I don't know how to print the entire array in one line. Is that even possible?
Spasmodic Awesome: It is for Python. I haven't used Java recently.
Hot Gyro: We can try this? Yeah, I think this is the way to print this out. I don't know Python could do that, too. I will have to look it up. Oh, I see. Okay, that's cool. I got some errors, by the way. Oh, yeah. I think this is wrong. This should be this.
Spasmodic Awesome: You have two semicolon.
Hot Gyro: I have that as well. And looks like okay, well, let's see this goes. Hmm.
Spasmodic Awesome: Yeah, using it in this function. But it's not defined inside mean.
Hot Gyro: Yeah, yeah. You're right. Well, so I think this is bad. This is entirely in line 52. Yeah. So just like I envisioned something was wrong here. I think the problem is, at this point...
Spasmodic Awesome: You need to check if the i and j is within the boundary of the array.
Hot Gyro: Yeah. So I think we need to terminate without continuing if we are at the boundary. So here is already bound is already... we already checking whether it's out of bounds. But I think what we should do here is when we are at the obstacle, if this is a minus one, we should return because we don't need to consider... Hold on. No, we should continue. We should. We shouldn't continue it it's an obstacle. We should turn back and then visit the other node. So I think that's one thing. But I think there's also more if I'm at the end I should I just still look around. Let's see if this works. It'll kind of still reset this. You want to see the... Okay, cool. So we're working 50 to 64 I am getting the exception and I will illustrate why.
Spasmodic Awesome: So you are calling a function, you're calling a function from within itself. But there is no exit condition like if i is less than zero, i is greater than equal to m... You are not incrementing i or j anywhere. So it just she means the same value like how well... yeah, you're increasing i plus one. But yeah, that wouldn't terminate it. So you need to call this explore from... I don't think it will work if you call it within explore. I think explore needs to be called from some outside function.
Hot Gyro: So I am calling explore from like my shortest path method here right? Sort of an entry point. Yeah. Yeah, I think Yeah.
Spasmodic Awesome: When it enters, it's like an infinite loop because it's just not able to exit.
Hot Gyro: Yeah, I'm trying to see if I'm just one condition away from exiting. So this is what I'm thinking. Because if I start off at the top left corner, 00. And then I say, Oh, I know, I should only do this if the array is zero, right? Now, that's one thing, I can simplify the solution a little bit, because we should only explore over updating. I mean, we are updating the infinite values, but we are only doing a traversal starting from the car position, right? So that's what we should do as a 0. So if I run this loop, if I run it, if I look at this first position would be here. And then the explore would look at minus one look at infinite, infinite look at these three positions, right, the last one would be returned right away. So okay, so something, I think something here is wrong here, because should I be calling it like this, or...? Well, hold on this one would be returned right away. And then I would call the one next to it, which is, which I will update. When I update, I should return right? Yeah. So when you update that I return, and then I would go to the bottom of an update and return. I think that that's actually good. And then I come to j minus one, which is minus one minus one is an obstacle, so I returned right away. So why would I be getting exceptions? I want to know if I want to, yeah... So for me to address this, I will print out i j. And that will hopefully help me figure out what my problem is. Because I feel like...
Spasmodic Awesome: if you have to, like actually draw it, like draw your code as an example. Like you, how are you transitioning from one side to another, like, you are doing this inside the shortest path. But this is just iterating, you are not actually moving at adjacent based on any condition like looking all around, but you are not really transitioning from any...
Hot Gyro: So when I call explore with i plus one and j, this would be let's say that, yes.
Spasmodic Awesome: Let's say that I call it on i equals zero and j equals zero. Is just like just the first case, it would go to it will check if it is equal to zero. And let's say it is and then it will go to explore. But then your i and j will both be equal to one throughout this infinite loop. Like it's not transitioning or the value of i or j is not changing. So it will continue looping on exploring around i and j. Let's say that you are starting from the first i and j column, you are going to go to j minus one. But that does not exist, those are edge cases.
Hot Gyro: Yeah, so I understand what you're saying. So on the second part where i and j does not exist, I think here we'll take care of the right, this condition here. Yeah. Because what you're saying is I'm basically going back and forth. I am jumping from zero to infinity back to zero back to infinite. So that will never stop. So I need to have a stopping condition of not visiting nodes that have already been visited. Right? And I think that's a challenge for me because I don't know how to prevent the explorer from visiting itself again? So I need some conditions here. And I first checked out of bounds. I checked minus one. I can check zero. Yeah, if you're not part of zero, so that's another one that helped. So basically cannot be less than or equal to zero. That helps. But what if it's a regular number? Actually, if it's a regular number, I think this will already do work to a lot. Let's see, I think this will still not solve the problem. But I think it's slightly better than before. Oh, yeah, this is the output. That's interesting. Okay. I think this is because I did not set it to... I did not set this to infinite here. I wonder if this is correct. Yeah, I know in Python it's easy to add this. I can quickly do this. Yeah. So let me just do this here.
Spasmodic Awesome: You can set it to 100 if that helps?
Hot Gyro: Yeah. But I'm very close to getting it here. This will just change to variable more. And this will be... Okay. So I think my one extra loop there. Let's see how this goes. Ah, yep, yep. Got it. Got it. Yep. Vertical. Let's see. I'm a little anxious to see. Oh, okay. That's yeah, in Java. I think now, I understand what you mean by hundred, because that will make a little easier to read. Now I just have to change this 100 for the purpose of simplifying the the output.
Spasmodic Awesome: So this is your input.
Hot Gyro: Oh, I'm printing out the input. Yeah, you're right. But then I should have updated already. Yeah, it should have been updated, but it's not. So that's interesting. That means I have a bug here. If it was 100, I would have updated with the index. And why is it not updated? Let me take a look. Am I not updating the array?
Spasmodic Awesome: So it's repeating that input. So it's not correct even for the input. It's the first or second column is zero. But the input is minus one. You might want to print both the input and output and then we can do.
Hot Gyro: Okay, so this is the input output. Yeah, yeah. Where the input is. And let's see how this works. Let me just make sure I put input here and select it. Yeah, that's not cool. Okay. Printing the input and output out together. It looks like nothing has changed from the input and output.
Spasmodic Awesome: Yeah. Yes, that's right. And your input is a little wrong per as the question, like...
Hot Gyro: Yeah, yep. Let me fix the input. I think there is a bug in the in the Explorer method. So let me just make sure the input is okay. So 0, so i think i have the one right I have that's wrong here. How can this be like completely off? Am I printing it out in order? Or am I rotating it? Let's say is zero... I'm just trying to understand where I printed so that it's the wrong input. Yeah.
Spasmodic Awesome: You are comparing both i and j with n, there is no m, like I know n and m are both same, but you are not really having a like even in this, I'm not sure if this is how Java works. But you're defining a dimension for n, but there is no dimension for m. So should this be an nxm?
Hot Gyro: I think this is fine, because I think I'm able to get a two dimensional array here. They're all initialized with 100. So this is all 100 first, but I'm just trying to, I think it's easy for me to do this. I'll just do a minus two and then see what what does that where does the minus two enough? So even the input is not being updated. Right? You can see the minus two is not anywhere. Yeah. So there's something really weird happening with the input. I declared the array here. And I'm supposed to get a minus two here, right? And when I print it out, it's not an... if I didn't really call anything. I should get the same thing as minus two somewhere. But I am not getting the minus two anywhere. So what is the problem with was this? Am I printing this wrong?
Spasmodic Awesome: Yeah, I think you're printing it right.
Hot Gyro: The thing is my two is not appearing anywhere. So the only reason why appear anywhere is that it's not updating the right way. I am printing it out with...
Spasmodic Awesome: Yeah, you might want to print it as soon as you're assigning, like right here. You can simply print it here.
Hot Gyro: Print the whole array here?
Spasmodic Awesome: Yeah.
Hot Gyro: Okay. So well, it will be all empty if I do it here. Yeah. Okay. Beginning, let's see how this goes. I mean, it's not that. Great too? Yeah, if I haven't declared that there's nothing there. So it wouldn't work. But I think what I can do is I can get out. Before I do any updates, I should get all hundred, right? See, if I do get everything hundred. I do. So that's expected. And then when I do the updates, unless I do it wrong, or maybe I'm updating it again. Oh, I know why it's zero, because I updated it again in the next one. So that's why they're there. So this is supposed to be minus two. And one, three, this work. So that's good. At least this solved one problem. Yeah, minus two is there which is good. So it is supposed to be minus one. That was the one mistake there. And then everything else looks good. Okay. So now I think the update is perfect. I think I just forgot to update the indices. And now we can see the input is perfect. Now the output is not. So the output is the problem here. So I'm not updating the output properly. Oh, I know why, because I'm not calling the close path. So let's do this. Let's see, if I get something good. Okay. Again, the output is not updated. So now I need to come in here and then check what? I don't need this anymore. And I need to come into the shortest path. I'm not going to handle the edge cases at this point. I will go through the loop. And they should be four, four, and only if it is zero, then I explore with the index. And if I were to do a printout, so right now at this point I'm debugging and I will check to make sure that I am coming in, I am calling explore on inputs that start with 0. So should I run this I should be only calling this twice. Looks like it's not even coming in at all here. That's why. So that's interesting. I should be running this double for loop, the array equals zero. If it's equal to zero, then I so in the code here, the reason why the output never change is a change to zero. Two and three zeroes. Those are the right input. So that's good. So at least we are going into the exploring method. So the problem is in explore here, right? Let me scroll up to confirm, looking at the map here and explore what we're doing, that's not correct. We are up in a distance of one every time we call it. And that's correct, we are looking at four quarters of the neighbors. And when we're doing the update... oh, so I think this might be a problem. I think the update should be done before we traverse. I think that's one thing. We should update it before we look at somewhere else. So if I do an update here, if it's 100, I update to the current distance. Because 100 means it's empty. And otherwise, if it's greater than zero, I will take the min. Yeah, I think this should be better. It's still not updating. So I think at this point, it will come down to me checking whether I have entered the distance here. Again, that and this is... I will put this here and then see what happens, just to see if I'm updating anything at all. It looks like I am not updating anything. It sounds like I am never coming to 100 in the code.
Spasmodic Awesome: Yeah. I think there is some problem. There's some problem with the way you are traversing. So yeah, i and j values are not getting updated. So just to debug that. And just seeing that if those values are what is expected. Like every time you hit 100, you are going into another function. It's true. So you might want to print every time you go to explore what are the values of i and j and then see, like if it's traversing or if it's really moving. But I think there is something missing with the traversal part. Like, were you actually traversing the array?
Hot Gyro: Do you think I'm close to the solution? Or do you think I'm missing? Or do you know if I'm missing a huge part of this?
Spasmodic Awesome: I think you are pretty close. I think it's just... So basically, the logic is more or less good. It's just that it's the traversing or the increment of the variable, which is missing. And so we can still work on debugging this for 10 minutes. So we can just print the values of i and j.
Hot Gyro: Yeah, so I printed it out. And it looks like I only traversed this twice, or none at all. And I think...
Spasmodic Awesome: So the first time you are going into the function is when i is zero and j is two. So you want to start with an i is zero and j is zero, which is the first hundred.
Hot Gyro: I wonder, you mean I should start in the top corner?
Spasmodic Awesome: Yeah, so basically everything you see 100, you are traversing. Every time you see a zero you trying to go to... So when does it have to call the function? Every time it sees a zero?
Hot Gyro: Yeah, so in my shortest path method, whenever I see a zero, that's when I start starting the Explore function, right? Or the method. I start at the first zero and then I start looking at, I start doing the DFS traversal and then update anything that says 100. So what I'm seeing as the problem here is zero and two is correct. It's first cell that is zero. Then it never called anything else. I think just fix it. I don't know why it exists, because I know Yeah. It shouldn't be right. It shouldn't. Actually when it's zero, that way, it'll never actually update anything. But if I put minus, if I put less than zero, then it will come back to the current cell and it will be an infinite loop. So the problem is I don't know how to ignore the current, the starting spot, right?
Spasmodic Awesome: I think you... Yeah you did it alright? I think the starting is already ignored because they are having i + 1, j and everything but the current cell. So there is no i and j in our calling cell. So it really does.
Hot Gyro: But then if you look at the 58, or 59. The next one will call the current cell back right? If I call one i plus one, the next one will call i minus one. So they will come back to me.
Spasmodic Awesome: Yeah, it was stopped right here?
Hot Gyro: Yeah, they will stop. Because of this.
Spasmodic Awesome: Are you saying this is working? I still think is wrong. Yeah, yeah. Yeah, that's all. Yeah. So the problem is, I don't know how to prevent me from updating the current cell through the cycle, traverse and come back. You can actually put a check that wherever you are traversing, it's not the current cell. It's not i j.
Hot Gyro: So I need to change the argument somewhat more? Is that what you're suggesting?
Spasmodic Awesome: No, I think where you are updating, you can add an argument and mentioned that if it is i j, you can just ignore that.
Hot Gyro: Oh, I see.
Spasmodic Awesome: So yeah, I have a question. So I can see that you are using this distance variable to update all the values for zero. But I don't see it being initialized inside shortest. path.
Hot Gyro: So this is initialized here. Ready to go. I think you're right. I think this, this might work. I think this might work. Let me just try this. Oh, no. It's still not gonna work. Yeah, there must be something that I don't see it because I I added that if it's 0 0, then I just return. I don't have to continue. Well, no, it can it. Can it be zero? Yeah. Could be 0 0. Yeah, there'll be just like the first or the first time I come in, I'm the zero then. Then I will just keep going. So yeah, I think at this point, I just don't know the algorithm well enough to... I have the idea. But there's got to be something that I'm not able to figure out how to stop it when I'm in here. You know, at this question. I have seen it a year or two ago. But I just at the time, I didn't know how to do it. But now I felt like I know how to do it because I can traverse a 2d arrays. I originally did the question of like computer, the number of islands and that way you could... That question was easier to understand.
Spasmodic Awesome: Yeah, it's kind of similar to...
Hot Gyro: Yeah, yeah, yeah. So yeah, it's kind of end it here. I couldn't solve it. I don't have time to solve it. Can you give me some feedback on you know, parts that I can improve? Parts that I did well?
Spasmodic Awesome: Sure I yeah, I have a few points. I'll definitely add that. And I think your approach should work. But just the initial time, which we took to, I mean, we had a lot of time, but usually they kind of want to start two questions in an hour. So I think you can improve on the speed with like more practice and stuff. I think your approach is fine, but two things which I can definitely feed off is the distance initialization. And we're just off the travel still looks a little off but I yeah, I am not exactly sure which line is wrong. Because yeah, this Java is new to me. But yeah, I think you are close once the distance and travel part is just yeah, I leave for detailed feedback and I'll also leave few questions which I found were similar to this.
Hot Gyro: Okay, yeah, that'll be very helpful. And one last question I have is, is there a follow up on this problem? Like, if let's say I solve it, are there additional questions about the solutions that you could add?
Spasmodic Awesome: Yeah, so usually I have been asked like two questions. Two questions from every interview. So, yeah, I think once you solve this within, like, within an hour, and ideally, so there can be one more question, or they can be a variation of this question or some build upon this question.
Hot Gyro: What would be a variation or a build up about this particular question? I just want to know, what is the next part of this question?
Spasmodic Awesome: Maybe there could be things that are taken, like you cannot... You can have, I don't know I cannot think of exact variation. But we can play around with the difficulty and add some constraint which makes it more difficult.
Hot Gyro: Got it. Okay. Sounds good. Okay. Yeah. Thank you so much for your time. And, it was a good question. I'm gonna study a little bit more.
Spasmodic Awesome: I'll have a link for you to the question and similar stuff. Yes.
Hot Gyro: Oh, awesome. Thank you so much. Have a good rest of the day or evening.
Spasmodic Awesome: Yeah thanks, bye.