Java Interview with a FAANG engineer

Watch someone solve the reconstruct itinerary 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

Reconstruct Itinerary

Interview question

You are given a list of airline tickets where tickets[i] = [fromi, toi] represent the departure and the arrival airports of one flight. Reconstruct the itinerary in order and return it.

Interview Feedback

Feedback about Wandering Nougat (the interviewee)

Advance this person to the next round?
Thumbs up
How were their technical skills?
How was their problem solving ability?
What about their communication ability?
Overall Feedback: *Inclined to Hire* - Strong knowledge of both data structures and algorithms - Was able to quickly identify the optimal DFS solution as well as the helper data structures to use for this problem - Nice use of TreeMap to handle the lexical order sorting - Very good mastery of language of choice - Strong knowledge of available data structures Things to keep doing: - Very good communication, talked through the problem fully before getting into the code. Great job of explaining thought process as you were coding Things to improve: - Try to work on catching a few of those edge cases up front before getting into the code. I think overall you did a good job of coming up with a solution before coding, but doing a dry run of the code might have helped.

Feedback about Recursive Werewolf (the interviewer)

Would you want to work with this person?
Thumbs up
How excited would you be to work with them?
How good were the questions?
How helpful was your interviewer in guiding you to the solution(s)?

Interview Transcript

