Google Coding Interview: High School Student's Algorithm Challenge

William impressively navigates a complex Google coding interview, demonstrating advanced algorithmic skills in graph theory.

### Google Coding Interview with High School Programming Prodigy William Lin
* 🎥 In this video, a Google coding interview is conducted with William Lin, a high school student and accomplished competitive programmer, showcasing his **impressive skills**.
* 💻 The interview focuses on a challenging problem called **"Airport Connections,"** which involves creating an algorithm to determine the **minimum number of routes needed** for passengers to travel between airports.
* 📊 William uses advanced graph algorithms, specifically **Kosaraju's algorithm**, to find strongly connected components within the graph of airports and routes, achieving a **time complexity of O(n + m)**, where n is the number of airports and m is the number of routes.
* ✈ The starting airport for the problem is **LaGuardia (LGA)**, and the goal is to ensure that all other airports in the list can be reached from LGA, despite LGA having **no outbound flights**.
* 🔍 The interview emphasizes the **importance of clear communication** and **understanding of complex algorithms**, with the interviewer providing **constructive feedback** on William's coding style and problem-solving approach.
* 👍 The interviewer expresses admiration for William's performance, stating he would be a **strong hire at Google**, highlighting the significance of his **youth and accomplishments in competitive programming**.
* 📈 The final output of the problem is determined by **counting the number of airports with an in-degree of zero**, which indicates the **minimum routes needed to connect the airports effectively**.
* 💬 Viewers are encouraged to **engage with the content**, think critically about the **problem-solving process**, and check out more interviews on William's channel for **additional insights into competitive programming**.

What's up, everybody? How's it going? In this video, we're doing the most exciting Google coding interview that I've conducted ever. That's right, this is not a Google coding interview with an adult competitive programmer. It's not a Google coding interview with a college student. It's a Google coding interview with a high school student. It's not just any high school student, though. This is the one and only William Lin. He happens to be a competitive programmer. Also, you may have seen him in his recent YouTube video that went viral where he won Google Kickstart Round A. He also represented the U.S. at the International Olympiad of Informatics, where he won a silver medal. He's also an international Grandmaster on Codeforces. He is a veritable algo expert. Speaking of an algo expert, for this Google coding interview, I asked him the hardest question that we have on Algo Expert. It's called Airport Connections. This is the kind of question that I would never expect a candidate to be able to fully solve and fully code out in just 45

minutes. I would expect them to struggle through it, maybe get a potential solution, cut out some of it. I would certainly expect to give them a lot of hints. I won't spoil anything, so you'll have to watch the entire video if you want to know how William did. But that's the question that I gave him, by the way, on the topic of algo expert. If you're prepared for your own Google coding interviews, check out my company algo expert. Use the promo code Cleanse helium for a discount on the platform. And finally, before we jump into the interview, just a few points. Number one, this is exactly how I would conduct a real Google coding interview. You'll see that we used Google Docs, which is what you would use in a technical phone interview with Google. We also had William screen share his screen so that we could see what he was drawing. This kind of mimicked an on-site coding interview where you would have a whiteboard, and he'd be able to exhaust some stuff. Number two, I would highly

encourage you to really try to solve this problem as you watch the video. Think of how you would approach the problem. Comment down below what you're thinking, what your approach says. Number three, at the end of the video, we have a debrief session where I give him feedback. That's always good to watch because you can see how the interviewer interpreted the interview. And last but not least, number four, we actually filmed a second Google coding interview on William's channel. We're giving you all kinds of Google coding interviews. Go check that one out after you watch this video. I'll put the links in the description and in the comments below. Be sure to show William some love. He seems like an awesome guy. I had a really good chat with him before and after the interview. So go give him some love. And with that, let's jump into the hardest Google coding interview that I've ever conducted. Hey William, how's it going? Are you ready for the interview? Everything's going fine. How about you? I'm doing great.

I'm excited to get started. Yes, I'm excited as well. Can't wait for this. Okay, so we're gonna have roughly 45 minutes. We have a Google Doc. You have your own drawing app that you are sharing with me so I can see your screen, so I can see what you're drawing. Wonder and uh, let's one note. Yeah, let's begin. I'm gonna put 45 minutes on the clock starting now. Okay, okay. All right, so I want you to imagine that you are an airline. So you support, you know, flying from airport to airport, and you've got a list of airports where your airline is available. And so I'm actually going to be giving you as an input to this function that you're gonna have to write a list of airports. I'll copy it in the dock here. These airports are gonna be these three-letter codes. You might be familiar with them. Like this is how this is done in real life. So, you know, BUD is like Budapest Airport, LGA is LaGuardia Airport, and so on and so.

