Python Interview with a Google engineer

Watch someone solve the partition array and public transportation problem in an interview with a Google engineer and see the feedback their interviewer left them. Explore this problem and others in our library of interview replays.

Interview Summary

Problem type

Partition array and public transportation

Interview question

1) Check whether it is possible to partition an array. 2) Is there a way to get from one city to the other with the given bus routes?

Interview Feedback

Feedback about Rocket Tiger (the interviewee)

Advance this person to the next round?

Yes

How were their technical skills?

4/4

How was their problem solving ability?

4/4

What about their communication ability?

4/4

Very good overall. Was able to identify a viable algorithm very quickly for pretty hard problems. Could probably improve by articulating at a higher level how the technique works. For example with DP, explain how the lookup table saves calculations vs a recursive approach. Also, take the liberty to shape your inputs how you want it (unless its a constraint of the question). For instance, with the bus problem, just declare that you are expecting input cities 0 - n if that makes life easier.

Feedback about Electric Burrito (the interviewer)

Would you want to work with this person?

Yes

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

I really appreciated the questions and thought you were a great interviewer. I also really enjoyed your active participation and enthusiasm as we went through the code and discussed ideas throughout the process.

Interview Transcript

Electric Burrito: Hello.

Rocket Tiger: Hi.

Electric Burrito: How's it going?

Rocket Tiger: Hello?

Electric Burrito: Can you hear me?

Rocket Tiger: Yeah I can hear you now.

Electric Burrito: Okay well uh so um are you ready to interview?

Rocket Tiger: Yeah go for it.

Electric Burrito: Um okay so I presume you're going to be using Python 3.

Rocket Tiger: Yeah.

Electric Burrito: And so how long have you been... are you currently not like working? Are you um are you just like a recent graduate or have you been working as a developer?

Rocket Tiger: Yeah so to give you a little bit of my background I've been working since graduation and that graduation was in spring, so I'm pretty much a new grad. So graduating 2018 spring, started around September, and using interview.io...

Electric Burrito: So did you study computer science?

Rocket Tiger: Did I what?

Electric Burrito: Was your degree in computer science?

Rocket Tiger: Oh so my degree was in chemical engineering with a minor in computer science.

Electric Burrito: Okay cool um. All right well on that note I think I'll start by asking a question.

Rocket Tiger: Um all right, sounds good.

Electric Burrito: Hmm let's see... um okay so um this question, so I have this this tree structure, and every element in this tree structure can be either an operation like plus minus. It's actually going to be one of four operations: plus, minus, multiplication, division. And so every node can be a operation or it can be an integer so... um and I want to find the result. Yeah evaluate this expression so like as an example like the tree that looks like this, like four and five, would return twenty. And then so times four and five, and then maybe like one minus... ah yeah it shouldn't matter one minus... lets see 2 - 1 ah so actually minus two, one. Okay so I might wanna space this out a little better.

Rocket Tiger: Yeah, I think it would be much clearer if I can figure out like who is the parent and child, okay.

Electric Burrito: Yeah yeah, so like that kind of thing. This one would be 4 times 1.

Rocket Tiger: Wait so there is one the child of the minus or who is that?

Electric Burrito: Wait but uh how does this work, hold on. I've asked this question before, I don't know why... uh okay scratch this question. I thought I knew this a little better, I don't know it. Okay here's a much easier question to understand and for me to understand actually. So you have this like two dimensional matrix and in it there are... say there are colors, so like there can be like three colors like red blue green and every entry in this two-dimensional matrix is a color and you want to find the biggest degree of colors that are touching each other. So let me see if I can draw out a matrix like that. So in this matrix, I guess blue there's five that are like continuous and touching so um you would return the color that is uh, that constitutes the biggest group.

Rocket Tiger: Yes that's fair. So there's two ways you can do this. One is union-find, and with union-find you have like a dictionary and whatever you join it, you just add up the sizes of two groups that you're joining. The other one is the depth-first search where you for each node, and you would mark each node after you visit in the depth first search, but you basically just go through and like each time that you see one of the same color, add one and visit that one, and just recursively visit all its neighbors. So we can do either, but those are to my knowledge...

