We helped write the sequel to "Cracking the Coding Interview". Read 9 chapters for free
Bus Routes
Watch someone solve the bus routes problem in an interview with a FAANG engineer and see the feedback their interviewer left them. Explore this problem and others in our library of interview replays.
Interview Summary
Problem type
Bus Routes
Interview question
You are given an array routes representing bus routes where routes[i] is a bus route that the ith bus repeats forever. * For example, if routes[0] = [1, 5, 7], this means that the 0th bus travels in the sequence 1 -> 5 -> 7 -> 1 -> 5 -> 7 -> 1 -> ... forever. You will start at the bus stop source (You are not on any bus initially), and you want to go to the bus stop target. You can travel between bus stops by buses only. Return the least number of buses you must take to travel from source to target. Return -1 if it is not possible. Example 1: Input: routes = [[1,2,7],[3,6,7]], source = 1, target = 6 Output: 2 Explanation: The best strategy is take the first bus to the bus stop 7, then take the second bus to the bus stop 6. Example 2: Input: routes = [[7,12],[4,5,15],[6],[15,19],[9,12,13]], source = 15, target = 12 Output: -1
Interview Feedback
Feedback about Ruminative Pterodactyl (the interviewee)
Advance this person to the next round?
YesHow were their technical skills?
3/4
How was their problem solving ability?
4/4
What about their communication ability?
4/4
Overall: Considering that candidate is applying for SDE-1 position at Microsoft, this interview could be hire call. But candidate has booked general interview with experience of 2 years, thus as per normal bar for SDE-2 this would be leaning hire. Thus marking it as "No". Summary: Candidate make sure they understand the problem and then proceed with solution. Candidate articulates their solution well. Candidate has good application knowledge about data structures. Candidate can improve complexity analysis skills. Candidate does not get panic while solving the problem. Candidate write a modular code with good naming conventions. Notes: + TC worked with the example one to make sure they understand the problem. + TC explained their understanding about the example1. + TC mentioned that this problem can be modelled as graph problem. - TC mentioned that they can have bus-stop as nodes of the graph. + But then realise that it would be difficult to calculate the bus switches. + TC clarified if it is okay to assume that there will be one source and one target as a input. + TC shared a approach. + TC could have done better in terms of the time complexity analysis. + TC used the set data structure to keep the visited nodes. + TC wrote modular code by having helper methods to build the graph. + TC used good naming conventions for method names and variables.
Feedback about Red Maelstrom (the interviewer)
Would you want to work with this person?
YesHow excited would you be to work with them?
4/4
How good were the questions?
4/4
How helpful was your interviewer in guiding you to the solution(s)?
4/4
Interview Transcript
Red Maelstrom: Cool. We'll spend like 40 to 45 minutes on coding problem. And last and 15 minutes we will keep it for the feedback.
Ruminative Pterodactyl: Okay. Thank to. Okay, no worries. Go ahead.
Red Maelstrom: Yeah. Please say.
Ruminative Pterodactyl: I just want to share that I am going to interview for Microsoft for I guess SD one level.
Red Maelstrom: Okay.
Ruminative Pterodactyl: Yeah, I just want to let you know that I'm preparing for that.
Red Maelstrom: Okay, sure. I never worked at Microsoft, so I'm not aware of the format exactly. But I do feel like they would have a typical coding interview.
Ruminative Pterodactyl: Okay. Should I just go ahead and do the question?
Red Maelstrom: Yeah. So basically you have array of routes. So each route is nothing but number of series of stops that a bus takes. And that bus will keep on repeating in that route in circles. And along with these route, you have two things, a start and a stop. So basically you have to tell what are the minimum number of buses you need to take to go from source to the target. And if there is no way you can go from source to target, you should return minus one.
Ruminative Pterodactyl: Okay, let's see. So basically source here is one in the example first and the target is six. So this is the bus number one, right?
Red Maelstrom: Yeah.
Ruminative Pterodactyl: And it goes to these stops, you can say one, two and seven. And there is another bus that is like three, six and seven. So basically we have to take like, so the question is basically the number of buses, right? Okay, so from first I can take seven, right. And then seven can go to three. And then three goes to six. So I guess this should be like two number of buses that I have to take correct?
Red Maelstrom: Right.
Ruminative Pterodactyl: So what I'm thinking is basically it can be represent as like a graph problem. So what I can do is basically convert these arrays. Sorry, am I audible? I'm just getting this error.
Red Maelstrom: Yes, you are. Okay, you're audible.
Ruminative Pterodactyl: Okay, take the first bus to this. Okay, no worries and then I have these routes. So for example, second I can go. Okay, this is twelve. So I'll take this bus as this is the source. So 15 and it has four and five. But four and five is connected to nothing like no other buses at the stop. So that's why I cannot reach to this particular source. That is twelve right. Okay, so what I'm thinking right now is basically creating like a graph from this. In my graph it will be basically. So I'm just taking the first example. So I'll go through the arrays of array. So one that is connected to two, right. And two is connected to seven right. And then I'll traverse through the whole array. And then there was three. So three will not already be present in the graph. So I'll just create like a three here, right. And then there is six. So six is already not present. So I'll just add that. And because seven is already present, so I'll just have a connection between six and seven. So that's what I'm thinking of building the graph. And once my graph is built, what I can do is I can just iterate over. It's like neighbors. And what I'm doing is either we can do like a d depth first search or a breadth first search here. But our goal here is to return the number of buses.
Red Maelstrom: So you are saying that the nodes of the graph is nothing but the bus stop, is that correct?
Ruminative Pterodactyl: Yeah, but again, in this type of, if I'm doing this, then the issue would be like how will I be counting the number of buses, right? Because if six is connected to seven, if I connect the six to basically seven, what I'll do is I'll start with seven here and I'll just go through like doing a DFS. Sorry, doing a bfs. If I start, I'll go to its neighbors. That will be like six and two. And it will be like unidirectional. Because I guess I can go from. Like, it will be unidirectional. But anyways. But if I go from seven, if I start, it's just that there is no way of counting the buses for me. So this might have, might have to do. Think of something else here. Let me think. So let's say this has to be zero. I, it sources one. Okay, so one can go to two and 17, six. But that should be like number of. So I might, I might have to make an account of like number of buses as well it. So if I take like a graph not checked. So if I do this. But again, I have the array index for that. So I can, so I can just like from seven, seven goes to one again right. It does not go back to two, correct. If they're like route given. So it's going from one to two to seven and going back to one, correct right. It forever. For example, bus travels and sequence forever. You will start at the stop source initially. Okay. I'm just trying to represent if I like, basically, if I represent this in like a 2d array. So I did this. You it. So let's say if I have like seven entries or if I have this. It. But again, it can be anywhere. So do the profit not work? Here's. Um. So if I take basically zero, comma. Zero. One, it. It. So again, I'm thinking right now, because I can have an object where I can represent the key, as in buses. But again, in this case, I'm just thinking of, I cannot traverse here. So if I have to traverse, there has to be some kind of graph connection. I'm just thinking of, can I pass the number of buses that I am in? I'm just connecting. So if I found this, I have to. I'm just keeping an account of it's in the same bus or the different bus. So here I'll start with the source. Sources. One. And there can be multiple sources as well here. Or can there only be one source and one target? How will that be?
Red Maelstrom: There will be just one source and one target.
Ruminative Pterodactyl: Okay, so. It. Basically one will have, one will have. I can go to two. Then from two I can go to seven. From seven I can go to one. Again for a level one, what I can do is I can have like three. Three can go to six, okay, now to six. From six I can go to seven. And from seven that is already there. So I can go to three. So seven can go to three and then three can go to six, okay? So here, if I start from the source, that is one, one goes to. Two. Then two goes to seven, seven goes to. So there it can go to one that is already visited right now. And then it will then go to six. And then six will go to three. Sorry. Three will go to six and six is our target. But again, here I should be, basically. I can do something like one. So basically a bus number, comma, one, comma, one number three is basically two, right? And the six is two as well. And the seven is. Two. But anyway, if I reach the target. If I have the target, I will. Just return the number. Okay? Yeah, so, sorry, I got a little bit stuck over there. So what I was thinking is basically creating a graph out of it. Now, instead of just the node, what I'll be thinking of is creating, basically keeping the counter of which bus is it. So basically, if I take this example, one, two, seven. Like the first one. So the one will go to second, right? The second will go to seven, will. So as one is already visited, it will visit like. Oh, but no, it will anyways visit the children's, right? So if I start from seven, it will go to one. So second and seven, then it will go to the second child, that is three. And three will go to six. And six is our source and it will just return the bus number. That should be, that should give us. The transfer in the bus number.
Red Maelstrom: So you are having a mapping of bus stop to what buses goes through that bus stop.
Ruminative Pterodactyl: Yeah. So I have this arrays, right? So I'm just thinking of how will I be taking an account of the number of buses, right? So if I start from one stop and I go to the other stop. So basically if I don't count one here, basically if I don't keep an account of the number of buses and I will just create this graph, it will just visit and it will tell us that it is possible to go to this source destination, but it will not return us the buses it took right. So this particularly, it will basically have the number of buses that it will return us the answer. Right.
Red Maelstrom: Okay, so if we take step by step, like when you will go through the array of routes and create this mapping and then you would add into the queue and iterate through it.
Ruminative Pterodactyl: Yeah.
Red Maelstrom: And what would be the complexity of that?
Ruminative Pterodactyl: So again, the complexity of that would be, worst case would be like going through every element. So all the routes that I have, in the worst case, if there is. Like no. The target is not present, then I have to traverse the whole thing. If I'm considering that there are r routes, then of r basically, and it is traversing all the nodes. Ah, should I proceed like doing code? Or we can discuss on it more. What do you think about it?
Red Maelstrom: So can you walk me through like first example? You already did that.
Ruminative Pterodactyl: Yeah. So basically my source start is seven, right? So I'll go through seven, right? Oh, sorry, my bad. My start is one. So basically I'll traverse with the one. I'll have like something as visited set that I'll be carrying for the nodes that I've already visited right.So I'll put that in the queue. Then I'll traverse that. I'll traverse to the children, like the nodes, the neighbors of it. So basically one, and then it will come to the children of it. That is two, right. And it will come to seven. So I'll go to the node and then I'll traverse to the neighbors of it. So two and two will be neighbor. I'll be going to seven because seven is like neighbor of two. Then when I come to seven, it will visit one and it should be present in this visited node already. So what I'll do is I'll traverse with the other node. That will be three, right. Then three from three, it will go to six and then six is basically our source. Like the target is six and I can just return the counter that we are keeping. So how does that sound? Obviously, like this is like one case that we are thinking of another one at the end. I can just have, if I don't find the source target and if I'm not exiting early, I'll just return that. I'll return at the end that it's minus one. Basically the node is not present. Um so does this approach sounds good or you have like a better approach in mind or if I'm going wrong anywhere?
Red Maelstrom: No, I think we can code.
Ruminative Pterodactyl: Okay, so it, it, function, function, search route. It will just take routes. Okay. And then what will happen is, so.I'll be creating a graph out of it. So I am using like a helper function, build graph. What it will do is. Now what I need here is basically for let I less than routes length. I'll be creating a graph here at the end, I'll be just returning the graph. So now I'll have let. So I'll be getting an array in that, right? So let it. And then for that j equals. So if my. Basically my temp of I, j is in graph. If it's not in the graph, then what I'll do is I'll just create. That and then I'll push it. So if I'm at two, will push the second one. So it should be ten, dot push it. Temp of I plus one. But again, this I have to handle here. If I plus one is equals, equals to temp length and. It push this. Actually I'll be pushing this and comma I plus one. So if it's like the last element. What I'll be doing is copy this if it's the last element and still be, so this I can do here. Sorry, if, yeah, one. So temp of zero. Basically if I'm like the last position, I'll be pushing it to one again. So after doing this, this should build our graph. Okay, then I'll just have my, so for zero, r s less than roots, length, I plus plus for let j equals to zero, j is less than sub zero, length n j plus plus. Okay, so basically if my routes of I comma, j is equals to equals to, I will be having like a start and end. So start and an end. So it's equals to start right. So then I have to do my traverse basically. So I'll be traversing and that should return this. I will just do a traverse. I'll call the traverse here. And what I'll do is I will give routes of I. Then I'll provide the graph. I also have to have like a visited. So I'll be just creating a visited set here. Okay, so. I'll come back to this. I'll start writing the function first. So function, just take this here. So this will be like my node, right? So I can do like if visited has the node, I'll just return it. Otherwise I'll just visit add node, understand? Limit here. Oh no, the node should be, it equals to node, okay. While my q dot length is greater than zero. So let my desk. So what I'm thinking is, so there will be like a stop and bus here. What I'll be getting is. Have a graph, right? Graph of stop. So neighbor of stop. So here I can check not invisited. If it's already not invisited, then I want to push it. Q dot push the neighbors. So this is stop. Okay, I push the neighbor here, right? Um. So here I have to check if my so neighbors here drop off stop will be again this neighbors here stop. Okay, so this should again be like I can destructure to m stop and then if m stop isn't visited, but I have to push the whole thing. So I have to push this here. And if my end stop is equals to equals to end, I'll just return the bus here, okay. And so I'm returning bus. If I'm not returning bus at the end, I'll just return like minus one. If I like all the duration when I went till all the things so. Visited, I have to still add to the visited. So q dot push this and then I can put this into visited, add and stop basically. So. Yeah, so this will be expecting. Either a bus or whatever. So I can just return this I guess. Yeah. So what I'm doing is basically I'm starting with this function, I'm building the graph here. Then I'm starting from the root, that is like the start root, right? And obviously here also I guess I have to handle here minus one. If I don't have the start position, they should handle that. Then I'll go to traverse and I'll be providing it with, for example one. So one it will go to. It. Will go to route, so one will. Be here. One will be in the queue, then it's shift, it will still be. Okay, so this has to be like a stop and then I'm traversing, so stop of stop. So it will go to 201. So two is not equals to end. So it's not in the visited as well right now. So it will go in, it will. Push two in the queue. So I guess instead of this I should be just pushing this and stop. It will go to two. So two will be here. It will go here. It still have length greater than zero. Two will be the stop. Then it will go two to two. Seven, one. So then stop will be seven and. Then bus will be one again. Then one. Seven is not the end. It will post. Seven is not in the visited as well. It will push it in the queue. It will put in the visited, it. Will go to one, right. So one is already visited. So it will go to the next of it. So that's three. Three it will put in the cube and then the source, it will go to three children and six, six is in, six actually is equals to N. And it should return the stop. So that gives us the bus number like the buses. And it will just return here and it will return two. If two was not six was not present, it should just go through all the list and it will return minus one. And this should return minus one. This is like my approach. What do you think about it? Ah Sorry. I have to pass start and end as well. Actually just end here for the reference. Yeah. So I can try running it or how do you want to go ahead now?
Red Maelstrom: Yeah, first test case.
Ruminative Pterodactyl: Okay, let's try doing that. And then to call the start and end source. Source and target it. How can I run over here for graph stop is for let m stop in graph of that.
Red Maelstrom: Can you print graph once how you have built it?
Ruminative Pterodactyl: Yeah. So. So my graph is this.
Red Maelstrom: What does two comma, one represent?
Ruminative Pterodactyl: So it's.
Red Maelstrom: Basically one, two. Seven is a node, is a route.
Ruminative Pterodactyl: Right.
Red Maelstrom: Which you are presenting as a node. Okay.
Ruminative Pterodactyl: Yeah. But I did this. It. Sorry about that.
Red Maelstrom: So if it's adjacent to list, right?
Ruminative Pterodactyl: Yeah.
Red Maelstrom: Elements in adjacent list should also be routes, right?
Ruminative Pterodactyl: Yes. That I'm trying is basically temp of. Just a second. So find this. My temp is of g. Okay, my bad. So if temp length this and then temp of g is this. Yeah, it, ah, anyway, so. Now I get to one, two. Two is going to one again. Why is that one, two do? Yeah, so now it looks a little bit how I want it, but again, this is seven and it's showing undefined. Why is that? So if it's like seven is I guess at the end. Yeah, it could be that. So if I plus one is temp dot length of zero, it should be j plus j plus one as ten dot length and zero. It's not running. Why is that? Can you run this code from your end? Because I'm trying. It's not running. Is there any issue with the.
Red Maelstrom: Yeah, I hear the same result. It improved. Yeah. Now instead of undefined, it's showing something.
Ruminative Pterodactyl: Is it showing something for you?
Red Maelstrom: Yeah, you can see right in the output instead of undefined comma, one. It's one comma, one.
Ruminative Pterodactyl: It's not showing on my screen actually for some reason.
Red Maelstrom: Can you scroll down the output window?
Ruminative Pterodactyl: Yeah, I'm trying to. Okay, sure. Okay.
Red Maelstrom: Is the output reset for you?
Ruminative Pterodactyl: No. Should I reset from my end?
Red Maelstrom: Sure.
Ruminative Pterodactyl: I'm not able to do anything here. Is it like locked?
Red Maelstrom: No worries. I don't know. Yeah, this is the first time I'm experiencing this. But yeah. Anyway, we're close to 45 minutes mark, so let's pause for a feedback. I think you did well that you went through an example to make sure that you understood the problem. You also walked me through what are your thought process about why this is the answer for first example and then only you went ahead and thought about solutioning it. And the first statement was this would be modeled as a graph problem. So I really like the way you articulated the solution. You not only just think in silos and try to keep thinking about sharing the end result, but you were keeping me in a loop during the process of coming for the solution. So that was a good sign as an SD one. So I don't see most of the SD ones doing that. They get a code out. But yeah, on the communication threat you did a lot better than expected. Basically. Next thing I liked about overall thing was even when you were moving in the wrong direction, you are calm and patient. You're still trying to get an input from my side which shows that you are receptive to feedback, which is one important aspect I look for junior engineers. You clarified, like, it's okay to assume that if there is only one source and one target, which was a good question. Your approach was good. Approach was on target. I think your time complexity analysis was off because it's not just about the routes.
Ruminative Pterodactyl: Right.
Red Maelstrom: You mentioned time complexity with respect to number of routes, but the bus stops within the route are also important aspect of your approach.
Ruminative Pterodactyl: Right.
Red Maelstrom: Because you are iterating through the stops also.
Ruminative Pterodactyl: Yeah.
Red Maelstrom: That is one thing which could have been done better. I think another thing which was good is like you mentioned while writing the pseudocode that you would be using state data structure to keep visited nodes, which was again a good communication and right data structure choice encoding. I like the way you use an aiming convention for methods. They were quite intuitive. And you wrote a modular code again, which is very rare when I interview for SD ones or even SD two s. So overall, I would have definitely been confident about giving a higher call based on this performance. Yeah, I know it's a working close to working thing. There might be some glitch in the implementation, but yeah, this was a good code. At the end of it. We took some time to come to the solution approach, you took more time relatively. You took less time to convert into the working code. So yeah, you should be happy with this performance. Would have been an interview I had taken, would have been a high call.
Ruminative Pterodactyl: Awesome. Thank you. Can you discuss a little bit more, how should I improve in giving the complexities? Because this is something that I always do that I talk about the complexity because before coding, but again, as you mentioned that obviously after your input, I thought that I have to be better in giving the complexity. So how can I improve my performance? Like what points should I keep in mind and what should I say in an interview? So it should not be like a negative point for me.
Red Maelstrom: I think the timing is right. You should share the complexity before implementation only because if you don't do that, you might implement suboptimal problem which might not be acceptable and you will lose interview time. In that in terms of complexity, look at the input parameters.
Ruminative Pterodactyl: Right.
Red Maelstrom: Though the source and target are constant, right. Variable thing, as you pointed out, is number of routes are. But at the same time, how many bus stops within each route are. That was the one parameter which you missed totally while analyzing the complexity of your approach. So just try to spend some time about what are the dimension or different aspects which will vary in a length in terms of input and try to use those to find out the complexity dimension array. It would have made sense, but I think somehow in your mind it was like it's one parameter. So I already using the size of it.
Ruminative Pterodactyl: Here, the time complex. Sorry, go ahead. Yeah.
Red Maelstrom: So here the time complexity would be in terms of total number of nodes to build a graph, total number of bus stops across the routes, and then in order to go through plus the number of nodes while traversing from BFS, it's a combination of both of these parameters.
Ruminative Pterodactyl: So routes and buses. Okay, got it. Cool. Yeah. Thank you. Yeah.
Red Maelstrom: Do you have any other question for me?
Ruminative Pterodactyl: No, I'm just like, have you ever had a chance to? But initially, you said that you had a chance to work with Microsoft, right?
Red Maelstrom: No, I never worked with Microsoft, but I did interviewed with them three years back. But I also realized that Microsoft hiring is very team specific. They don't have generic format across teams or across. Because I have friends who have been giving interviews in Microsoft and currently working in also currently working in Microsoft. So their experience is varied because they applied in different. So yeah, no generic format for Microsoft interviews. That's what my understanding even when I gave.
Ruminative Pterodactyl: Yeah. Awesome. Is there anything else for me?
Red Maelstrom: Are you a university graduate applying for university higher role?
Ruminative Pterodactyl: No, actually I was working at a company and I was reached out by a recruiter, basically a talent sourcer and they told me that there is a hiring event in Microsoft and that's for SD one role. So that's why I got to know that it's like SD one role. But yeah, I don't have a specific level in mindset right now. I just want to go and interview.
Red Maelstrom: So basically if you have industry excellence, be prepared to talk about your current project in your last round. I don't think like initial rounds will discuss about that. If it is a hiring event, mostly the last round would be with a hiring manager they call a. Yeah, that guy would dwell upon your current project and your interest in technologies.
Ruminative Pterodactyl: Okay, so basically I talked to the recruiter and he said that right now. It's for everyone and mostly like back ends till now, whatever the internships and experience that I have is on front end. Basically. Mostly if there are requirement I have worked on the back end, but mostly it's on the front end focus. So will that be an issue in this process? Because obviously I did my bachelor's and master's and I have worked with back end technologies but I have not have field experience. So will that be a negative mark?
Red Maelstrom: No, you haven't been lying. The only thing is you shouldn't lie on resume and get caught later. So if you have already clarified that if your receiver already mentioned that you predominantly work in front end, I don't think that's an issue. For one position it is expected that there would be some learning curve. So even during the onboarding part there won't be much hiccups.
Ruminative Pterodactyl: Okay. Got it. Yeah. I have done some preparations, I guess I got maybe a couple of weeks, but I just. Interviews get. You get nervous. Yeah.
Red Maelstrom: So you can search on Google like bus routes, lead code. You will find this problem, try to submit code and debug it so that you get implementation.
Ruminative Pterodactyl: Yeah, I'll surely do that.
Red Maelstrom: Cool. Awesome. All the best for your actual interviews.
Ruminative Pterodactyl: Thank you so much. Thank you for your time. You've made me really comfortable, so it was like you were great as an interview. So thank you.
Red Maelstrom: My pleasure. Bye bye.
Ruminative Pterodactyl: Thank you. Bye.
We know exactly what to do and say to get the company, title, and salary you want.
Interview prep and job hunting are chaos and pain. We can help. Really.