forth. So, these are all the airports that you've got at your disposal for your airline. And then I'm also gonna give you a list of airport routes or airport connections. So, for the purpose of this question, I'm gonna use the words routes and connections kind of interchangeably, okay? They're gonna look like this. So, they're gonna be pairs. It's gonna be like one list of lists of lengths two where you've got two airports in the lists, okay? And what this represents is it means that your airline has a one-way flight from the first airport to the second airport, one way. So, for instance, here, yeah, one way. So, you can fly it with your airline from DSM to ORD. You can fly from SIN to CDG, etc., okay? Yeah, now you're the kind of airline that really wants to support its travel. You want to make sure that your travelers can travel the world, experience all of the airports that you have, you know, connections to or flights to. And you have one airport in particular that's really popular. We're

gonna call this the starting Airport. Maybe it's like your headquarters or something like that, so I'll put it here. This is gonna be the third input to your function, and here, this starting Airport is going to be LGA, LaGuardia, which is in our list of airports. You want to make sure that any traveler who wants to travel to one of these airports starting at LaGuardia can do that. You want them to be able to reach any Airport in your list of airports starting at LaGuardia. Now, the thing is, as you might notice in the routes, LaGuardia isn't necessarily connected to every airport. In fact, I don't think LaGuardia has any outbound flights. Yeah, it doesn't. So, wait, it doesn't? Yeah, so what you're gonna have to do is you're gonna have to write a function that is an or devise an algorithm that is gonna determine the minimum number of routes or connections, so one-way flights that you have to basically allow as your airline to enable any passenger to go from

LaGuardia to any other airport. Now, the one caveat is that others, it doesn't have to be that the passenger can hurt you. Can you still hear me? Can you still hear me? Oh, your voice got cut off. Okay, can you hear me now? Yeah. Okay, okay, perfect. So, like I was saying, you want to make sure you want you want to allow all of your all of your passengers to be able to go from LaGuardia to any other airport. Now, the only caveat is that they don't have to be able to go directly from LaGuardia to another airport. It's okay if they fly through other airports. Does that make sense? Any number of airports? Yeah. So, for example, like imagine, well, you could go from LaGuardia to sa n down here in the routes. That would mean that you could also go from LaGuardia to eyw because you could first go through sa n. Does that make sense? Yes. So, also, these passengers don't care about having like five transfer flights. They don't care about having five transfer flights all

they care about is being able to reach the destination airports. But you have to, you're working on behalf of the airline, so you want to minimize the number of connections or routes that your airline is gonna have to support so that every passenger can go from the starting Airport to all of the air other airports. And it turns out, just to give you the answer for this particular example here, the answer would be three. So I'll write it down, we'll put answer three. The reason it's three is because if you connect, basically like you can, you can add three connections that are gonna allow, you know, your users or your passengers to go from LaGuardia to any other Airport. Okay, do you know which um, which three here so that you need to add? Yes, so for example, you would add one connection from LaGuardia to Tel Aviv TLV, and the reason is because like that opens up a lot of flights, right? Then you would add one to either SFO or maybe San here, and then finally you would add one

to e WR okay, okay, so that's the entire problem, right? That is the entire problem, you know? Okay, so first off, we have lists of airports and such, lists of one-way connections. So this can basically formulate this entire problem as a directed graph, okay? Okay, so now you know about strongly connected components. Remind me or educate me, okay? So I, so imagine if we have a directed graph. So, okay, maybe it looks like this, and then in this graph, we have, you might notice that, oh wait, actually I'll just do this. You might notice that there are these components that can, there are these groups of nodes, okay, such that, yeah, not from any node in a group, you can travel to any other node in the group. So for example, yeah, you started at this node over here, then by following the edges in here, you can also travel to all other three nodes. And yeah, the same is true if you start at the others, do you know? You can always reach the four nodes. So yep.