Electric Burrito: Have you seen this one before?

Rocket Tiger: So full discussion I've probably seen like 750 Leetcode questions at this point in the last four months.

Electric Burrito: Oh my god.

Rocket Tiger: Yeah yeah I have on site with like Google on Monday and so I've been prepping like crazy.

Electric Burrito: Oh well that's uh incredible then hmm.

Rocket Tiger: Oh yeah also for your binary search question... your binary tree question earlier I think would be like divide and conquer right, like you'd evaluate the left side of tree, evaluate the right side of tree, do whatever is... then return it.

Electric Burrito: Okay cool so maybe I'll find a more difficult question let me think um... I'm sorry, what did you say?

Rocket Tiger: I don't know if I dug myself into a hole now cuz I don't I don't know if I want a super hard one.

Electric Burrito: I mean if you, if you're not getting challenged then there's no point so... okay um let me think um... how does it do this? Sorry I'm just looking some questions I've written the solution to and trying to figure out if I can re-ask that same question. Hmm okay here's a good one... so you have an array of random integers and you want to partition this array into... you were wondering if you can partition this array such that the sum of the left elements is equal to the sum of the right elements. So let me write that out. Have you heard this one before?

Rocket Tiger: I have not.

Electric Burrito: Okay... So this one's easy to partition because you can just put a partition between three and one and two, so the left and right side are equal. And then you can also have any arrangement so... This is also true. But then something like this is false.

Rocket Tiger: Okay.

Electric Burrito: So I'm going to write the solution for the second one here. It's going to be the same as the first one. It's just called a function partition.

Rocket Tiger: Hmm let's see... So it's kinda interesting. This is definitely one I have not seen before so there might be a dynamic programming way of doing it, otherwise I wonder if we... so dynamic programming would probably be a more complicated way of doing it and I think there is a way. But I think that hopefully there's a simpler solution and without dynamic programming.

Electric Burrito: Mmm-hmm.

Rocket Tiger: So let's run through a couple examples. I wonder if it would help... so there can be multiple of a number like there's negatives and positives right, so it's basically going through whatever arrangements of whatever numbers you have right?

Electric Burrito: Mm-hmm. So just presume they're all positive if it makes it simpler.

Rocket Tiger: Let's see... so let me see if sorting gets us anywhere, so if I sort this one, I end up with a two, two, three, three, and four. Okay so now that I have this, can I figure out whether it's possible?

Electric Burrito: So I think you're uh... actually I don't know how to solve this without dynamic programming.

Rocket Tiger: Okay fair.

Electric Burrito: Ha ha ha maybe if you were exploring that route. Another way I guess... yeah okay I don't want to interrupt you, I'm sure it is possible to do it without dynamic programming because you would just explore all possibilities multiple times, so...

Rocket Tiger: Yeah yeah that'd be super expensive um so yeah.

Electric Burrito: Which is fine if you do it that way too, I don't really care.

Rocket Tiger: All right yeah we can try that in like a worst case, but I feel like the dynamic programming would be more interesting just to try out, so let's say if we're gonna have dynamic programming solution, it would probably... we would start off... let's see how do we want to frame the dynamic... I'm trying to think of the recursive relationship that you want to have because you probably start with a base case and then you'd like incrementally add each number and then sort of evaluate it and compare it to what you've already done, like your sub problem. And so I'm trying to think what would be the ideal base case. So say let's say the different look... So you start off with the... say initially you process... how do we want to do this here... I think we want to have a dictionary and each dictionary is going to have a list or each dictionary will have a set. So... and this is how we would store our results and then is equal... Basically the strategy I want to use is... say we do like three one two as an example right, so when you initially start you're going to... and let's say that you have like a left and a right, right? When you initially start it you will have processed zero elements and you will have a difference on your left and right side of zero right? And now you process your first element so after one element... so now you process your three, and with your three you could either be in a three or three right? And this is... so the recursive relationship is basically if you add it to... so I guess this is the value if we're going to define that, is equal to left side partition minus right side partition.