Recursive Werewolf: okay, can you hear me okay? Wandering Nougat: Yeah. Recursive Werewolf: Okay, great. I switched over to phone. So yeah, great to be here today. My name is Brandon. I'm currently a software engineer full stack. I'll be doing your interviews here today. We're gonna start off with a few questions that just helped me determine what to ask here and how to grade. How much experience do you have? Wandering Nougat: I have 3-4 years of experience technically like one year or two years experience in India in my home country and one and a half years here in US. Recursive Werewolf: Okay, so are you going for like mid level positions or senior? Wandering Nougat: Yeah, mid level SD 2 Recursive Werewolf: Mid level, okay. And then are there any specific companies that you're targeting? Wandering Nougat: Yeah, mostly FAANG, Amazon, yeah for now. Recursive Werewolf: Okay cool, ya no that that helps a lot. So in the top right corner of the screen, you'll see a drop down to select your preferred language so you can go ahead and select that. Wandering Nougat: Yeah. Recursive Werewolf: Cool and then let me grab, you said Amazon? Wandering Nougat: Yeah. Recursive Werewolf: Okay, I actually just interviewed there so I can give you the question I got let me let me find it. Wandering Nougat: You did for mid level or senior level? Recursive Werewolf: Yeah, what do you say? Wandering Nougat: You did the interview for mid level or senior level position. Recursive Werewolf: Yeah, I just interviewed as SDE 2 there actually. So I can give you this. So this is definitely on the harder side of things. If this one you think is just too tough to do right now just let me know and we'll ask another one I don't want I want to use your time the best so let's see here's what we have. Let me think of how to, some examples here. Wandering Nougat: [Reading question quietly]. Okay so this is sort of okay we are given multiple stops. So the first glance of it gives me that it's a sort of data structure, which is probably hinting the towards doing some search on the input. So what searches like what I'm going to do is what like that's my first thought is what it's saying is it's given a bunch of start and end stops. And JFK is my starting stop and I need to sort of. So what's the is there an ending stop in this? So like, if given the JFK is my starting stop, so itinerary means it has to visit all the places? Recursive Werewolf: Yeah, so it should visit all the places in there. And there will be at least one valid option. So you're going to use all the inputs. So you can see the first one there is four. So your output array should be size of however many tuples were in the input plus one. So like here, you can see for line 36, we have four input pairs. So we're going to have our output is going to have five. Wandering Nougat: Hello? Recursive Werewolf: Yeah. Wandering Nougat: Yeah I'm also dialled in from home, I don't know, there was some internet issues on my side as well. So Recursive Werewolf: Okay, yeah. So you're talking about kind of the, you don't know the start and end, that's kind of what you're figuring out. We can see here, the input here, first one on line 36, we have four pairs. So we know our output is going to have five numbers or five members. Wandering Nougat: Correct. So what I'm trying to think about is like I need I have a starting point, JFK, what I'm going to do is, basically, I just need to find a path from one starting point. And I don't know the ending point, but ending point is going to be, which covers all stops. Now, here, what I think is that let's create a map of the input and take my starting point as JFK. And try to find the next stop. Now, which is MUC. Now from MUC, I'm going to find the next stopp, which is LHR. Like, obviously, the map will give you that input from LHR. What's the next stop, SFO and from SFO, it gives me the next stop is San Jose. Now there, so it's a sort of what I'm thinking is doing the DFS on the input, and then my backtrack from locations which I've already visited, or probably I'm stuck, I'm back in the same same same airport. Basically, I need to find a path, which is a valid path covering all the stops, there can be multiple paths. What it is saying is you have to return the return the one which has the smallest lexical order. I think that's Recursive Werewolf: Exactly yeah like a order. Yeah so that's going to be kind of the tricky part here. Wandering Nougat: Yeah, that's what I'm thinking about. Because the mapping is single. And like, obviously, the map can have multiple paths. You store one path, then if you go to the other path, you see whether you have already smaller path there. Yeah, I'm just trying to think how can I do that? Just give me some time. So let me okay, that's the first example. If I take the second input, what it is saying is, if input is the starting point is JFK. So there are so if you see there's multiple from there multiple flights from JFK one is to SFO one is to Atlanta. Now If I go the SFO route. I go to but I need to take the Atlanta route because as a is smaller lexical order than SFO. So I believe I can take that. If that's what I'm thinking right now. I'm not sure if that's the valid answer. So JFK to Atlanta, then Atlanta to, Atlanta to SFO or SFO, but from SFO I can't. In the second it says there are multiple stops. So what's the I'm just trying to understand the end goal whether we need two airports multiple times as well. Recursive Werewolf: Yeah, you could visit an airport multiple times. So like here, you kind of have these loops between JFK SFO and Atlanta. But you can you can go to the same place twice. Um, you just don't want to use the same pair twice. If that makes sense. Wandering Nougat: Okay got it. Okay. Recursive Werewolf: So if you can keep track of like, some somehow there according to the pair, because you could have like to like see, you could have two pairs that are in there twice. If you were to do like a full circular rotation. Wandering Nougat: Makes sense. Okay, okay. Give me you're just trying to think how would to solve that problem because I know that it's a normal DFS backbreaking problems, when I'm trying to gauge into that, how can I solve this multiple stops? And how to stop my backtracking where and how. Now the main question is how do I [ineligble]? But basically what I'm thinking is like, that's my way of thinking. So what's happening is I'm going to create a map of that this is graph data structure. Now, if you take the second input, I'm going to start a DFS from the JFK as a string, like that's the airport and try to find the next stop for that. Now the next stop for JFK, in the second input is Atlanta and SFO. I'm gonna pick Atlanta first, because that's, that's, it's, it's smaller in lexicographical order. Go Atlanta and the next up from Atlanta, JFK, and SFO from there as well. And while I'm doing that, I'm going to keep the the routes that have already been reversed, it means JFK to Atlanta has been traversed. I'm going to keep a string JFK dash Atlanta, to to JFK dash Atlanta to properly marked as done so I'm not going to take that route again. Now. Yeah. Because that, can we route again? Or it's just one? That's what I'm, I think it's one. Recursive Werewolf: You can only use each pair once. But you could have like to duplicate pairs from there. Wandering Nougat: Okay, I can have wto duplicate pairs. So basically, I need to store the counts as well for that. So okay that's what i'm thinking. Recursive Werewolf: Yeah, I guess that could work. Or you could just mark each one visited. As you kind of go, just whatever you think will work to handle that. Wandering Nougat: Yeah, so I think I can do that probably count, marking each one is visited out there, and maybe taking an index value or something like that can be helpful. So I believe, what I'm going to do is just create a map first, for this, which is going to be graph data structure, which I'm going to use that graph is actually to do a DFS on that particular data structure. And then once while doing DFS, I'm gonna find that route, and backtrack from all the paths which are not value paths. And then once my DFS finished and all the, all the all the things are exhausted, then I'm gonna return my output. Like that's what I'm thinking to go with this problem. Recursive Werewolf: Yeah I think at a high level, but yeah, that sounds pretty good if you want to start implementing. Wandering Nougat: Yeah sure. So this is my current solution. Let me take another basically another function which is basically is returning I see that input, output is a list of strings and that's going to be a list of strings. Create liking. Sorry for spelling anything wrong. Okay create itinerary I'm just gonna do that. And what it's taking is basically it's taking the list of string. And this is the input and to length okay, that's a constant thing. Okay, now what I'm going to do is let's create the first thing is the result which I'm going to return as binary. I'm gonna just make this the error code. So I'm gonna create a map basically which is have a string and a list like from starting source position to multiple position so that's gonna be a hash map. Now I'm gonna iterate over my string and code and probably get. I'm just gunna think how can I keep count just give me one second. So I have a list of strings and iterate and do DFS with that. How will that map be traversed? Recursive Werewolf: Sorry have you been typing? I'm just taking notes here for feedback. But yeah, no worries. Wandering Nougat: Yeah. I'm just trying to think how can I keep that count thing. I need to just keep that is there are multiple pairs, like JFK to SFO or multiple times, I'm just trying to think, should I keep the count? How do I do that? Because this is all I can do, I think this. So once you have this map string to, so like this, so this will give you basically that how much time it occurred in that particular thing. So now I'm going to iterate over my string, and that input. So that's gonna be, that's going to be my list of string by grid over flights, so this basically is a list of a list of strings like this, this thing and MEC. So it's going to check if this if my graph dot contains that particular thing. Then obviously, it's gonna get that basically it's gonna get that entry. Okay, this is yeah. And now, I have that entry. Now I'm going to do this entry dot put, entry dot get while it's going to be entry dot get. One second it's going to be okay. Just give me one second okay, it has this map now entry dot get. The other one, so this dot get one. That's the second round of that. Now so now it has occurred second time we'll do while plus plus while plus equals one basically and just put it back there so list dot get one comma while. And then it's going to be graph dot put. Technically, it's gonna get that entry only because it's a reference there. So now the key if the key doesn't exist, so if you could just create a new key basically so what I'm gonna do is just graph dot put list dot get zero and then new HashMap and what you do is you createan instance of a HashMap basically. String integer, map route is new route. I think I don't need this let do this directory so that I can test input directly. This dot get 1 dot 1 and graph dot put and this dot get zero slash my map route. Okay, this is done. This will basically create a graph now process the input now what I'm going to do is start the DFS, I'm gonna write another function which is going to be a DFS and just create that particular route. So what I'm going is do DFS which is going to take input input is going to be this graph basically. So that's going to be this graph and I'm just trying to and it has this as well because it's gonna input into probably the result with whatever it is. So Recursive Werewolf: That makes sense Wandering Nougat: I'm going to correct this later, this is my graph and then this is my list of integer. Recursive Werewolf: I think that's string right? Wandering Nougat: Oh, sorry. Yeah that's right. Correct, that should be string correct yeah. So now, this also needs to take sort of the source string, basically, JFK. So that sort of the start string we just take, I know everything needs to start from JFK and wanted to pass it like this. Now, what it's going to do is get all the mappings of JFK and try to find them. One. So I think one thing I can do here is if I use this as a tree map, all this key entries will be lexicographically sorted. So basically Recursive Werewolf: Oh I see that makes sense okay. Wandering Nougat: Yes. So yeah, I'm just trying to make it more easy, because what it will do is basically just make it so this is gonna be tree map. Yeah. And what it is, is causing issues, why? One second. I'll check this out later. So let's start with so we have tree map already. Now what I'm gonna do is, so it says my start thing. So I'm just trying to understand now, what was going to be my ending point here, ending point means when I should stop the DFS, and return the result, so technically Recursive Werewolf: Yeah so once you have everything out of that array, or everything visited, then you know, because you've learned we can assume you we have at least one valid path Wandering Nougat: Correct. So what I'm going to do is I'm going to delete entries from side by side. So once my map is empty, I know that it's fine. So what I'm going to do is result dot add start. So that's going to my starting point. Now, if there's going to be sort of ending point now if see that graph dot is empty, so I think this gives you that if HashMap is empty, then basically you return that result. Not return there's obviously just return. So it's gonna populate it from the function as well. So graph dot is empty, it's going to return from there directly. I'm just trying to think now what I'm going to do is now the next start is get all the entries for the graph, dot get start. Graphs dot get start. So this is this will give me all the route from JFK basically the first map route. Now I need to, now obviously, this is all already a sorted order, which when I need to iterate over this particular route, so I create over this map dot entry, which is going to be string comma integer. Entry is map route dot entry set. In this entry, now I need to call this DFS function back again, with all these entries, whichever available, so what I'm going to do is call this DFS function again. Now, whenever I'm calling a different function, again, I'm going to remove the, the entry part and add it back later. So from from this map, which is map route, basically, I'm gonna remove, not remove basically just reduce that instance, from that particular map. So technically, what I'm going to do is int val is equal to entry dot get value. Yes and if val is equal equal to one, directly remove that, because that's already gone.Map routes dot remove. What I need to remove the entry dot get. And there can be one issue, I believe in this content modification, I believe or I'm not sure. So we are actually editing of the map and modifying the map as well correctly. So it can give concurrent modification is what I'm doing is now you can just directly call the DFS function. And you can put this value back after this. So technically, you're just gunna go graph, result and the next starting point is going to be my entry dot get key. That's the next route that you need to take. And what it does is basically put that entry in the map back, I believe, let me think about it. Recursive Werewolf: Okay, yeah, I'm a little, I think I'm just not following. But um, yeah, let's see. Wandering Nougat: Yeah, so what I'm doing is basically just iterating over all the, so from JFK that these are from, let's say, from any point. Now, these i'm going to be iterate over all these routes and pick the first one. The first one is, it's a tree map. So it's already sorted. It's in lexicographical order. What it's going to do is there can be multiple, SFO can be there with two flights from JFK to SFO. So it's gonna, if it's only one entry, it's gonna just remove that from the map. So it been used current, the current DFS call, and it's going to make that DFS call. Otherwise, it's going to just reduce that by one so that when it gets passed in the next DFS call this graph is basically used there. Recursive Werewolf: Yeah I see, that makes sense. Wandering Nougat: Yeah, it's a little tough. So I can do this visited as well. But it's gonna, I'm just trying to think if I change it to visited, because now once this DFS call finishes, basically, what we need to do is put that thing back to what it was, like restore the map, basically, because it needs to go to other parts as well. So just give me one second to think about that. So let's, so when it's goes back, it's gonna put it, entry dot get comma one. And otherwise it's gunna do plus one, basically. Cool. So this is how the backtracking will happen. And I think once we have exhausted it means they're going to be. I'm just trying to think how that graph where I'm deleting that graph thing. So basically, I need to delete entries somehow just give me two minutes to think about it. But yeah, it's a sort of this code structure do you have any doubts in this like anything? I know there are still problems i'm trying to figure out but Recursive Werewolf: Yeah, I think at a high level this looks good. Yeah, these are a little hard to follow but I think that's fine. I think you have some errors up above like is this just supposed to be Treemap because it says your put can't, it's not applicable for those arguments. On line 41. Wandering Nougat: Because this is why I'm creating a tree map here. String integer right now I created tree map here. On line 43 I think it's giving issue because what it is doing is graph is a graph is string to tree map. Yeah, that's true. So one thing I can do is basically maybe that can be that can solve the issue I believe because I think usually in java it doesn't come but. Okay, now. One second what it says. Yeah, the value is a map then why it's, graph, graph dot put, list dot get zero. The first one in map route is a tree map which I'm putting it back in. So why it's giving an issue, let's doing this thing and I don't know usually it takes this. Yeah it solves now but this should this never comes in Java, this ID is different and normal ID this because it takes an abstract class as well so yeah now that problem solved. Yeah so the graph solution exists and what we are doing is basically... Sorry this should be. Okay yeah now there are no errors in the code. Now what I'm going to do is I've solved all the errors now just going to go into each entry. Now the one thing that is left is so whatevers happening is this condition where we're doing graph is empty return. Now there is no way this code is deleting that entry from the graph. So it has to delete that entry from the graph, it means it has to see that when from when all the routes from JFK have been exhausted, I need to remove that entry from the graph map basically. Now how do I check that as when I didn't here, basically when you see our particular string you see that if value is equal to zero already and then. Okay, if val is equal equal to 0. I'm going to do for that particular value is zero I'm gonna delete that entry so basically graph dot remove. Graph dot get, start dot remove basically. Which is entry dot get key. And continue to the next entries. So this should solve the problem, every time we see that we now at one point of time all the entries will be exhausted and it will return from here then result will have desired paths and finally return the result there. Recursive Werewolf: Okay, um yeah, yeah, this looks pretty good here. Do you want to write some driver code so we can see see if this works? Wandering Nougat: Yeah let me do that so I'm going to read the solution. Recursive Werewolf: Whatever's just in main gets called here because you're already in solution. Wandering Nougat: Oh, yeah. But I need to Recursive Werewolf: The method will be called automatically. Wandering Nougat: No no, I need to sort of, I need to call the function in this main class only because main will be called you have to either you can make it static but you have to create an object of this class solution. Object of this class solution we'll call this so that's what I was doing. So I need Recursive Werewolf: Yeah, yeah, I guess if it's not static that makes sense. Okay. Wandering Nougat: Yeah. So that so I'm just gonna copy these two things. It will take time to create input so give me just one second, list of integer. Could do, I think I can do that? And Recursive Werewolf: I think did you mean to do strings not integer Wandering Nougat: Oh, sorry. I always do that mistake with string. Recursive Werewolf: All good. Wandering Nougat: Yeah. One second I just again, just copy these things so that I can easily. Ok now and this is done so lets do that. What I'm gonna do is call this function we're just gonna take this list it's gonna get done. Okay I can, now it looks good it might give some error. Okay so let's try to run this see what it says, it's in sixty five. Let me just debug some things here. It says the input is sort of empty, lets see whats the size of the graph, it's full so it means your four values are there but the problem might be graph. Yeah, all entries are there it's one entry. Line 66 where is this one. So I think one thing anyways, yeah, it's working. You see Oh, sorry. So this is the route so let's see what's the output JFK, MUC, LHR, SFO. Yeah, this is the final output. So this is output. Recursive Werewolf: Okay, ya no that, that looks good. And then yeah, I think by using the tree map you're handling the lexical order. So that should make sense. Wandering Nougat: Let me try this for the second input, let me copy this here. Recursive Werewolf: So let's say it's, I'm going to just take two minutes. JFK to ATL, SFO to ATL, one is ATL to JFK, ATL to JFK we need another one basically here. Which is going to be list five and so that's going to be the ATL to SFO basically and now thats them so that's what they're going to run. Okay, so what's the issue with the, so it's given at 63 Okay, okay. Okay. I can do this in planning basically. But I think it's a Java thing. A primitive error non primitive it's a non primitive that's why it's causing. So I'm just trying to understand in 60 Wandering Nougat: Somehow you're getting null in the map when you try to get it here it looks like, but which one is null is it the inner or the outer. Recursive Werewolf: Yeah, basically what I can do is well, so its just to check I'm pulling it. Okay, so let's try doing this. Just handing null check. Okay, so this is the output I think it's not correct, JFK SFO ATL and JFK. Yeah, so Oh, I think so what the problem is with the code, I believe, is that that count in which I'm putting it's not getting enacted in the code, so there has to be something so it is just getting values one time and it stops at JFK. Why it is stopping at JFK? It finds the graph is empty why? I'm just trying to understand that? Wandering Nougat: Yeah, let's see. Recursive Werewolf: Okay, I think okay you get this graph it contains get zero Wandering Nougat: I think the issue here is that you have multiple JFK's whereas the first one you didn't. Recursive Werewolf: Yeah. I'm just taking this when i'm putting these values here. So whether that is happening or not. So, okay, so now I think I got it what I'm trying to, what the issue is so basically we have to do graph dot put [ineligble]. I think this should get that because it was not updating the map, either it's a reference, it should get updated but I'm not sure why? Technically it should be, yeah. Yeah, the one thing is, I think is the only problem with the code is I believe I think the map is not keeping track taking care of the count thing where multiple JFKs or SFOs are there. So I believe that's going to be problem where we are constructing the map and constructing the graph. But I don't find a problem here. And Wandering Nougat: yeah, I'm not sure exactly where it is, either. But I, I see. Yeah something with those multiple lists there. Recursive Werewolf: Correct yeah. But mainly because once I solve that count problem, I think it should work because because the right now it's working. It's only technically just getting that one value. So I think it's not going inside test and see if it's going inside test or not. Because this is what it updates. Yes, it's going inside. So it's going twice inside it means there are two values which are repeating. So JFK is repeating, JFK to SFO and SFO and yeah. So JFK and ATL are two which are the maps which are oh, okay. So this is working fine it means it's going into the code this code is updating because it's printing this inside two or twice for JFK and ATL which are repeating, which is the flights repeating. And it gets this entry contains it checks. I think I got it what the issue is. Just give me one minute I'll just solve the problem, one, one minute, one minute. Wandering Nougat: Got it. Got it. Got it. Got it. Was that some mapping there? Okay, okay now, the issue is? Recursive Werewolf: Yeah, I got it. So now that once I solved this problem, because I was not getting the entry. Now it's giving, I assumed that it will give this concurrent modification exception when multiple entries are there. So we're trying to modify when you loop over a map, you can't modify the map. Basically, that's what I was doing. So I think why keeping a separate visited array or something that will solve this problem? Technically. Wandering Nougat: Oh that's interesting that you can't modify. Okay, that makes sense. Recursive Werewolf: You see where what I'm doing is for map entry. So this is in Java whenever you're iterating over even if you're iterating over an array, you can only get get values from that, you can't set. So that's, that's why it's called concurrent modification exception that you are iterating over it and modifying that so you get a copy and that's what you do it,. technically. Wandering Nougat: That makes sense, okay. Recursive Werewolf: Yeah, in terms of I think the time complexity for this is going to be what is for DFS order of technically it's order of words as you said, the word is just defined as this JFK to SFO is the edge and the number of nodes or vertices, like number of unique strings. So that's going to be that plus n plus and if I zoom n is that number, and n is the number of edges. So time complexity is going to be that for a particular case, and returning space complexity, obviously, it's O(N) because the number of edges which are there. Wandering Nougat: Yeah, no, I think that makes sense here. Yeah, this is a pretty good, pretty good algorithm there. Okay, cool. Yeah. So we're pretty much at time there, then. I'll give you some time back here. Is there anything? Any questions that you wanted to ask me or anything? Recursive Werewolf: Yeah. You said, you've got this question at Amazon. So were they expecting full solution? Or were you able to do it? How's it? Wandering Nougat: So the one I had was very, very similar. Just I don't have the full prompt. But yeah, this I did have to get a full solution, or I did at least but it I, you can't run your code in their IDE. So it was just kind of, I might have had a few errors there. You know, but they don't they don't run it. So I think like what you had would have been fine. You had it at a very high level. It's more about the problem solving. Yeah, so I think that's fine. Recursive Werewolf: Okay, cool. Wandering Nougat: Then there's another one, if you want to look it up for after it's called trapping rainwater, you'll find it on leetcode. That was also one I was asked as well, or the modification of that, but similar. Recursive Werewolf: Makes sense. So that was like which team you gave an interview for? Wandering Nougat: I am still finalising things with offers, but I'll probably be joining AWS or amplify. And I'm more of a front end position. But they still like to ask these questions for that. Recursive Werewolf: Make sense, okay. Okay, yeah, for and for I think they have four rounds or third round. For one of the rounds they ask low level design. And I think I don't how many. Wandering Nougat: Yeah, exactly. Yeah. So you also use a system design too. For Amazon, I highly recommend just brushing up on the behaviourals as well. They really drill you on those leadership principles. So just make sure you have those fresh. Recursive Werewolf: Yeah. Yeah. Wandering Nougat: Like I said, I'm happy to help. I just did a Google, Amazon, Snapchat. Like the whole loop. So happy to help there. Recursive Werewolf: Yeah, I think I am looking over that. I'm making stories right now. Lighting for that as well. Wandering Nougat: Okay, cool. But yeah, so yeah, I'll leave you with that then. Yeah, anything else last minute or? Recursive Werewolf: No, I think that's all. Thank you. Thank you for your time. Thank you for taking the interview. Wandering Nougat: Yeah, no problem. Thanks so much. And yeah, so you'll get some opportunity to leave feedback here. Appreciate whatever you have and have a good night. Recursive Werewolf: Yeah, sure. Thank you.
Ready to practice with a mock interview?

Book mock interviews with engineers from Google, Facebook, Amazon, or other top companies. Get detailed feedback on exactly what you need to work on. Everything is fully anonymous.