after you find these office of all these strongly connected components will be disjoint from each other. So the because if you imagine that like if we have like to strongly connected components, we're like one node is part of both. We know by the definition that like we can travel, we can travel from us number years one, two, and three, you know about yes the option that we can travel from 1 to 22 because they're in the same component, and then you can travel from 2 to 3 because they're in the same component. So in fact, we can also travel from 1 to 3 and 3 to 1 as well. So in fact, like if you if these two groups of nodes can all go, can all travel to each other, then like this entire group of five nodes is just one strongly connected component. So yep, so why just showed that is that these components are disjoint. So is that is that part clear? Yep, that makes sense. Okay, so after we find of the oiseau.

notice that like each node will be part of exactly one component. So if, if like because single nodes will just speed your own components, so each node will have its own component. And then, okay, after we do this, we'll compress all the components, all the components into nodes. So I mean by this is at this original directed graph here will become a new graph like this, which is basically taking the components and we're just basically taking the big circles and then like making them into the new nodes, sure. Okay, so and then in this new graph over here, the compressed graph, oh, will what is it choose this out, will get an acyclic graph. And that's true because, for example, if we had a cycle like this, so if these formed a cycle, then what happened is that these three would actually be part of the same component. So it's impossible for the new graph to have any cycles, right? That makes sense. Okay, oh, so now we get to, okay, so now we get to like our, oh, by the way, like we can just work with the new graph and

completely ignore the original graph because as long as we can reach some node in a component, we can reach all nodes inside the component. So, oh sure, yeah, okay. So, and then let's say that I'll just created a new like compressed gas. So, if I new compressed graph looks like this and maybe just draw a few more, and then maybe then we have our starting node, which can be basically, let's say, to start notice over here. Yes, yeah, that's fine. Oh, when you do well, basically, you add a new directed edges from s to other nodes. So, for example, we could do this, but then adding this edge doesn't help because like this node was already reachable from s already in the beginning. Sure, and so now, okay, so now let's, so now the notes which aren't reachable from s are these nodes over here with an N degree of 0. So, they don't have any nodes pointing towards them, so it's impossible for us to reach these nodes, to reach these components. Okay, okay, so that means

that we need to cover these nodes when you do like a die just so that as can so that any person starting from s can travel to these nodes right yep all right so the only way we can do that is if the only way you can do that is if we add an edge from somewhere can thing too like this no over here and we need to do the same thing for this as well and then notice that if these two nose with in degree zero are reachable from s and that means that all other nodes will also be reachable from s as well as long as we deliver the notes within degree zero then we'll be fine and just to clarify William when you say when you say in degree 0 or n degree zero you're talking about like like inbound edges right yeah ten degree is inbound edges and an out degree is outbound edges yeah okay so so then on so we know that we must at least add an incoming edge to each of these two nodes in order to like satisfy the problem and

one way you can do so is just to connect it to us. So, we'll just connect them like this, and then after a week after, if we connect a new edge from s to each node within degree zero, we will be able to, like, on all nodes, we'll be able to be reached from s. Yeah, okay. So, the answer for the problem will just be, we'll just feed the number of nodes with an N degree of zero, which are not us. So, this case is just 2. And so, the entire algorithm here is, so first, oh, I'm on the Google Talk right now, by the way, so yep, yep. The first thing we do is we'll process the input. So, I'll make the strings and do some more, some more usable form, I guess. So, okay. Then, then we all, yeah, we'll find the strongly connected components. Okay. And then, next step is to compress the graph based on components. And then, last step is to find the number of nodes within degree equals zero, which are not s in the new graph. And then, that will be our

answer and just a William for for the number of that last step. The number of in-degree equals zero, which are not as in the new graph. Is it not possible to have two nodes with in-degree zero that then connects the same node? It is possible, but those two nodes would still have in-degree zero, so you would still need to reach them. So actually disregard what I just said. Yeah, so we know that we must connect these types of nodes, and then it happens that once we connect these types of nodes, all nodes will be reachable. So yeah, so yeah, the establish the lower bound and the upper bound for the answer to be this number, the number of nodes with an in-degree of zero, which are not s. Yeah, all right. So today, if you want, why don't you, but before you jump into the code, why don't you just very briefly walk me through how you are gonna conceptually do these four steps? Okay, so processing, I guess. So first, I'll just go through the list of airports and then assign each string.