Electric Burrito: Yeah okay.

Rocket Tiger: So this would be an example of three... well actually zero and then partition and then three right because zero minus three, I mean zero... this would be...

Electric Burrito: So the value is the difference, the imbalance.

Rocket Tiger: Exactly exactly, so it's going to be your difference and you would do that by iterating through every value in the step before, so I get to the negative three and the three by adding or subtracting three from every value in the step before, so just like zero layer and then same thing after two, so it's negative three is going to come like four, so five subtract one, it could be negative five if I add one and then for this three, it should be two or four right? And so I'm going to do this for every single step. Okay there. Apparently there's some shortcuts that uh has been added so when I hit enter they just automatically add them. At the end I'm going to look at the set for my last row and if zero is in my last set return true, otherwise return false. Does that make sense?

Electric Burrito: Yes that's great.

Rocket Tiger: All right so we ready to code this up then?

Electric Burrito: Well that's up to you, but this is looking good, this looks like the right way to go I think.

Rocket Tiger: Okay yeah I'm trying to think if there's an edge case, I mean I can tell you the run time for this is going to be... let's see the size it's actually not I think that cuz it's like 2^n. Let's see...

Electric Burrito: Well what's the max size of your... I guess you're storing these... every uh every row so to speak, you're storing these result values, so what's the maximum size of one row?

Rocket Tiger: I mean so it looks like we double each time right? So for this one we had one element and did we subtracted and added for each element before and so it grows by two, by magnitude of two, so the largest would be like 2^n, n being how many elements you have. I mean is that we're going for or are we trying to optimize it further down.

Electric Burrito: So that would actually be the the runtime of if you didn't use dynamic programming, if you just brute force every possible partition where every element can either be in the left side of the right side, then you have 2^n possibilities.

Rocket Tiger: I think if you said we brute force yeah.

Electric Burrito: So if you're doing this lookup table then the whole goal... I mean then you might encounter like some values that are repeat so you don't have to keep traversing down that that tree. So in this case it will be a little faster. I mean I'm wondering maybe you could explain how much faster it will be, like what will be the runtime if we're using this dynamic programming approach.

Rocket Tiger: So I mean the idea of this set is so for instance if we like you do step down on some on some of those branches so for instance is like a negative 2 right, because our default pick, the value is a set, you'd only go down one of these two, you wouldn't go down both of them. But that being said that's your worst case scenario with the n in case when you don't have those duplicates.

Electric Burrito: Hmm... okay I say that because actually I haven't thought about this uh really in depth so yeah so maybe you're right but I'm thinking like, let me think what am I thinking like, okay so for every row like the number of possible values you could have is at the very last row is going to be a hip spin from negative the imbalance could be... like let's sum the whole array right, so the whole sum of the array is going to be like 6, so the end, every possible value you could conceivably have is from negative 6 to positive 6, so let's call that n and then for every... you're going to do every row I guess you'll have like how many operations for every row. I'm sorry how many of these rows will you have?

Rocket Tiger: You're going to have n rows because you're evaluating each element.

Electric Burrito: Yeah so I mean I'm just guessing that it would be like in nxn size of space and then yeah runtime I don't know, maybe it is two then, but it must be faster because you're cutting off the branches..

Rocket Tiger: That's a worst-case scenario where you were inputting something and for some reason that input was tailored specifically so that you never got the same sum I don't know if that's like maybe it was like I'm a super worst case that's like definitely not average case.

Electric Burrito: Oh yeah yeah but okay yeah the reason why that can't happen is because obviously negative n to positive n is going to be much smaller than 2^n if n is like... if n is 64 and 2^n is like a huge number and then the biggest positive and negative value you could have is like just depends on the size of your max sum.

Rocket Tiger: Okay oh yeah okay yeah that makes sense that make sense okay. It's mathematically proved that you wouldn't be able to do that then. Alright cool that makes.

Electric Burrito: Um yeah I guess as you pointed out this would be like an MN space solution so I guess we can code it up then um... see so... So technically if we really want to optimize on space we actually don't need to keep the entire dictionary with all the levels because really all we care about is the current level and the level that came before it right? Because we'll never reference beyond that point. That being said, we can probably just do this for now because doesn't affect the Big O notation, but yeah, that's like a huge optimization if we really wanted to do it.

Rocket Tiger: Okay.

Electric Burrito: Okay and that looks about right to me... And that's pretty much it.

Rocket Tiger: Well okay. Cool. Wow, that's pretty cool. Uh you want to test it?

Electric Burrito: Yeah sure I'm hopeful that works but I should be able to fix if it doesn't. Um so yeah let's say...That didn't work, that's not good.

Rocket Tiger: That's fine I wonder why. S I don't know if I remember it but is it is it that the arrays start off at one or start off at zero?

Electric Burrito: Um the arrays um...?

Rocket Tiger: Like the first, sorry the first dictionary. So like when you enumerate the...

Electric Burrito: Oh that's a very good point um so it's definitely going to be zero, but that's not what we want, we want i + 1.

Rocket Tiger: Okay.

Electric Burrito: So let me yeah let me double check that, so for i element we want this to be one. We're going to change that to... I really don't want have to worry too much about the off-by-one errors each time. So yeah let's see if that works now. Okay that seems to work.

Rocket Tiger: Alright! What happens if we do this. Nothing. Does it return? Is this still running?

Electric Burrito: I think I hit at the same time as you did.

Rocket Tiger: Yeah cool wow that's great that's a lot better than than my solution.

Electric Burrito: I mean in your solution I guess like if it's longer is it more optimal?

Rocket Tiger: No, it is exactly the same algorithm. I think I just had to what, did I do I'm like making sets on I'm sorry, I really only know JavaScript, so let me see. Yeah I do exactly the same thing um. Oh in the end... No, that's pretty much exactly what I have. I'll even copy and paste it. I just had to write this like auxiliary function to... actually you might want to do that for practice like to return the actual left and right sides of the partition.

Electric Burrito: Okay.

Rocket Tiger: Because I mean knowing whether you can partition is one thing but actually having it is even better so...

Electric Burrito: Yeah yeah so the question about um actually having it, that's actually a Leetcode question and so like the reason I was able to come up with this is it's very similar to that question because the one where you return the sizes like on Leetcode, it's like a leetcode hard and yeah it's basically that, and they do a similar solution um, where it's recursive like always like yeah but it's a little bit more...

Rocket Tiger: How could you do it?

Electric Burrito: Yeah so the way you would actually do it...

Rocket Tiger: I think you can do it without even modifying what you have now you just have to add to it.

Electric Burrito: Yeah so you would modify it a little bit in the sense that, let's see... yeah so for each iteration you know it's... yeah you do have to add something, sorry.

Rocket Tiger: Yeah because you could... with this one it's like you have to also... I guess this actually is different because in the Leetcode one, you didn't have to use all the elements, but in this case I guess you have to use all the elements. If you want to like strictly partition it.

Electric Burrito: I see so in Leetcode if you hit zero at some point then you just return.

Rocket Tiger: Well the Leetcode one is return the largest sum on each side where they're equal, and so you have like a Map of the array.

Electric Burrito: Oh that is a little trickier.Okay yeah well I'm sure you can think about that. So okay now that we have a whole other 30 minutes I was just going to take advantage of this and ask you another question if that's okay. Unless you're on a time crunch.

Rocket Tiger: Oh no no, it's a more practice so I'm grateful.

Electric Burrito: Okay cool so this one um... okay so you're in this city and this city has all... you're in this country and there's a bunch of cities in this country uh like a handful of cities and then there's a public transportation system and they have bus routes and the buses go in this like circle visit like City A City B City D City F and then back to A and then there's like another bus that goes from like A to some other city and it has its own cycle and the question is so let's say I have two cities, for any given two cities, is there a way to get from one city to the next by taking public transportation.