a and like an ID number for therefore starting from zero so okay zero one and then and then what I'll do is I'll Kate and okay then Jason C list to represent to graph so for each of these also I'll have a map it stores the string and an integer and then this will be the map which comforts from the name of the airport into the ID of the airport and then sure sounds good I'll go through the list of routes and then for each route I'll convert the name into the ID and then alright so first what out what else used to store the graph is I'll use an adjacency list so I see a factor is just a list and I'll have so for each of that end nodes I'll have a list of a story a list of which notes it can't reach yep sample let's say yes and if DSM is if DSM is 0 and Ord is 1 then what I'll do is I'll just I'll just add I'll add the value 1 into a jacent 0 its

that yeah ok totally up ok so now I created the adjacency matrix no the adjacency list of the entire grass and yeah that's really uh that's basically why I wanted to do input yep sounds good they found the Jason c-list I will find the strongly connected components so this is this is the more I guess this is a more interesting part of the solution so they're actually they're actually algorithms which do this for you I think it's called corsages algorithm and well basically you find it'll find the it will give you the kind of strongly connected components of the of a graph in all of em plus em time where n is the number of nodes or the number of airports in our case and M is the number of edges or the number of routes in our case sure so oh should I explain this algorithm like I don't exactly know how do you don't really exactly know I'll explain it I just kind of know it if you want for now let's skip it and we'll what once you get into

the implementation details we'll maybe we'll talk about it there, but the idea is here. You're applying this algorithm to get all those strongly connected components, and I'm assuming is the idea that your output there will be another adjacency list but for just these new connected component nodes or what I guess the output will be. So for each, so yes, for each like component, they'll choose a representative node of the component arbitrarily. So maybe like, okay, maybe like these are the representative nodes of each component. And then what we'll do is we, so you have this array called who of you, basically who of you will, you can the node which is the representative node of its components. So for example, sure, okay, I call it if I want the who value of this node, then it will return this node because it's the representative node of its component. And then gotcha, okay, so this algorithm should return this district to create this who already. Yeah, there sup is to compress the graph based on the components. So all right, so what

I'm going to do is but in order to represent the new graph. I'm also going to use a new adjacency matrix. I'll call it a DJ to event. And then even though that there might not be an components. I'll still use. I'll still use a also have an array of size N. And then what I'll do is I'll only considered the representative notes. So basically all notes you such that are who are you is equal to you. These are the notes that like I'm going to work with. Okay okay. So in order to get this new adjacency list from the old one. Well what I'll do is like this leave for each waste original edge you to be if ah if these two are from different component components. Then I'll basically add a new way. I'll add a new edge for their representative nodes. Does this part make sense. Can you repeat that. So for every you'll you'll go through every alright now I want to yeah no go ahead you go ahead. Alright so basically for each of the original edges in this graph.

I want to like comfort. I want to like add these edges, convert these edges into the new graph over here. Okay, yeah, okay. So the first thing is if an edge connects two nodes in the same component, then we can't base. Then since the component just becomes one node, then we'll just remove this edge. So that's why I do here. So for each edge from u to V, if these, if u and V are not in the same component, and we can check that they are not in the same component if they have different representative nodes, right? Oh yeah, okay, okay. So then some, if we find that U and V are from different components, so like these two nodes, then we'll add an edge in a new graph between the cut, the components. So document. So that's why we have, we add an edge from the representative node of U to the representative node of V. And just if you go back to your drawing for a second here in the upmost connected component, the one that you were looking at a second ago, you have

that one with the four nodes. Imagine, imagine two of those nodes pointed out to like that other green node in the one with the triangle. How would you handle like not do a counting twice, you know, that the representative node of the four-person thing points to the representative note of the three-person one. Does that make sense as a question? Do you mean like another edge like this? Yeah, exactly. How would you, and imagine that that other edge that you pointed, imagine it pointed to, yeah, I guess yes, because that like that means that you would you would add the representative node potentially twice. How would you handle that? So if we have, if we have, if you have two of the same edges in this in this new adjacency list, then it actually won't affect our answer because our answer is just the number of nodes with an in-degree of zero, which I not s, but then if if we add, oh, you know, if we duplicate edges, then that won't change if a node has an in-degree of zero or not. I see, so you are you are purposely