Rocket Tiger: So it seems like that's a depth first search problem right?

Electric Burrito: Hmm I don't know. How would you do it with depth first search?

Rocket Tiger: So to get a better idea of the input, so I assumed I would be given like a list of lists right with each list within the larger list representing... so for instance if I... I don't know what input looks like but I'm imagining would look something like this right? So let's say you have two cities and so this one is going to go to city one and this one is going to go to the city here, so it would be just like a circle right? Like zero goes to one one goes back to zero right?

Electric Burrito: Okay yeah.

Rocket Tiger: Or maybe this goes to like two and then this goes three and this one goes to... I don't know back to one, right? So I'm assuming that's what the input would look like.

Electric Burrito: Wait so sorry, uh describe this again? So the first entry, just one and two is what?

Rocket Tiger: So this is saying that because this is index zero right, this is saying that city zero has a path to city 1 and city 2 right?

Electric Burrito: Oh okay okay. Oh no uh you don't have that. Sorry I should be more clear about my... I'll give some input actually. Okay so you have a bunch of buses, so bus one visits these cities, one two three.

Rocket Tiger: Okay.

Electric Burrito: Right and then bus two visits uh like three four five and then bus three visits four eight nine. Sorry yeah I'm just giving the city's number names, which you have done so. Let me see and then the next visits... I mean so far now okay yeah, it just visits seven and eleven and the question is like can you get from... if you're trying to get from city two to city eleven, can you do it?

Rocket Tiger: Oh okay so in that case this is going to be a union join problem. So what we're going to do in this case is, so this would be like one. So as a base case I guess your first iteration through each bus route, that can be one union right? Um and this is going to be a union and this is gonna be another Union... and then... oh my that's actually really um... yeah and so then you would... let's see how would you do this? That's actually kind of tricky.-

Electric Burrito: So what's wrong with the union approach?

Rocket Tiger: So the union approach is really expensive right?

Electric Burrito: Why is that so what? Tell me what your unioning and like how you're doing it a little more in detail.

Rocket Tiger: Yeah so as an initial case um... so let's see how... let's say that my parent is like the array where I'm keeping track of like what's union is in the array. So City... I guess we don't have a city Zero here in this case. But so City One Two Three. So let's say One and then...

Electric Burrito: So One, uh so parent is what exactly? It's like the root of the union?

Rocket Tiger: Like which union it's in, um like which group so...

Electric Burrito: Oh you're storing it like an array in addition.

Rocket Tiger: Yeah yeah so like that's how I usually do union join.

Electric Burrito: Okay. Oh I got it yes, yeah. Union elucidation.

Rocket Tiger: So do I want to? Maybe I shouldn't do it initially going. So initially I was gonna do it like this is gonna be one union, this is gonna be one union, this is gonna be one union, that's going to be another union. Um maybe that's not the best way to go about it. Ah actually just see so 3 4 5... Actually okay nevermind I don't think it's gonna be expensive, yeah it's not gonna be that bad. So let's see, so these are all gonna be in one set. Okay and so when I get to the next one, that gets tricky because you come across 3 4 5 it's the reason both. So here I guess you could also have a set seen right? So that sort of tells you whether you should check to merge groups. So initially for 1 2 3, like now that I have seen four right, and then index which is Union join the whole row because that's like one bus route. So also you would need to check so for each bus route checks if any are in seen. Yeah because if they are in seen then you'll need to start joining them. Okay and so I also probably keep that in a list because you might run into a scenario, this for like if we had a four and a two right here, just as an example, you would need to join it to two separate groups right, not just one.

Electric Burrito: Mm-hmm yeah okay.

Rocket Tiger: Um okay so in this case when we run across the three, we see three has been seen before and in that case see so three has been seen before... also you still there?

Electric Burrito: Yeah I'm still here.

Rocket Tiger: Ok just wanted to check because across the top it says refresh to the latest version which I don't know that means.

Electric Burrito: Um yeah I don't know what that means either.

Rocket Tiger: Ok ok yes seen...