okay with duplicating edges, yeah, and so purposely it's just convenient to not check couldn't or duplicates, fair enough, yep, no, totally make sense. okay, so now we have this now. okay, did this new adjacency list, and all we do is now the only part left is to find the number of nodes with an in-degree of zero, which I not us. so the first step, I'll just count. I'll just go through calc number of you such that. so I only want to work with the representative, so first thing is you make sure that you is the representative of the component, of its component, and then I also need to make sure that it hasn't. Oh, actually, after we create the new adjacent least z-list. um, let me think. so since you have a problem, take your time. okay, so since we want the in-degree of all the nodes. Oh, we'll make more sense. Instead of having, instead of doing stuff like working with a new adjacency list, we actually just need to count the in-degree for all the components, so I'll

just have an array. They're called a degree, so then our code doesn't change much, but we'll just do is we'll do is we'll just change this part. So we add an edge in a graph from u to V, and when that happens, the in-degree of V increases by one. So I'll just replace this part with I'll add one to the degree of the president representative node of feet like this. Gotcha, okay. So now, so for instance, in your OneNote here, you had in the one with the Surrey nodes in it, you would suddenly have an in-degree of - yeah, okay, okay. So now you want to find the number of in-degree it's acquitted zero. So just check that it's zero, and then after we find that count, we oh yeah, actually we just and and and when you just need to make sure that it's not the component of this. So as long as this component does not contain s, then we'll count it, and then the count will be our answer, yeah.

okay okay I think this is a good overview of everything. I think we can jump into the coding. We've got roughly 15 minutes left, so yeah, let's jump into it. Okay, so oh, so I guess I'll just write a function for this. So I say yeah, well, I'll just not care about capitalization. Yeah, don't worry about that. Just call it salt because I don't know what to call it in. And I have a list of airports, so be a list of strings. And then I also have a list of lists of strings, social media routes. Now lastly, I have the studying airport, which is a string. Yep, okay. And then the first step, I go through the list of airports and assign each string an ID number. So solve it. I'll just find an, which is just sighs our list of a Poisson. And I also have this mapped to comfort from the each string to each string of the airport to its ID. And I just go from time, just go through each of the airports and then

I'll set the string. I'll set this string in them. I'll put in and Shina map with the string as a key and I as the value, and I will be the idea of the airport, okay? And then I create this actually um. I'll just do this kind of like in a competitive forum, so I'll have a maximum value of, and I'll just make it something like this. And then I will, and then I'll, I need to clear this adjacency array on the outside with the McGregor you of n, so this part is still okay. And then I go through the routes. I'll just do this, so for each edge, I'll just add it into the Chasen c-list, so okay. Oh, the starting node is, will basically be a, basically use of my map to find the ID of the starting node, which is the first node of this list. And then I'll find the ID of the second node, and this will basically you add to edge, yep. And then the second part is running the strongly

kinetic hones algorithm. So for this, I'll need the it gives me a cool array, so I'll declare this as well, and then Ford algorithm for this artisan. I also need a reversed adjacency list. I'll call it R, okay, and then I also need, was it, I need its back for this, okay, and then in the start of the exam, I'll create the reverse adjacency. So basically, for each or judge and the Jason Lucy list, I'll just add it to the reverse adjacency list. I'll just swap I and J to make it reversed, right, okay, okay, and then the algorithm consists of two parts. The first part is, oh yeah, and I also need a boolean array to store if I visited a node or not, yeah, for the DFS that I'm going to run, okay, okay. So if this node is not visited, like this node is not visited, then I'll run DFS on it. So let me write the code for DFS one. So why visit this node? I should set it to visited, and then, and then I'll do is

I'll try to visit other nodes from this node. So, for each other node in the adjacency list, if it's not visited already, then I'll visit it now. Lastly, I need to add this node into the stack. Okay, so that's the first DFS function for you're adding the node. You're adding the node that you are currently doing DFS on in the stack. Yeah, after I visit all your notes. Okay, yeah. And then the second part, I um, I basically go through the stack starting from the top of the stack. So, well, well, like just fact is not empty, look at the top of the stack and then I'll remove it. Okay. And then if it's so, what I'm going to do here is I actually, I'll just create a new array called fizz. So, this will act the same. It what this will have the same function as the first of is array, but I know before DFS. Okay. And then if it's not visited, then we all visit it like this. No, now remember that we need to find the

who array like this note you hear will be the representative node of the entire component. So, what DFS 2 will do is the FS 2 will go through all nodes in use component, and it'll set those nodes to a little set that representative knows of all those nodes in the components. So, to you, yeah, um, did you say something? No, no, I see. I said I just confirmed what you said. Yeah - you are ninja and to be the representative. So, we've first since we visited, we started to visited, and then now we set the cordon. So, we decided to their representative, and then we just, and at this time in DFS - we work with the reversed adjacency list. So, we do pretty much the same thing, and if V is not positive, then we'll visit it. And this time, we go to node V, but on the other side, it is still same. So, we call DFS - V Ranch is the reason that you are going through the reversed adjacency list here. I guess I like what is that reason. Uh, the reason is with how this algorithm

for finding the components works. So wait, I haven't really thought about, oh, I haven't really thought much about why this algorithm does this. But if you want me to, then I didn't try to find a few examples. Let's assume for now that I'm like, I trust that it works. Some just interesting. I'm sure that there's like a piece of logic that makes everything click together. But okay, let's assume that it works. Okay, so now after this entire loop of two DFS basically, yeah, I basically found the who array for each node. So now for this problem, we can just ignore the new adjacency list. We only need to work with the only you want the in-degree of all the nodes. So yep, I'll create this array called others' greatest degree array. And then let's see. So now we go through the edges, and then all we do is we check that these two are in different components. And if they are, then we add an edge from who have I -

who LJ so the in-degree of curves journey increases that one. So this will give us the in-degree of all of the in-degrees of often those in the new gas. Yeah, because if they are not, if they don't have the same representative node, then the one that we are pointing to has an N degree. Okay, yeah. And that's where last stuff we found a degree right now. We just count the number of nodes, number of components with a zero in degree and don't contain us. Okay, so this will be our answer. So we go through each of the nodes and make first checked eyes by representative node. So who have I should be itself and then you also check that as a degree of zero. So now we make sure that it doesn't contain the, it's think it doesn't contain us. So as long as I is not equal to the who of the ID of this and the who of idea of us, I'll just use the map to find a ID. So it's starting airport. So if all these the conditions are true and

that means we need to add an edge from the starting airport into this node. So we had wanted answer and can you can you repeat why you're doing the first condition the who of I equals I okay. So I'm basically iterating through all notes in the original graph like five zero two and minus one. But then what I wanted what I want to do it actually is to iterate through all nodes in the new graph. Oh the condemn strength yeah the condense graph. So those new so in order to iterate through only the the nose in a condensed graph. I only I need I make sure that the node is it's representatives in its own components. Since each component has exactly one representative. So each component will be checked through exactly once. Gotcha I see. So this condition sort of like cleverly kind of ensures that you're only going through those representative notes. Yes gotcha okay okay cool. Say it looks like you're you're done here right. Yeah I think yeah I'm pretty sure it is. Okay so before we've got like a couple minutes.

left on the clock, which is like kind of perfect timing. Let's see if we can just, if you can walk me through all the various code blocks and their complexity analysis. Oh, okay, so oh yeah, I forgot to do that. Um, okay, so the first part and up by a way format again. Yeah, see false us map. It's basically a binary search tree. Its operations are like a vlog, and like if I want to improve the operations to constant time, I can use a hash map using an order. I just, I didn't like really care about this since this is like, this just, it doesn't really matter in this to making this solution correct anyway. So in order to improve the complexity, I'll just use an unordered last year. Okay, so okay, the first part, this loop. Oh, by the way, I'll just use n as the number of airports and M as the number of routes or edges. So this, okay, sure is open. This part is of and because we loop through m times, each like each iteration is constant time and then

for creating the reverse adjacency list, this part is O(n + m) because, yep, we loop through, we have n iterations, so that creates the n here, and also for each this, we iterate through each of the edges, so each yep in a graph like gives us constant time, and then for this DFS, this DFS is over n plus n time. This is pretty similar to like a normal DFS, so what I do is, since once we visit a node, we never visit again, we visit each node exactly once, so that gives us like the n in our time complexity, and the m comes from, so every time we eat o in this loop over here where we go through the jason see list of U, we do this exactly once for each edge, so each yep is checked exactly once, so that gives us all of em yep, gotcha, and then this part where the second DFS here is its yes, it's pretty much the same thing as the first DFS, do I need to explain it? This is where, and this is