Electric Burrito: So what are these union joins... let's go out actually maybe you can describe your approach a little better. So like I guess your union joining each right ok. What exactly are you union joining and like why?

Rocket Tiger: Um so I'm union joining the ones that I haven't seen before um because that way they will be in like the same grouping right, and union joining means that you can within that group go from a bus to any other city.

Electric Burrito: Ok so if I go to like... let's say you're union joining all the cities into different groups right?

Rocket Tiger: Yeah.

Electric Burrito: Ok and so then if a city is in the same union set then you can get between them.

Rocket Tiger: Yeah pretty much, um so there is a solution... so it would be... so if n is the number of buses and then m is the number of cities within each bus route, we can probably do a union join that's m*n^2 time. I'm just trying to optimize down, but so like that will probably be the cleanest way. Yeah so to explain the m*n^2 way of doing it, you would literally just go through every single combination, so I would start with this one, like one I would union join with two right then I would union join it with three, and so now all these are one grouping, and then three... this is why it's O(n^2) is because if you do this n times for the number of buses and then within each bus that's n^2 right, so I union join 3 with 4 and then I union joined 3 to 5 and then I go down, you can join four with five. Oh okay I don't need to do the pairwise thing. In that case is nm time because they will already be in a union okay. Okay yeah I may have been overthinking this earlier. In that case it's just nm.

Electric Burrito: Okay so what is the algorithm.

Rocket Tiger: So to go okay... yeah so let's see if I can just go over here... let's say we have the functions, really only the one that matters is the union right? And also find parents. Okay actually root is probably better right? Um so what we're going to do is or each row and then or these for each row.

Electric Burrito: What is one row? Oh that's each route.

Rocket Tiger: Yeah for each bus route. Okay we're going to union join everything... So basically that means like for every element after the first one we're going to...

Electric Burrito: For every city in route.

Rocket Tiger: Yep and then I would let us union everything, so to continue with a second route here, 3 is unioned with 4, and then 5 is also unioned then.

Electric Burrito: Oh okay. And this second time you encounter 3 here, that's fine because it's already in the set you're saying?

Rocket Tiger: Well so in this case you don't actually need to have, I guess if we want to check for redundancy, that's okay, but you don't really have to have this set at all, that set doesn't actually matter.

Electric Burrito: Okay.

Rocket Tiger: Yeah because if we...

Electric Burrito: Yeah because you already know you can yeah. You check three and it already points to one.

Rocket Tiger: Yeah so it doesn't really matter, and plus when we do the joining we can probably have a check that's like if a parent is already equal to like the same parents and just do nothing right? So that's another way to deal with it just within the join method.

Electric Burrito: Okay so what happens when you hit seven here?

Rocket Tiger: So also to clarify um, the way the parent list is initialized is initial parent array is each element is just going to point to itself. So that would just be none.

Electric Burrito: Okay.

Rocket Tiger: Yeah so in general for union joins that's how you would initialize the array, each node is like its own parent and for unions you would travel up to their parents and then set one pant equal to the other parent right? And so in this case because seven hadn't ever...

Electric Burrito: Yeah yeah.

Rocket Tiger: So when you hit the 7, you're going to join it with the 11 right? So just finish the... So the other elements I guess would be taken care of and then if we decide to keep the 7 it would look like that right? So 11's parent would be 7's and parent is itself.

Electric Burrito: Okay yeah.

Rocket Tiger: And so just to finish it off so um these would all be in the same grouping. 6 doesn't exist. 7 also doesn't exist. 8 is in the same group as 4. And then 9 is also in the same group as 4. So then we would at the end find the parent of what is of 2 is a city we care about, and you find a parent of 7, also by parent I mean root, and so you find the root of our cities and then you'd be like oh they're not the same, in which case they aren't in the same group and they can't you know interact with each other, and so your turns false in this case.

Electric Burrito: Ok cool. I think that will actually work.

Rocket Tiger: Yeah um.

Electric Burrito: Yeah sure you want to try coding it up? I think it might need one little change but yeah.