where we get into the whatever you call the core la whose algorithm or something on actually like. I'm just saying about the second DFS is structurally its structural eats the same as the first one. Yeah, so yep, time complexity is the same. Yeah, then for is for loop here for you calculate the degree array. We loop through, we live for high from 0 to N, and then we also loop through all of the edges. So this part is and each edge we move to gives us constant time. So this part is all of n plus M. And then lastly for Kelly dancer, we loop through all end nodes, and then each node is we do a constant time check. So this part is just all them. So in total, like if we add everything together, we get a time complexity of all of and plus M. Yep, cool. And let's skip the space complexity for now, just in the in the t minus like three minutes that that were that we are in now. Just one quick thing that I'm curious about here in

your while loop. Yeah, you're popping off the stack once, but then you reap off the stack. Why are you doing that second popping off the stack? Oh, actually, the top. This function top doesn't pop off the stack. The only... Oh, oh, it's top. Yeah, top. Okay, yeah. I thought it was pop. I misread. Okay, okay, cool, perfect. Um, okay, so then this makes more sense, and I think this looks great. Yeah, we're out of time. Okay, so taken as long as I didn't, like, mess up my implementation for Corsage's algorithm, then this should be fine. Yeah, I mean, I'm gonna look that up, and at this point, I... This one, we're done with the interview, so I think, you know, for the people who are still watching here, um, I would encourage you to look that algorithm up. I'll probably put it on the screen somewhere. I'm gonna go look it up. I'm curious, especially why you're doing the reverse adjacency list if so. Okay, with... Let's get into debrief if you want.

like William just leases for the rest of the video. So, first of all, this went a little bit over time, went to like 40, 48 minutes, but like this was like totally fine. Um, I will do my best to give like feedback for whatever feedback I can give. But first of all, like this one splendidly series. I think this is awesome. Like I said at the beginning of the video, like this is the type of question that I would either not ask in an interview because I think it's too difficult in an interview or too time-consuming or both. Or if I were to ask it, I would not be expecting, and he, I would not be expecting like perfectly written code or working code, and I would probably be expecting quite a few hints. So, fantastic jobs from the point of view. Oh, sorry, go ahead. Oh yeah, I wasn't expecting, like I wasn't expecting strongly connected. Come on, it's in this problem because it's actually a fairly, it's pretty common in competitive programming, but

then it's not common enough to actually be encoding interviews, so I was well. I'm surprised it's a fairly complicated. Yeah, it's a fairly. I'd say it's like a probably a slightly more advanced graph topic there. So you can solve this with a worse complexity without doing the connected components. And so that I was actually like, I didn't think of the connected components solution where I've like, I've thought about it. I've never really like written it down. So this was like super cool to see because you can basically do, you can do like further form or DFS's to find like unreachable nodes or things like that, which give you the same answer but are not nearly as elegant as condensing the graph, if that makes sense. Right? Yeah. But so yeah, going back to this, the feedback like from the algorithmic point of view, fantastic job. Like there's probably no point of criticism that I can give you. You not only were able to solve the problem clearly optimally, but you went

through it seamlessly from a communication point of view. Really great job. Like, you're under pressure, you're writing a really complicated algorithm, you have to write the code, you communicate. I was not lost at any point in time except for my own lack of knowledge about like the crew lodges algorithms. I was able to follow through what you were doing, which is like, I think it is a big. I'm commending your ability to communicate here. And then finally, as far as the code, I mean, if I want to be like really nitpicky but really keeping everybody watching and you to William like this is I'm trying to find constructive criticism. I would just say that, you know, encoding interviews, typically we prefer seeing a little bit more descriptive in this and like the variable naming because it helps, you know, follow through. I think this is something that like in competitive programming, you tend to use like very small variable names, right? I guess, yeah, that's true for competitive rhyming, but I guess like I thought since I was already like talking through