Rocket Tiger: Also I'm guessing the cities in the bus route can be any number right? They can be like one, five, one hundred, two thousand right?

Electric Burrito: Yeah there could be any any number of cities. They're really just names, so they don't have to be numbers.

Rocket Tiger: Okay.

Electric Burrito: Unique identifier for the city.

Rocket Tiger: Yeah I'm just making sure...

Electric Burrito: Or you can rename... Yeah just presume it's just integers, like presume you pre-processed it and labeled all the city ithe number like...

Rocket Tiger: Okay yeah otherwise then use a dictionary just wanted it like the ideal item would be yeah.

Electric Burrito: So it was about input actually. I'm gonna fix my question so that it fits yeah.

Rocket Tiger: So if we can assume that... so we need to figure out how many cities we have and so let's assume that we have simply processed... All numbers are continuous. So we need to find I guess some like small first step. So that'll get us the total number of cities. So ideally that should set up our initialized array so it'll look something like... right?

Electric Burrito: Sorry what what is a max city? that's the root city?

Rocket Tiger: So max city is just like the largest number that you have in your input so for instance if like the example that you pasted above it would be 8 right? All it's doing is just telling us how large our parent arrays should be.

Electric Burrito: Oh, I see I see.

Rocket Tiger: The numbers where contiguous are preproccess.

Electric Burrito: Oh yeah oh I see what you're doing. You got to allocate the array that's okay, got it.

Rocket Tiger: Yeah and if it wasn't preprocessed and that was like the point of me asking if it wasn't preprocessed like that, like if this was one it was like 9999999, you would use like... because you would want to have a list that would be mostly empty. Yeah I mean you can obviously change it into like a dictionary if you wanted to, it's just your preference for how you want to do it. But if they are continuous then like a list of probably easier and faster access yeah.

Electric Burrito: Than a dictionary?

Rocket Tiger: Yeah because a dictionary is always going to be slower than a list right because a dictionary like is a superset of a list basically right like, it it's like more optimized or something?

Electric Burrito: Yeah yeah basically like it's impossible for dictionary to be faster than list because the dictionary does like list operation plus other operations. It doesn't really matter um for like a Leetcode question yeah. Yeah you will have set that up. And let's see our next step is to... I'm just going to try to find my place again because I got off on a tangent there. Um...

Rocket Tiger: Yeah sorry about that.

Electric Burrito: Yeah no worries.

Rocket Tiger: Thanks for the knowledge.

Electric Burrito: Yeah yeah. Okay and then that case we have to define a couple functions really quick. Okay um so what this is doing is it's going to find you the root of your current node because it's basically going to traverse up like different parents and then also what it's going to do is it's going to, once it finds the root it's actually going to assign it to the parent of this current node and so not only does it find you the root but also shortens down the height of that recursive traversal so that's the next time you do it it will just be like one step away, does that sort of make sense?

Rocket Tiger: Um I think so.

Electric Burrito: Yes yeah it's just that in the future if you ever want to find the root of this one again like you will have updated it on line 86 and so you can like shorten the traversal a lot.

Rocket Tiger: Oh I see yeah. But isn't that what a union set is anyway?

Electric Burrito: Um so for a normal one you wouldn't... so you would for instance if I am... So this is what you could do instead, this is like a lazy way of doing it. I think that is taught in textbooks more. In this case you don't cache it in an array and so if you were to call root(i) on this one, you would have to go all the way back up the tree. Whereas in this case now you're only like one step away from the root right?

Rocket Tiger: Oh I see, I see. So that means okay even the worst case you're only a like constant time away from finding the parents.

Electric Burrito: Yeah yeah exactly you're like reducing the height of your tree yeah. That might be easier for debugging later on because it'll keep the first one that we encounter. Yeah that seems good to me, um give it root, a union, alright and then at the end you're gonna return root. Ah see oh we need to have in our parameters source destination. First equal to root, dest and that should be it.