what my code was doing, so I thought it was fine if I didn't use be able names which were that descriptive. I would say it was because, like I said, I didn't typically like the reason you look for descriptive variable names is because it helps make it easier to follow, but I had no problem following here because you were communicating so well, and you went through the examples so well. So yeah, I think yeah, they were all good. And also things like adjacency or degree or eggs UV, these are like, these are totally fine. Maybe like, maybe who, maybe who would have been like, Hey, there was a point of improvement, like again, I'm really being trying to find constructive criticism, but otherwise fantastic job without a doubt, strong hire from my point of view. If I were like a coding interviewer at Google still for both a full-time, for both an internship, internship, like not even a question in full-time, not even a question. So for what it's worth, William, you have a Clement Molesky's blessing for whatever.

that represents really. I guess it means a lot if it's from an X Google engineering like this one. You're really you're better than me at algorithms, sir. So, are you suddenly have like a lot more experience or early you will you clearly live and breathe this stuff. So, but cool. Any last words that you want to tell the viewers or anything. So, be sure to check out my channel because I have a lot of interesting stuff about competitive. So, uh, if you do competitive or Emmy, that's how you get really good at these type of problems. So, yeah, check it out. Definitely check it out. It's like awesome content and like super super cool, super cool guy. Thanks so much, William. Thank you. So, that's gonna be it for this video. I really hope that you enjoyed the interview and that you found William's performance as impressive as I did. I mean, it was absolutely insane, really incredible performance. The fact that William is so young just adds even more impressive nough stew all of this. And like I mentioned at the beginning of the

video. We filmed a second the Google coding interview on his channel. Go check it out. It's a very different type of question, lots of learning potential, and show him some love. He seems like a really nice guy with a very promising future. With that, don't forget to smash the like button if you haven't already. Subscribe to the channel if you haven't already, and I will see you in the next video.

Google Coding Interview With A High School Student

Clément Mihailescu

William Lin, a high school student and competitive programmer, conducts a Google coding interview, tackling the challenging "Airport Connections" question.

He shares his thought process on time complexity and the structure of the algorithm while discussing the creation of an adjacency list and finding strongly connected components.

The interview highlights the importance of allowing passengers to travel between airports through other connections, rather than directly.

The video features a coding interview with William, focusing on solving a problem related to airport routes and connections.

The interviewer provides feedback on William's approach, highlighting the use of descriptive variable names and effective communication.

The algorithm to solve the problem involves processing the input, finding strongly connected components, compressing the graph, and identifying nodes with a degree of zero.

The discussion revolves around minimizing the number of airline connections needed to reach various airports.

The example given suggests that three connections are sufficient to cover all destinations from LaGuardia Airport.

The algorithm involves identifying strongly connected components, choosing representative nodes, and creating a new adjacency list to represent the optimized connections.

The graph is represented using an adjacency list, with a map to convert airport names to IDs.

The algorithm adds edges based on routes and tracks in-degrees to identify reachable nodes.

The final count of nodes with in-degree zero, excluding the starting node, determines the solution to the problem.

Conceptualizing the Solution for Airport Connections

The problem involves a list of airports and one-way social media routes, which can be formulated as a directed graph.

The first step is to assign ID numbers to each airport and map them to their corresponding strings.

The goal is to identify nodes with an in-degree of zero, as they are not reachable from any other node, and to connect these nodes to establish reachability within the graph.

Finally, the components of the graph are compressed into new nodes, resulting in an acyclic graph that can be used to solve the problem.

The first DFS function visits unvisited nodes and adds the current node to the stack.

The second part iterates through the stack, creating a new array to track nodes in the condensed graph.

The algorithm ensures that each component's representative node is checked only once, and the in-degree of nodes is counted to identify those with zero in-degrees.

Analyzing the Complexity of a Graph Algorithm

The reverse adjacency list creation is O(n + m) due to n iterations and constant time edge checks.

The first DFS also runs in O(n + m) by visiting each node and edge exactly once.

The second DFS and the in-degree calculation follow a similar pattern, ultimately leading to the identification of nodes with zero in-degrees as the final answer.

Solving the Google Coding Interview Question

The video features a coding interview with a focus on finding strongly connected components in a graph, using algorithms like Kosaraju's.

The interviewer provides feedback on the candidate's approach and offers insights into the algorithm's logic.

The discussion includes the importance of in-degrees and edges in determining the minimum number of routes needed for passengers to travel between airports.