Rocket Tiger: Okay I think that makes complete sense, so and I don't want to take keep you here too long, so there's no need to test it, I guess you could do that on your own time. Okay so because we're out of time, there's even one more extension to this which maybe you want to think about, which is like how would you find like the shortest number of changes between buses, like let's say every time you want to get on a bus, it costs like a buck fifty per bus pass, like how can you do this in with the spending the least amount of money, in the economy. So that would be like a breadth-first search, you want to store from each city. So you'd have like pre-process your input array and then basically you want to get into like a dictionary where like each key is a city and then the value for that dictionary is a list of the cities that you can go to and then you would breadth-first search, and yeah you just return the amount of stops it took.

Electric Burrito: Yeah exactly okay cool yeah. Uh thanks for taking the time to let me interview you. I actually was anticipating that I was going to be interviewed today, so I was kind of surprised to learn that I signed up to be the interviewer but great hahaha, thanks for bearing with me.

Rocket Tiger: I had a person and I asked them like oh just kind of like your background in detail I had them to subscribe it for like five minutes as I looked for the question.

Electric Burrito: Because of what?

Rocket Tiger: Oh I had them like describe their background for like five minutes as I was like scrambling to find a Leetcode question for them.

Electric Burrito: Hahaha okay that's a good strategy, I'll keep that in mind if it happens to me again. Okay thanks, good luck on your interview.

Rocket Tiger: Oh yeah. Do you have any feedback or things to improve on?

Electric Burrito: Oh yeah feedback of course um, yeah so I think, let me see the first one was pretty good. I think the second one if you could like articulate. I totally forgot about feedback. If you can maybe spend even more time like or make sure that like exactly the algorithm you're going to use is like clearly articulated before you do it before you start coding. I think um maybe you're fine there maybe it's just because I don't have super good familiarity with these questions I'm asking. It was harder for me to understand your approach. And then another thing here, like I mean just like judging I'm not a good judge of a Python code because I don't know Python, but I think this like max city and just like this stuff here maybe it could be like taken out or something but other than I mean I think these are really hard problems and you figured out the algorithms very quickly, so I think and then you were able to transform that algorithm into code, so I mean I have no complaints there I think.

Rocket Tiger: Yeah yeah really appreciate it! Also I noticed when you were... is Union join not the way you're thinking of doing the second one? Because I noticed like maybe you were like thinking of a different approach?

Electric Burrito: No uh, so I only ever thought about this problem and like kind of like kind of on my own time, but then I was thinking I would do like I would just like somehow like... conceptually the idea behind it would be I'll make a graph and each node on the graph is the route and so I would go through each route and then like make edges from one route to another route if they hit the same city and then at that point like you were saying you could do a breadth-first search across this graph to see when you hit a route that contains the city you're looking for. So somehow like that just seemed a little bit like higher level like easier to understand then this Union stuff, but I think the union stuff is actually faster, maybe faster I don't know, and maybe the union stuff is more natural to think about too so I don't know. That's just how I was I was thinking about it, but I really like the implication of union stuff, that's really good.

Rocket Tiger: Yeah for the most part whenever I've seen problems that can be solved with union join, they can also be solved with depth first search, and so yeah I could definitely see what you mean like you'd process the routes and then for if it's like in the same route, then you're at an edge between those two cities, so that definitely makes sense, you can definitely do it that way yeah.

Electric Burrito: And also I'd never heard of this union thing for the what was the other one you did the union for? Oh it's my first question on the the matrix, the the color to matrix, so that was a really cool approach too, so maybe I'll think about using that more if I get... if I'm tempted to do a depth-first search, then maybe I'll think about a union set next time.

Rocket Tiger: Okay I mean to be honest I feel like depth first search is a little cleaner because like with the union join, you always have to define like the root method and the union method and so that's a little bit of overhead but also like once you copy-paste it like a million times, you kind of know what it looks like.

Electric Burrito: Mm-hmm yeah, cool yeah that's a really good interview thanks for uh thanks for working with through these things with me, it's very helpful for me too! So yeah good luck, enjoy your practicing.

Rocket Tiger: I appreciate it, thanks a lot for your question. I hope you have a great one.

Electric Burrito: Yup.