Before the interview, William told me he was a little nervous. Does this look like the performance of someone who's nervous? 😋Be sure to check out the other Google coding interview that we filmed on William's channel here: th-cam.com/video/-tNMxwWSN_M/w-d-xo.html
Hi @Clément Mihailescu, do another interview with me, I am totally self taught engineer (only high school graduate) and I was recently interviewed by Amazon and Google.
I started coding websites in PHP at age 14 for my Counter-Strike team, but I did not even know what a linked list was until age 19-20. Also, my code and website looked like crap. It was 2004 though, for my defence most websites looked like crap.
I've been learning to code for about a year now. Every couple months I use this video as a mile marker to see how much more I understand than I did the last time I watched it.
If you are trying to understand the theory of the program, you can look up graph theory and more specifically directed graphs. There are tons of books that explain it from a programmer's point of view, though I highly recommend reading a more mathematical source if you can understand the mathematical language. Good luck on your coding journey!
This is more of a data structures and algorithms problem than a programming problem. Learning to code is just simply being able to use the tools to fix a job. This is more theory of how to structure code in a way that can fix the problem. In this scenario, he is using a direction graph to represent the relationship between each airport. The graph shows the edges of each node, and he then simplifies the graph to exclude useless information (nodes that are strongly interconnected can be summed to 1 node). From here, a breadth first searching alg can be used to find where the solution should be. This is all theory The actual coding may only take like 10 minutes to implement Search up data structures and algorithms on TH-cam, some really good videos that help break it down in a less maths heavy way. Maybe try get your head around time complexity as well Keep it up buddy 👍
@@enyplayz1514 Late response, and not directed to me. But i started learning python for my self due to it's less incline learning curve. The syntax is easy to follow and the thought process between different things within OOP is easier to learn. Secondly i learnt Java, which is similar but still different, now im learning c++ on my own. Another "programming language" that is very useful in todays society is SQL due to databases widespread use in almost any modern business. I'm currently 1.5 years (+0.3 self learnt) into my programming journey. I'd probably say start with python if you want to learn coding easily and also learn a language that is going to be used very widely in the future. It's strong, simple and very modern. There's alot of good free online courses, even here on youtube. good luck
C for competitive programming D for dijkstra E for education F for flow charts G for graphs H for heaps I for iterative deepiening dfs J for jump point search K for kadane L for logorithmic time M for min max N for null O for big O P for prime Q for quick sort R for recursion S for sets T for trees U for unordered map V for vectors W for width X for xavier Y for f(x) Z for complex numbers
G for greedy search H for Heurisitic search I for insertion sort J for Johnson's algorithm K for Kruskal's algorithm L for linked list M for minimax algorithm N for N-queens problem O for Optimization problem P for Pigeonhole sort Q for Quicksort R for Recursion S for Shortest path T for Tree traversal U for Undirected graph V for Venn diagram W for Weighted graph X for Xenomorph algorithm Y for Yak algorithm Z for Zucchini algorithm
Wonder if he had it prepared before. Definitely makes good impression. I think I'll use it myself one day though if used incorrectly and under stress it might sound a bit arrogant
after watching the whole video, yeah this is just easy SCC stuff, an IGM on Codeforces like him is expected to solve it within minutes (or maybe 10 or 20 minutes at most)
@@sf43205 dude ... the purpose of a coding interview is to (1) asses the applicants cs knowledge and (2) test problem-solving skills. It's annoying when people trash on coding interviews saying its irrelevant to what they do on the job when that's not the purpose of an algorithm/coding interview.
@@sf43205 Actually you can't solve the problem with a single recursive function, unless you're a terrible programmer who writes monolithic untestable methods that won't scale very well. Understanding the complexity and performance impact is also part of this. He has 2 recursive functions that can be threaded tasks. Whether he did that on purpose or not, I don't know. He also split the sorting of the data structures from the solving and usage of those structures which is good algorithm design (this should have been taught in your school) and actually makes the implementation not very complex and reasonable to debug. The problem is not simply finding a valid route, which could work with one decently concise method, sure. It's about finding the route with the least cost. His solution is great, I worry more that he's writing algorithms that he's memorized and doesn't understand WHY they work. This can be problematic when you need to translate that work to other hardware or even other languages. But he'll learn more about that when he studies.
It's easy when he has the solution while Clement described the problem. He just needs to spend his processing power on explaining it. Imagine how fast he'll be once he learns the mathematical vernacular to express well-known ideas in college.
You mean kids since forever: "I learned everything else before learning another language"? Language doesn't measure your intellect and it doesn't required you to learn English first before you can master other stuff.
@@phunweng962 Coding culture in india is on Boom right now.Iam a college student in india and literally everyone here only talks about competetive coding
I was just learning how to code, but I learned that it’s time to quit Edit: the replies have changed my mentality. It’s not time to quit; it’s time to improve.
He does a very good job at visualizing and properly explaining his thought process. Very impressive. His explanation is also well structured and he seems very confident in his knowledge. He is definitely gonna make it.
What struck me about this interview is that the question is an extremely basic graph theory question, and most of the discussion is just about implementing very basic ideas from graph theory. With that being said, I know that I would fail this interview, because I definitely couldn't implement all these steps under pressure. This makes me realize that to work at a company like this, the skill you need is not to be a genius problem solver, but rather to be familiar with the already existing basic techniques, be able to explain them clearly to a layperson, and code them cleanly on the spot.
@@RenatoOliveiraGaming Lmao.. its basic Question. Actually I didn't even understand the Question that was asked but What The Student is explaining is very Basic stuff.. I just passed 3rd semester in university and I had thus subject called Data Structure. Lmao... its all that stuff. It's piece of cake.
@@pets9921 in general a question like this is kind of labelled "basic" only because it's one of the first concepts you'll learn when looking at graph theory, connectedness, and traversing nodes. shortest distance between two nodes is a very common problem in its own, in this scenario just depends on the algorithm you implement which gets more and more complicated. the question will always be in general very simple, just knowing which implementation to use and how it works to replicate it is the main hard part.
You know he explained it very well from the fact I didn’t know ANYTHING about directed graphs and strongly connected components but his explanation made sense LOL
I can honestly feel the sheer happiness in william's face when clement starts asking questions. Its like he is really enjoying solving this problem. Way to go!
I like his problem-solving process. Drawing out the problem, simplifying it, planning the steps. It's so methodical. I also like how he checks with clement if he understands up to that point, that shows that he is really thinking clearly.
1. AFAIK Your job is to provide shortest route from START airport (LGA) to any other of the first array. Yet your job is to create new *least* amount of paths from LGA to those Airports that are unreachable from LGA at the moment. 2. HE builds GRAPH. HE compresses it (reduces interlooped nodes to 1 node) with Korasaju algorithm. Then he searches the solution for the shortest route for any given END. The last part is something i can predict, cuz, well, i've doing my stuff listening to the video on background since minute 15 i guess... he reversed links of the graph, so, during the solving END became START and LGA (initial START) became END.
Can't give you nothing but one stupid suggestion : practice. I've solved similar task once. I suggest to practice it the tough way - use C with least libs included, no segfaults and memory leaks. Just juice the best out of the problem: crack the algo down and get used to the conception of memory usage and structure composing altogether.
Don't look at it that way, William doesn't possess anything you do not possess, the difference is in time spent. You can always improve yourself, and you also don't need to do it alone. Good Luck on your studies!
You can code without knowing all of these. They're only important for higher posts. And you can just take some courses, maybe free even, and they're easy to understand.
It's always gonna be like that brother, no matter what field, not matter what company, not matter how experienced you are, you will always have bad interviews. Sometimes it's your fault, sometimes it's the interviewer's, most the time it's both. All you gotta do is to not underestimate yourself, do everything you can and if you fail tell to yourself that's more experience. Maybe next time you'll be less anxious, maybe you'll be more prepared, maybe you'll present yourself differently, etc... But it can only get better ! :)
Interviewer: [explains problem] what is your solution? Me: do you know stackoverflow? well I do and there's your solution edited: oh wow didn't expect this to hit 900 likes, thanks everyone!
One thing folks never compare yourself, the result which you are seeing is not just one day of work it requires lots of practice and dedication to develop such skillset. Have a great day ahead.
I sometimes believe that kids like him were born to do this, just like any athlete..yes they worked hard but they were destined to become that good.. thats the conclusion i came too,, could be wrong but thats what helps me not comapre myself.
The fact that I didn't practice as much as he did is what hits hard, not just that he's great at what he's doing, because he's more competent as a person
This is what is called a competitive programmer. Probably he is used to compete in sites like codeforces, hacker rank, URI, etc. I used to hang out with folks like him. Learn a lot from them but was quite difficult to keep the same level as their.
I understand a lot of the coding and the physical logic, I am so blown away on his problem solving skills and his ability to think of pretty optimal solutions within minutes of reading the problem. It would take most people hours to think of even a half optimal solution to this problem, he solved the whole thing and explained it in 45 minutes with time to spare.
I'm a sophomore in college and just took an algorithms class that goes over a problem like this! I noticed it was a BFS algo pretty easily, but it's always difficult to put it into actual code. That's amazing that a high schooler was able to do this!
@@bahriaproperties1143 after the post order search, I think a breadth first search (bfs) through the newly created list works, Ik for a fact the successive depth first search works tho
@@tens0r884 The guy is a sophomore who doesn't even qualify as a beginner in the field, and has a chip on his shoulder. Then looks down on the kid because he's a high schooler and gives gives him back handed praise. Necessary.
2:55 He smiles because he realizes that it's an airline problem. If you've ever been in competitive math, stats, or programming teams, you'd know that anything to do with flying and destination plots is.. insanely difficult.
Could you explain why? I’m just curious as I don’t know much about this topic. Is it harder because you don’t have specific paths to follow like roads or variable changes due to the environment?
Insanely difficult, but it's also been done to death, so perhaps not so difficult after all. :) Now try on the stable roommate problem for size. I only accept answers in SQL. ;)
@@fortythirty Yes. It is also because of the environment. With a normal Chess or Rubix scenario, you have preinstalled paths. You can't go across the Chess board or turn once to solve these puzzles. With a plane graph, you could use one flight to get around the world, or use 30 different flights to get around the world. It has stumped developers for years!
Have to say, i understood this sooo much better now that I’ve taken my college’s data structures class. Looking forward to two more years then a lifetime of more learning!
Yeah, people shouldn't get discouraged these like most technical interview problems are really simple rephrased data structures problems that were made more to tease out how you approach problems rather than testing your ability to memorize content.
@@TheFriendlyInvader Thank you this made me feel a lot better I haven't taken my data structure classes yet still learning microsoft office and barely touching some Java and I had no idea what they were talking about n felt discouraged.
I tried to make an algorithm that gives me the exact amount of locations and the locations itself that would need to be connected to my new „airport“ in order to reach every place from my new „airport“. My solution before watching the video after the explanations was that if you do a new list that is a copy of the airports list, you can do the following: for x in (copied airport list) for y in (connections) if x == y[0] copied airport list.remove(y[1]) Explanation of the code: Line 1 makes x cycle through the copied airports list, getting the next string after each cycle. Line 2 makes y cycle through the connections, getting the next string list after each cycle. Line 3 compares current x string with the first string from current y (the currently selected airport with the starting destination of the currently selected connection way). Line 4 is finally removing an airport (the final destination of the currently selected connection way) if the if-statement is true. It’s removing from the copied airport list (let’s call it the anchors list). What you’re left with is a list with every location you would need to set a connection (I think, thought about it for 10 min). Edit: By deleting the list while going through it, you won’t end up going through already accessible airports. Wanted to add this because people might think it would result in deleting a whole „loop“ section where each connection goes back to itself original connection. That wouldn’t be the case though. And yes you would need to try-catch it irl because it would give you an error if you try to delete an airport that is already deleted/nonexistent (which is like 2 words spread over 2 lines)
Absolutely INSANE. Tbh my mind went straight to Dijkstra's algorithm when I saw plane routes. Which I understood at some point but could never code on the spot now. I've also been coding for 13 years.
Interesting... Graphs are the right answer when looking for an application programming job - but did anyone grok that, at it's heart, it's not even strictly a graph problem? I mean, yes... you should always answer this AS a graph problem. Keep the solution you offer general, extensible, self-documenting and easy to understand. You should spend most of the interview walking them through a fairly bland and unsurprising answer. After all, there's often a follow-up or spec-change... and if you have to rewrite your existing code, it's a major fail. So... stay general, and model the problem statement closely. But then, when the interviewer is finally satisfied that you're just boring enough to play well in a team churning out unsurprising and predictable code... offer them the _"red pill"_ by pointing out that this approach, though fairly standard, is actually horrendously inefficient. Imagine Morpheus saying : _"What if I told you, you're solving the wrong problem... and all this code is mostly an illusion designed to stop humans from realising the truth and freaking out?"_ Drop a closing tease, like _"I'm just thinking, this problem is actually a lot more interesting than it appears... for example, say we ever needed to run this over big data, I reckon we could consolidate hundreds one way destinations per couple of cycles, in-place, to get the same data without ever building the tree. Almost no heap utilisation, leaves the compiler free to use streaming SIMD and bring those ultra-wide registers into play. The cost saving in a server farm would be absolutely staggering. Of course, it's not pretty - there'd be a tradeoff in readability and it's far less general... but still, it's shocking just how well this optimises." Then, just let it hang there in the air... Basically, you just said _"and, if that's not enough - we can use magic!"_ ... expect an arched eyebrow. If they ask you to expand how you'd do that, then you can take them on a REALLY deep dive without compromising your previous 'safe' answer... and, if they say _"no need, we're very happy with what you've supplied"_ you've still shown you may have hidden depths in terms of problem analysis. In the latter case, you can safely assume there's not likely to be much challenge or opportunity for progression. Sometimes, you'll be asked to re-interview for a different role. You see, there's the UI's and the Apps, and Client code... that's all really safe and boring, and it gets a lot of employee churn. Then there's the behind-the-scenes bread-and-butter data crunching work that pays the big bucks and requires more analysis, problem solving and reductionism. You can interview for both, but let them choose what they want to see. Get it right and you'd be surprised how often you can essentially get hired to a role that's not even open, just to stop you walking out the door. Standard library coders are ten a penny these days, but the kinds of folks who can reduce a problem to it's essence and can switch between high level to machine level, well... the universities just aren't churning many of those out. We live in a world where everyone and their grandmother can code, fewer can program _(yes, it's traditionally a different discipline)_ ... and fewer still have a solid appreciation of how to move a problem into the processors domain _(as opposed to wasting resources bringing the processor up to meet the problem in the natural domain)_ But, you MUST provide the safe answer first! And deep-dive only by invitation, right at the end... offer too clever a solution without being explicitly asked, and you're unemployable! - They'll step over you on the way to the next interviewee : )
Finally being able to see how a coding interview should have been conducted successfully. first starting from your intuition and explain your ideas Then outline the steps in the algorithm explain detailing each step and finally do the code (Rather than seeing myself having awkward silences and making nonsense answers)
I am a freshman comp sci major taking discrete math right now and its kind of cool seeing some of the concepts of that class "coming to life" in this coding interview
Trust me buddy you’ll be fine out there even if don’t remember graph theory by the time you graduate. Most companies looking for developers are not doing shit like this as part of their business. I bet they don’t even use it in most Google engineering jobs.
@@gabrielordonez8011 lol so you just wanna be a code monkey? you're basically just a typewriter then? no original ideas, you'll just write whatever you're told, sorry dictated... that's a sad approach to cs
I'm impressed by his knowledge of network theory. I'm a mathematician and did a good chunk of network theory throughout my degree and he's got a good grasp of all of those concepts despite being in school still. I always allow for a bit of stumbling as everyone gets nervous in interviews, so his understanding is clearly very strong taking that into account.
I think the kid in the video is dragging on for too long. He goes on tangents that don't have a directed end. I wouldn't hire him because he isn't answering the problem layed out before him. Solve the problem first, explain your solution later.
@@nilen I was wondering if you could help me I'm a student. I'm studying on code academy and I was wondering is there a more effective way to learn code? I'm looking but the internet is a big place. If you could help I would appreciate it thanks!
Good on this kid for knowing about graph theory and connected components. As soon as he mentioned LGA and I didn't see it on the list, I figured the problem out, but I have a PhD in combinatorial design theory. There is no way I knew these concepts in high school.
Ya my limited experience with discrete (math) principles let me understand perfectly well the kids solution, though if I were there, there would be no way I would be able to write code that nice and would probably take me 4+ hours before I could come up with a solution like his…
@@catedoge3206 I didn't delete it, but I don't see it here any more. Someone must have deleted it or something. This has happened to me a few times now.
I don't even code but I really enjoyed this, I just got started on a very very very basic level and even still I was able to follow and learn a whole lot more than I thought of this just through his explanations even though of course a ton went over my head. Just a wholesome interview was really cool.
I've never coded in my life and the concepts overwhelm me, but my mathematic and analytical reasoning skills are above average and he really makes me feel like I understand what is going on!
I really like your professionalism. I once took an interview at a company which I won't disclose, even though I'm not legally obligated to, but that's not cool, who even though I passed the technical interview put me through another technical interview with the team leader for some reason (officially, there was only a technical interview and a team-"fit" interview), I guess he wanted to impose himself, and whilst I was explaining and thinking the problem he was constantly interrupting me, asking stupid questions, even to a point while I asked him "let me think a little, please, I'll explain in just a second" he continued intterupting me with "what are you thinking about? Tell me what are you thinking at" countless times. I ended up solving the problem and failing this last interview for another candidate. I'm really appreciative about your attitude to your candidates. I feel like some interviewers, given this position and ability to filtrate who gets in and who doesn't, have grown a big ego and suffer of some emotional issues. Then again, it might be just me, and I may too sensitive or have stupid expectations of them.
William Lin is so always so impressive to watch ! I also took the time to do this exercise in python with a totally different approach (took me a little over 1h though). I thought that using an object-oriented approach could work and it did rather well ! Since I have not done any programming studies I have yet to look into the complexity of my code so if anyone could give me feedback on it I'd appreciate it! Here is the code (with comments) : # Data given airports = [ "BGI", "CDG", "DEL", "DOH", "DSM", "EWR", "EYW", "HND", "ICN", "JFK", "LGA", "LHR", "ORD", "SAN", "SFO", "SIN", "TLV", "BUD"] routes = [ ["DSM", "ORD"], ["ORD", "BGI"], ["BGI", "LGA"], ["SIN", "CDG"], ["CDG", "SIN"], ["CDG", "BUD"], ["DEL", "DOH"], ["DEL", "CDG"], ["TLV", "DEL"], ["EWR", "HND"], ["HND", "ICN"], ["HND", "JFK"], ["ICN", "JFK"], ["JFK", "LGA"], ["EYW", "LHR"], ["LHR", "SFO"], ["SFO", "SAN"], ["SFO", "DSM"], ["SAN", "EYW"]] Start = "LGA" # Answer class Airport(): # Initialize the class with the airport name, the list of airports, the list of routes def __init__(self, name, airports=airports, routes=routes.copy()): self.Connections = [name] self.MissingAirports = airports.copy() # Remove from the missing airports the starting airport self.MissingAirports.remove(name) # Find all connections in current routes not in the existing list of connections and remove them from the list of missingAirports for i in routes: if i[0] == name and i[1] not in self.Connections: self.Connections.append(i[1]) self.MissingAirports.remove(i[1]) # Recursive method : when I add a connection to self.Connection it will be taken into account for i in self.Connections: for j in routes: if j[0] == i and j[1] not in self.Connections: self.Connections.append(j[1]) self.MissingAirports.remove(j[1]) # I now have the connections with the current routes. # Find out the number of new connections obtained when connecting to a missing airport def CountNewConnection(self, name): newAirport = Airport(name) Connections = self.Connections.copy() count = 0 for i in newAirport.Connections: if i not in Connections: count += 1 return count # Connect to an airport using its name and add the new connections to self.Connections def ConnectTo(self, name): newAirport = Airport(name) for i in newAirport.Connections: if i not in self.Connections: self.Connections.append(i) self.MissingAirports.remove(i) # Create object using Airport class with the starting airport. Start = Airport(Start) #initialise the iteration count iterations = 0 # #Loop : while the length of unique connections is different than the length of airports while len(Start.Connections) != len(airports): # Count the number of new connections when connecting to an airport for each missing airport count = [Start.CountNewConnection(i) for i in Start.MissingAirports] # Connect to the missing airport with the maximum of new connections Start.ConnectTo(Start.MissingAirports[count.index(max(count))]) # add 1 to iteration count iterations += 1 # return the number of iterations. print(iterations) # Possible to print to which airport it has to connect and in which order in the while loop.
You got a coding interview when you were 16... That in itself is impressive. Hope your success continued in life! (success in just obtaining opportunities... not that you got ur ass handed to you lol)
Have now subscribed to both channels. I programmed for about 10 years and then switched to Product (and have interviewed at Google). William's raw brainpower, problem understanding, high level solution description and coding while speaking/explaining (and while under pressure and being recorded) is impressive for anyone at any level and any age. Considering he won't hit his 'peak' for another 20-ish years, I suspect we'll be hearing/seeing more of him as a programming force of nature. Props!
@@laggyfilms4768 I was replying to "Apparently grads have a hard time w this" and I was saying "Really? it should be easy for them". I am not talking about the "him" that you are talking about. I wasn't replying to the Title: line where Vitus is talking about the Title of the video but rather the next lines.
My solution to this problem would be, reduce our connections(A -> B) to just a list of B, create a map from our ports with each port mapped to False by default. Iterate through the list of B, turning ports[B] to True. our result is the length of a filter that filters ports(C, D) by not D Note: This was completely inspired by finding the edges method he provisioned
It should be noted that adding new nodes to cover in-degree 0 nodes will always at least preserve the number of total in-degree 0 nodes in the graph, or even increase the total number (if you add multiple nodes as the interviewer suggested briefly before retracting). Therefore, the incoming edges have to be from an existing node, and this node must be the Starting node if you care about preserving acyclity. Any other node would create a cycle if connected to the in-degree 0 nodes because of the topology of the graph. Also to clarify, every node under the node that the Starting node points to can be disregarded because they are children of that node and thus can clearly be reached, and every parent node above the node that the Starting node points to (excluding the Starting node itself) will be able to be reached if the in-degree 0 ancestor nodes are taken care of.
@@Allie912 He is conducting a mock interview to which he will be given a result. His result was a “strong hire,” as per the interviewer’s feedback. I just pointed out the moment he seemed to have it in the bag. You don’t need to look into it that much.
@@Allie912 You don't need to graduate to get hired. Most people who graduate with a comp-sci are bumbling idiots anyway. Just like any STEM field. Let's not pretend that it actually has worth outside of getting you better chances of a job, if you're already competent enough, then it doesn't matter.
As an applied mathematics student, it’s not too difficult of a problem; but approaching it from a cs point would make it more difficult with the syntax and algorithms tied to the language , but his understanding of graph theory is pretty impressive considering the level of abstract math it is and the level of math you’re taught in hs . Once you understand the graph theory approach tho , you’re setup for success. Great job to him !
Me, thinking I'm really smart: Hah! That's a piece of cake! Just go through an array of all the connections and start by picking out the ones with the inputted destination as the second index of that connection. Now, from those, for each one connection, scan for those where index 1 equals index 2 in any other connection AND index 1 is equal to the departure airport in that connection. If no matches are found, it means there are no routes that short, and you just repeat the process but you go one step further until you find the departure airport. While you do this you can list all the available routes, or just immediately display the minimum number of "jumps" you have to take to get to the destination, like this exercise asks. **watches the solution** Oh. I'm dum dum.
I think your idea too would work equally well, it's also really simple and easy to understand. At some point in the process you described, you're bound to come across an airport in index 1 which isn't in index 2 in any of the other connections. This is equivalent to finding nodes with 0 inbound connections, and hence if you count such cases(excluding start point) you'll have the minimum number of connections to be made. One exclusion in this process though would be if there is such an airport in the 1st input list that has NO incoming or outgoing connections(and hence would not be taken care of in our first process), and for such an airport, an additional direct connection would be required. Even though William's brilliant graphical approach really helps visualize and provides an interesting approach, your solution would work just as well!
I hope this shows people that a degree doesnt make someone good, This shows people that someone that put in the hours and the passion, that's what matters. He probably spent a lot of hours cracking leetcode questions.
@@Garentei Ofcourse you have to work on other stuff too, but still, the key is putting in a lot of hours, there is no magic there. Read/Practice repeat.
ikr, he probably doesen't even pay attention much in high school but do his own studying since, you know, high school is like 90 % memorization, 10% applying logic/skills. EDIT: Danggg i'm right. looked at his channel right after this vid and look what i found th-cam.com/video/Q7p8nC_-qUo/w-d-xo.html
@@jgsource552 Actually pretty awesome, the path he was going was very good without university, he would have come equally far without it. Nothing against degrees, the problem of the whole educational system it is trash, it was and is designed to create workforces, people smart enough to "operate the machines" but dumb enough to not question the system. Anyway, if I had to choose a university it would be MIT.
I learned a lot from you guys. Clement, your acting is exactly as a interviewer, doing these little "ok" moments, where it always tickled me and made me think, "am I doing something wrong?". Now I know that this is just the response from an interviewer to keep the neutrality so he can see if the interviewee is confident enough to support his argument. And William, you just taught me how to be confident of supporting my argument. Despite if the solution you're giving is not exactly what the interviewer expected (or otherwise), that doesn't mean it's not a better solution. It's actually very cool how you easily went through the problem with full confidence, and accepted possible failure, only to kill the task dead in its tracks. :D I've been watching both of you for a long time, and I've learned very different things from both of you! Happy to see you two in a single video. Cheers!
Thank u guys so much for uploading such valuable content, I learned a lot. As an Engineering Grad student I can't help but feel humbled by the later generations efforts and achievements, and I hope the open sourced collaborative environment continues to grow and become successful. ....but I'm not gonna lie, I also feel cheated by the system, for we pay a lot of money to get degrees and certifications, and even if we nail an interview, we still don't get hired.....esp, for decent positions that we worked hard for many years for....all in all, I wish everyone good luck and Godspeed.
Before the interview, William told me he was a little nervous. Does this look like the performance of someone who's nervous? 😋Be sure to check out the other Google coding interview that we filmed on William's channel here: th-cam.com/video/-tNMxwWSN_M/w-d-xo.html
Clément Mihailescu yes he seem super nervous if that’s what you want to know.
How good would he be white boarding in C++ though I wonder?
Nice interview Clem!!!
Hi @Clément Mihailescu, do another interview with me, I am totally self taught engineer (only high school graduate) and I was recently interviewed by Amazon and Google.
Next Interview : Gennady Korotkevich
Can we become like him if we buy algo expert?
Imagine you have to present your project in class just after this guy ....
@shrowdy ydworhs Well, I guess you will receive full points without doing anything...
@@LiudongZuo XD
Just half ass it.
Okay I am done
Just hack his computer to one up him
That guy knows Kosaraju's algorithm, and he is in high school. When I was in high school , I once shaved my entire eyebrows to see how I look
I started coding websites in PHP at age 14 for my Counter-Strike team, but I did not even know what a linked list was until age 19-20.
Also, my code and website looked like crap. It was 2004 though, for my defence most websites looked like crap.
Zuckerbook also shaves his eyebrows, so I guess the joke is on this Google Prodigy.
but he is competitive programmer, in competitive programming this is one of the easiest graph algorithms.
i cant even programme a basic result of an area of a square :((
@@klicer3068 would you like a job at Google?
He’s making my parents proud
Lmaoooo
@sun If u don't get the joke, ur probably under the age of 10
@@The2AmInventor Literally no one cares
@@icyweiner2182 Literally nobody asked
@@The2AmInventor Quiet child
I've been learning to code for about a year now. Every couple months I use this video as a mile marker to see how much more I understand than I did the last time I watched it.
If you are trying to understand the theory of the program, you can look up graph theory and more specifically directed graphs. There are tons of books that explain it from a programmer's point of view, though I highly recommend reading a more mathematical source if you can understand the mathematical language. Good luck on your coding journey!
This is more of a data structures and algorithms problem than a programming problem. Learning to code is just simply being able to use the tools to fix a job. This is more theory of how to structure code in a way that can fix the problem.
In this scenario, he is using a direction graph to represent the relationship between each airport. The graph shows the edges of each node, and he then simplifies the graph to exclude useless information (nodes that are strongly interconnected can be summed to 1 node). From here, a breadth first searching alg can be used to find where the solution should be. This is all theory
The actual coding may only take like 10 minutes to implement
Search up data structures and algorithms on TH-cam, some really good videos that help break it down in a less maths heavy way. Maybe try get your head around time complexity as well
Keep it up buddy 👍
Hey what programming languages did u learn and what are u learning now?
@@-nocturn3268 are you by any chance a swe? Can I reach out?
@@enyplayz1514 Late response, and not directed to me. But i started learning python for my self due to it's less incline learning curve. The syntax is easy to follow and the thought process between different things within OOP is easier to learn.
Secondly i learnt Java, which is similar but still different, now im learning c++ on my own. Another "programming language" that is very useful in todays society is SQL due to databases widespread use in almost any modern business.
I'm currently 1.5 years (+0.3 self learnt) into my programming journey. I'd probably say start with python if you want to learn coding easily and also learn a language that is going to be used very widely in the future. It's strong, simple and very modern. There's alot of good free online courses, even here on youtube. good luck
Everyone as a kid: “A for Apple, B for Bird,...”
WilliamLin as a kid: “A for Abstract Datatypes, B for Breadth-first Search,...”
C for competitive programming
D for dijkstra
E for education
F for flow charts
G for graphs
H for heaps
I for iterative deepiening dfs
J for jump point search
K for kadane
L for logorithmic time
M for min max
N for null
O for big O
P for prime
Q for quick sort
R for recursion
S for sets
T for trees
U for unordered map
V for vectors
W for width
X for xavier
Y for f(x)
Z for complex numbers
G for greedy search
H for Heurisitic search
I for insertion sort
J for Johnson's algorithm
K for Kruskal's algorithm
L for linked list
M for minimax algorithm
N for N-queens problem
O for Optimization problem
P for Pigeonhole sort
Q for Quicksort
R for Recursion
S for Shortest path
T for Tree traversal
U for Undirected graph
V for Venn diagram
W for Weighted graph
X for Xenomorph algorithm
Y for Yak algorithm
Z for Zucchini algorithm
@@awekeningbro1207 0 for false
1 for true
3 for 11....
@@firecracker-i2h 2 = 10
No, B is for Binary Tree Reversing
“that’s the entire problem?” Sounded pretty confident and cool
Wonder if he had it prepared before. Definitely makes good impression. I think I'll use it myself one day though if used incorrectly and under stress it might sound a bit arrogant
I’m reasonably certain he could of just produced the results in the amount of time he spent explaining what he was going to do.
This problem was easy considering it was supposed to be the hardest
after watching the whole video, yeah this is just easy SCC stuff, an IGM on Codeforces like him is expected to solve it within minutes (or maybe 10 or 20 minutes at most)
Time stamp plz?
Non programmers don't realize how impressive this is. Most software engineers can't solve this.
So this kid is really smart lol
@@sf43205 dude ... the purpose of a coding interview is to (1) asses the applicants cs knowledge and (2) test problem-solving skills. It's annoying when people trash on coding interviews saying its irrelevant to what they do on the job when that's not the purpose of an algorithm/coding interview.
And when you say most, you’re not lying. 99.99% cannot solve this.
Oh so he smart😳
@@sf43205 Actually you can't solve the problem with a single recursive function, unless you're a terrible programmer who writes monolithic untestable methods that won't scale very well. Understanding the complexity and performance impact is also part of this. He has 2 recursive functions that can be threaded tasks. Whether he did that on purpose or not, I don't know. He also split the sorting of the data structures from the solving and usage of those structures which is good algorithm design (this should have been taught in your school) and actually makes the implementation not very complex and reasonable to debug.
The problem is not simply finding a valid route, which could work with one decently concise method, sure. It's about finding the route with the least cost. His solution is great, I worry more that he's writing algorithms that he's memorized and doesn't understand WHY they work. This can be problematic when you need to translate that work to other hardware or even other languages. But he'll learn more about that when he studies.
1 minute after hearing the problem, I'd be like: - "Ok, guess I won't be working here then, thank you and bye."
Bro, you just killed me😂😂😂😅😄😄😃
😂😂😂😂
😂😂😂😂😂😂💀💀💀💀💀💀💀💀
1 minute after hearing it? 1 minute into him saying the problem, I was like what the hell?
exactly
"There's always an Asian better than you, even if you're Asian."
There are asians, and there are Asians
this is technically impossible, as it implies the need for an Asian better than the best of Asians, but I don't care
It's True.
maybe a belarusian in case of Competitive
You mean there's a Russian ?
TH-cam is getting real comfortable with these double no skip ads
Bro right! Its gonna be 1 minute advertisements here soon.
On mobile press the (i) stop seeing this ad and then cancel and it’ll skip both of the ads
@@James-pf1vg oh my god, thanks dude!
I just pay for TH-cam red because I use TH-cam for like all of my tv related entertainment
@@brentmadison7605 you must be over 40
How he managed to explain such a complex topic/code so easily under pressure is amazing, great video!
crazy isn't it, I think it's because he gives simple and concrete visual examples and relates it back to his reasoning
@@adamma1024 do you believe that leetcode is best for getting well prepared for coding interviews in big tech companies?
@@JL-pg4pj actually yes it shows you are capable of problem solving
Practice practice.......
It's easy when he has the solution while Clement described the problem. He just needs to spend his processing power on explaining it. Imagine how fast he'll be once he learns the mathematical vernacular to express well-known ideas in college.
William has the code in his head after 5-10 minutes but talking about it and finding the right words was not so simple.
Impressive work.
Kids in 2030: "I learned Python before English"
Probably some kids in foreign countries like this now. Maybe South Korea or Japan.
I'm a kid who learned to program before I could read/speak English (this means almost no documentation and no stack overflow).
You mean kids since forever: "I learned everything else before learning another language"? Language doesn't measure your intellect and it doesn't required you to learn English first before you can master other stuff.
@@donaldazevedo5554 Bro people in Japan don't even have a computer in their house
@@phunweng962 Coding culture in india is on Boom right now.Iam a college student in india and literally everyone here only talks about competetive coding
I was just learning how to code, but I learned that it’s time to quit
Edit: the replies have changed my mentality. It’s not time to quit; it’s time to improve.
I think you should edit your comment to say:
"It's time to improve ", bro.
Brandon Castillo good advice
Same here lol, regretted clicking this video tbh
its google interview
🤣🤣na bro come on you jus gotta keep grinding
Clement: I'm going to take your interview now.
William: Well first, let me give you a lesson on graphs.
😂😂😂🔥
As he talks about it I can see the strongly connecting components dancing with the representative nodes.
Hahaha
I thought the same thing 😂
He does a very good job at visualizing and properly explaining his thought process. Very impressive. His explanation is also well structured and he seems very confident in his knowledge. He is definitely gonna make it.
He would make a great teacher.
I think at this point he already made it
He already made it. He won huge competitions and has a successful youtube channel. He’s a student at MIT rn so he’s set for life
I dont expect less from an asian kid
I used his code and it brought back my dead cat to life.
😂😂😂
😂
😂😂😂😂
I cannot deny that
Fr
if I'm being interviewed I say "Well first off LGA is a terrible airport"
And then if they don't laugh, just awkwardly stare at them for the remainder of the interview with no other word spoken.
@@azonnoza thanks both of you I’m crying
@@azonnoza hehehehe
@@azonnoza why bro, you made my blood pressure rise up.
Always go jfk
Few years later...
Clement : Google coding interview for a baby who is about to be born in 3,2,1. Now!!!
Lol
Typical quora question: I'm a zygote that's just been conceived by mommy and daddy. Is it too late to learn how to code?
HT Rajan Cracking up HT. It’s nver too early to start!
@@htrajan No, coding is transferred through genetics and requires at least 5 generations to establish
@@htrajan Aah, reminds me of the days, when instead of code it used to be JEE preparation
What struck me about this interview is that the question is an extremely basic graph theory question, and most of the discussion is just about implementing very basic ideas from graph theory. With that being said, I know that I would fail this interview, because I definitely couldn't implement all these steps under pressure. This makes me realize that to work at a company like this, the skill you need is not to be a genius problem solver, but rather to be familiar with the already existing basic techniques, be able to explain them clearly to a layperson, and code them cleanly on the spot.
Yes yes and yes.
Familiar with the techniques, connect, clearly explain, and cleanly code them is a lot more difficult than it sounds
This was not an 'extremely basic graph theory question'. It was hard!
@@RenatoOliveiraGaming
Lmao.. its basic Question.
Actually I didn't even understand the Question that was asked but What The Student is explaining is very Basic stuff.. I just passed 3rd semester in university and I had thus subject called Data Structure. Lmao... its all that stuff.
It's piece of cake.
@@pets9921 in general a question like this is kind of labelled "basic" only because it's one of the first concepts you'll learn when looking at graph theory, connectedness, and traversing nodes. shortest distance between two nodes is a very common problem in its own, in this scenario just depends on the algorithm you implement which gets more and more complicated. the question will always be in general very simple, just knowing which implementation to use and how it works to replicate it is the main hard part.
This interview gave me an unexpected and unnecessary stress.
same lmao
@@wegojim732😢
😂😂😂
Congratulations to William Lin who just won the 2020 IOI championship with the only full score amongst the top competitors across the world.
I like how William is literally giving a lecture to his interviewer😂
True lol
And you can tell by the look on the interviewers face his ego took a little hit bc he's the interviewer and he's being taught by a kid lol
im pretty sure the interviewer just wants to know how much the kid understands. kinda the point of the interview
LMAOAO THAT S WHAT I WAS THINKING
@@Jaybiv interviewing tactic and you think that his ego is hit. he has seen numerous different ways to solve the problem.
You know he explained it very well from the fact I didn’t know ANYTHING about directed graphs and strongly connected components but his explanation made sense LOL
Thought it was only me- although I've never heard this term before, yet when he was explaining, i thought to myself "hey, that made sense"
my understanding stopped at 2:19
you are bad as **** bro, mine understanding stopped at 2:57 :3
Serious. I'm still laughing with this
focus and a lot of practice and tutoring will help you understand problems like these
@@brandijohnson1326 Dude ur right. I focused. Didn't give up. Practiced a lot after watching this video and I still don't understand.
Hilarious 😂😂
I can honestly feel the sheer happiness in william's face when clement starts asking questions. Its like he is really enjoying solving this problem. Way to go!
I find William's voice much more calming than the interviewer!
I like his problem-solving process. Drawing out the problem, simplifying it, planning the steps. It's so methodical.
I also like how he checks with clement if he understands up to that point, that shows that he is really thinking clearly.
That is far more better than misunderstanding the question right?
Clement is so lucky to get taught by William!
I will make sure to watch this video multiple times to understand 2 things:
1. What was the bloody problem statement?
2. And the solution
1. AFAIK Your job is to provide shortest route from START airport (LGA) to any other of the first array. Yet your job is to create new *least* amount of paths from LGA to those Airports that are unreachable from LGA at the moment.
2. HE builds GRAPH. HE compresses it (reduces interlooped nodes to 1 node) with Korasaju algorithm. Then he searches the solution for the shortest route for any given END. The last part is something i can predict, cuz, well, i've doing my stuff listening to the video on background since minute 15 i guess... he reversed links of the graph, so, during the solving END became START and LGA (initial START) became END.
Lol
@@Vasilevus as a student i want to ask you. How you able to solve and make logic of such type of complex problem.
Please reply and guide.
@@Vasilevus yea, I still don't understand
Can't give you nothing but one stupid suggestion : practice. I've solved similar task once. I suggest to practice it the tough way - use C with least libs included, no segfaults and memory leaks. Just juice the best out of the problem: crack the algo down and get used to the conception of memory usage and structure composing altogether.
Me: I wanna learn how to code, let’s watch some interviews!
Me after this video: Time to apply for a job at McDonald’s
😂😂😂y'all just killing me
Hilarious 😂😂😂
Second year in college.....still trying......still.....
Don't look at it that way, William doesn't possess anything you do not possess, the difference is in time spent. You can always improve yourself, and you also don't need to do it alone. Good Luck on your studies!
You can code without knowing all of these. They're only important for higher posts. And you can just take some courses, maybe free even, and they're easy to understand.
The smart kid in math class explaining to me what math is
If this is how you get into google than I'm happy working in McDonald's.
Ahahahha
Lol I swear 😂🙏
HAHAHAHAH
Ashutosh one burger plz😂
hahahahhahaha
Me after one coding interview: "Mom, I think I need to re-enroll and take culinary course instead."
*TEARY EYES*
No because there always an Asian that’s gonna out do you in that too 🥲
😂😂😂😂
And you'll meet Gordon Ramsay in your interview
It's always gonna be like that brother, no matter what field, not matter what company, not matter how experienced you are, you will always have bad interviews. Sometimes it's your fault, sometimes it's the interviewer's, most the time it's both.
All you gotta do is to not underestimate yourself, do everything you can and if you fail tell to yourself that's more experience. Maybe next time you'll be less anxious, maybe you'll be more prepared, maybe you'll present yourself differently, etc... But it can only get better ! :)
Then Gordon Ramsey in the interview: what kind of food is this, you fuukeen donkey?
He made an extremely non trivial problem look...trivial. What a beast, well done William!
Interviewer: [explains problem] what is your solution?
Me: do you know stackoverflow? well I do and there's your solution
edited: oh wow didn't expect this to hit 900 likes, thanks everyone!
Literally Me!! hahahahah.
@@otakuu9609 same! lol
I would go for a more general answer and say : GOOGLE
One thing folks never compare yourself, the result which you are seeing is not just one day of work it requires lots of practice and dedication to develop such skillset.
Have a great day ahead.
Python exactly! Thank You!
Ty bro
I sometimes believe that kids like him were born to do this, just like any athlete..yes they worked hard but they were destined to become that good.. thats the conclusion i came too,, could be wrong but thats what helps me not comapre myself.
The fact that I didn't practice as much as he did is what hits hard, not just that he's great at what he's doing, because he's more competent as a person
This is what is called a competitive programmer. Probably he is used to compete in sites like codeforces, hacker rank, URI, etc. I used to hang out with folks like him. Learn a lot from them but was quite difficult to keep the same level as their.
Clément is like "yeah it totally makes sense", then he makes that expression like "I have no idea what he's doing, but I trust him" lol
I hate that, he should've pressed more for an explanation because the strategy was convulated and confusing.
@@09SmashingPumpkins It's convulated because you don't understand it
@@09SmashingPumpkins It wasn't
The problem here is that, william only has 45 minutes to find, explain and programm a solution.
Clement is owner of Algoexpert - I doubt he had trouble following some abstract concepts.
I understand a lot of the coding and the physical logic, I am so blown away on his problem solving skills and his ability to think of pretty optimal solutions within minutes of reading the problem. It would take most people hours to think of even a half optimal solution to this problem, he solved the whole thing and explained it in 45 minutes with time to spare.
Its beautiful how an interview turned into a lecture
I am proud that my name is William, just because of this guy.
🤣🤣
LOL
😂🤣😂🤣
I started watching this at 1 am instead of sleeping, and I don't even know anything about code.
I’m with ya
Welcome to the club hello world
Same here
You should get started.
It's fun
@@yawarmushtaq6000 how fun it is to be sleepless everyday
I'm a sophomore in college and just took an algorithms class that goes over a problem like this! I noticed it was a BFS algo pretty easily, but it's always difficult to put it into actual code. That's amazing that a high schooler was able to do this!
This kid is a coding genius who puts most people working in the field to shame. You're just a random ass college student, relax.
@@conocosz So overly unnecessary man
Bfs ?
@@bahriaproperties1143 after the post order search, I think a breadth first search (bfs) through the newly created list works, Ik for a fact the successive depth first search works tho
@@tens0r884 The guy is a sophomore who doesn't even qualify as a beginner in the field, and has a chip on his shoulder. Then looks down on the kid because he's a high schooler and gives gives him back handed praise. Necessary.
Me, a beginner: “Oh this will be interesting and insightful”
Me after watching this: “Welp. Turns out, I’m an idiot”
I felt the same way lol
@@willfelder4808 shit sounds like a bunch of bs lmao
I am dumb I'll be honest after watching this....and I'm asking myself why did I take this course
Welp, I've a got a long way to go....
ya fr i got an interview later and this rly did not help ajshjahsj
2:55 He smiles because he realizes that it's an airline problem. If you've ever been in competitive math, stats, or programming teams, you'd know that anything to do with flying and destination plots is.. insanely difficult.
Damnnn 😭😭😂
Could you explain why? I’m just curious as I don’t know much about this topic. Is it harder because you don’t have specific paths to follow like roads or variable changes due to the environment?
Insanely difficult, but it's also been done to death, so perhaps not so difficult after all. :) Now try on the stable roommate problem for size. I only accept answers in SQL. ;)
dont even get me started. its mainly the cartesian plane plots that are connected and blah blah that co relate to this
@@fortythirty Yes. It is also because of the environment. With a normal Chess or Rubix scenario, you have preinstalled paths. You can't go across the Chess board or turn once to solve these puzzles. With a plane graph, you could use one flight to get around the world, or use 30 different flights to get around the world. It has stumped developers for years!
Have to say, i understood this sooo much better now that I’ve taken my college’s data structures class. Looking forward to two more years then a lifetime of more learning!
Yeah, people shouldn't get discouraged these like most technical interview problems are really simple rephrased data structures problems that were made more to tease out how you approach problems rather than testing your ability to memorize content.
This is why I want to learn programing. What an absolutely amazing journey it must be
@@-karter-4556 then have u yet?
@@TheFriendlyInvader Thank you this made me feel a lot better I haven't taken my data structure classes yet still learning microsoft office and barely touching some Java and I had no idea what they were talking about n felt discouraged.
than*
Being a high school student, his programming level and his knowledge of being able to explain it over a video conference is amazing.
The kid obviously has a high IQ. IQ transcends age.
While all of the beginner software engineers are thinking:
I could definitely solve this with 1000 lines of loops & If else Statements.
Oh! my my😂🤣🤣🤣
check my comment above. 25 lines of simple code
I tried to make an algorithm that gives me the exact amount of locations and the locations itself that would need to be connected to my new „airport“ in order to reach every place from my new „airport“.
My solution before watching the video after the explanations was that if you do a new list that is a copy of the airports list, you can do the following:
for x in (copied airport list)
for y in (connections)
if x == y[0]
copied airport list.remove(y[1])
Explanation of the code:
Line 1 makes x cycle through the copied airports list, getting the next string after each cycle. Line 2 makes y cycle through the connections, getting the next string list after each cycle. Line 3 compares current x string with the first string from current y (the currently selected airport with the starting destination of the currently selected connection way). Line 4 is finally removing an airport (the final destination of the currently selected connection way) if the if-statement is true. It’s removing from the copied airport list (let’s call it the anchors list). What you’re left with is a list with every location you would need to set a connection (I think, thought about it for 10 min).
Edit: By deleting the list while going through it, you won’t end up going through already accessible airports. Wanted to add this because people might think it would result in deleting a whole „loop“ section where each connection goes back to itself original connection. That wouldn’t be the case though. And yes you would need to try-catch it irl because it would give you an error if you try to delete an airport that is already deleted/nonexistent (which is like 2 words spread over 2 lines)
I use 2000 lines. I am more productive than you all
@@birolklp5574 If this passes all tests, it would be a 10-line, O(m) solution to a 50-line, O(nm) problem. Great job!
Absolutely INSANE. Tbh my mind went straight to Dijkstra's algorithm when I saw plane routes. Which I understood at some point but could never code on the spot now. I've also been coding for 13 years.
My mind also flipped to Dijkstra's and A* algorithm very quickly, but only because i dove into Networking during my Bachelors degree. Impresive!
Stephan Brandt right, yea I also quickly thought about Ferasiskis algorithm and implementing some form of trachial loop as which might work
yes
Interesting... Graphs are the right answer when looking for an application programming job - but did anyone grok that, at it's heart, it's not even strictly a graph problem?
I mean, yes... you should always answer this AS a graph problem. Keep the solution you offer general, extensible, self-documenting and easy to understand. You should spend most of the interview walking them through a fairly bland and unsurprising answer.
After all, there's often a follow-up or spec-change... and if you have to rewrite your existing code, it's a major fail. So... stay general, and model the problem statement closely.
But then, when the interviewer is finally satisfied that you're just boring enough to play well in a team churning out unsurprising and predictable code... offer them the _"red pill"_ by pointing out that this approach, though fairly standard, is actually horrendously inefficient.
Imagine Morpheus saying : _"What if I told you, you're solving the wrong problem... and all this code is mostly an illusion designed to stop humans from realising the truth and freaking out?"_
Drop a closing tease, like _"I'm just thinking, this problem is actually a lot more interesting than it appears... for example, say we ever needed to run this over big data, I reckon we could consolidate hundreds one way destinations per couple of cycles, in-place, to get the same data without ever building the tree. Almost no heap utilisation, leaves the compiler free to use streaming SIMD and bring those ultra-wide registers into play. The cost saving in a server farm would be absolutely staggering.
Of course, it's not pretty - there'd be a tradeoff in readability and it's far less general... but still, it's shocking just how well this optimises."
Then, just let it hang there in the air...
Basically, you just said _"and, if that's not enough - we can use magic!"_ ... expect an arched eyebrow.
If they ask you to expand how you'd do that, then you can take them on a REALLY deep dive without compromising your previous 'safe' answer... and, if they say _"no need, we're very happy with what you've supplied"_ you've still shown you may have hidden depths in terms of problem analysis. In the latter case, you can safely assume there's not likely to be much challenge or opportunity for progression.
Sometimes, you'll be asked to re-interview for a different role. You see, there's the UI's and the Apps, and Client code... that's all really safe and boring, and it gets a lot of employee churn. Then there's the behind-the-scenes bread-and-butter data crunching work that pays the big bucks and requires more analysis, problem solving and reductionism.
You can interview for both, but let them choose what they want to see.
Get it right and you'd be surprised how often you can essentially get hired to a role that's not even open, just to stop you walking out the door. Standard library coders are ten a penny these days, but the kinds of folks who can reduce a problem to it's essence and can switch between high level to machine level, well... the universities just aren't churning many of those out.
We live in a world where everyone and their grandmother can code, fewer can program _(yes, it's traditionally a different discipline)_ ... and fewer still have a solid appreciation of how to move a problem into the processors domain _(as opposed to wasting resources bringing the processor up to meet the problem in the natural domain)_
But, you MUST provide the safe answer first! And deep-dive only by invitation, right at the end... offer too clever a solution without being explicitly asked, and you're unemployable! - They'll step over you on the way to the next interviewee : )
exactly i thought the same thing.... dijkstra's but the kid is awesome.... 👍🏼
A few months later, Watch William Lin conduct the coding interview of Clement.
wow this guy's explanation on SCC was perfect, I can see how deeply he's understanding about the algorithm. i learned a lot, thanks
You know he is good when he sounds like a tutor to Clem. Damn.
Finally being able to see how a coding interview should have been conducted successfully.
first starting from your intuition and explain your ideas
Then outline the steps in the algorithm explain detailing each step
and finally do the code
(Rather than seeing myself having awkward silences and making nonsense answers)
I am a freshman comp sci major taking discrete math right now and its kind of cool seeing some of the concepts of that class "coming to life" in this coding interview
Trust me buddy you’ll be fine out there even if don’t remember graph theory by the time you graduate. Most companies looking for developers are not doing shit like this as part of their business. I bet they don’t even use it in most Google engineering jobs.
Same with me! Just finished learning about the stable “marriage” problem, super interesting
@@gabrielordonez8011 lol so you just wanna be a code monkey? you're basically just a typewriter then? no original ideas, you'll just write whatever you're told, sorry dictated... that's a sad approach to cs
I'm impressed by his knowledge of network theory. I'm a mathematician and did a good chunk of network theory throughout my degree and he's got a good grasp of all of those concepts despite being in school still. I always allow for a bit of stumbling as everyone gets nervous in interviews, so his understanding is clearly very strong taking that into account.
*hey I'm learning to code, lets check out what an interview might be like down line
"welp, guess I wont be doing that anymore"
bhahahaha, yup, my thought exactly. Uninstalling pycharm right this moment!
Feel that
I think the kid in the video is dragging on for too long. He goes on tangents that don't have a directed end. I wouldn't hire him because he isn't answering the problem layed out before him. Solve the problem first, explain your solution later.
of course you won't if you have that attitude, this problem isn't that hard unless you're a beginner
@@nilen I was wondering if you could help me I'm a student. I'm studying on code academy and I was wondering is there a more effective way to learn code? I'm looking but the internet is a big place. If you could help I would appreciate it thanks!
I can't imagine getting to a point where any of this make sense to me. But I'm trying.
Good on this kid for knowing about graph theory and connected components. As soon as he mentioned LGA and I didn't see it on the list, I figured the problem out, but I have a PhD in combinatorial design theory. There is no way I knew these concepts in high school.
Ya my limited experience with discrete (math) principles let me understand perfectly well the kids solution, though if I were there, there would be no way I would be able to write code that nice and would probably take me 4+ hours before I could come up with a solution like his…
these kids keep getting younger and smarter. it's insane.
i can't see your comment anymore did you delete it? the one with hiring an msc guy
@@catedoge3206 I didn't delete it, but I don't see it here any more. Someone must have deleted it or something.
This has happened to me a few times now.
I don't even code but I really enjoyed this, I just got started on a very very very basic level and even still I was able to follow and learn a whole lot more than I thought of this just through his explanations even though of course a ton went over my head. Just a wholesome interview was really cool.
Me 3 minutes in: "Okay, back to Modern Warfare".
anddd that's why your life sucks
SOMEONE must be the consumer.
😆 🤣 😂
Paul Gomez who said his life sucks in fact I would bet money that you are unhappy and you feel your life sucks and you projecting.
@@diegocruz9080 The comment i was searchig for as soon i read that shit!
william is a really good teacher, it shows that he knows what he's talking about
I've never coded in my life and the concepts overwhelm me, but my mathematic and analytical reasoning skills are above average and he really makes me feel like I understand what is going on!
Plot twist: He's a great actor and just convinced the interviewer that he was right
I really like your professionalism. I once took an interview at a company which I won't disclose, even though I'm not legally obligated to, but that's not cool, who even though I passed the technical interview put me through another technical interview with the team leader for some reason (officially, there was only a technical interview and a team-"fit" interview), I guess he wanted to impose himself, and whilst I was explaining and thinking the problem he was constantly interrupting me, asking stupid questions, even to a point while I asked him "let me think a little, please, I'll explain in just a second" he continued intterupting me with "what are you thinking about? Tell me what are you thinking at" countless times. I ended up solving the problem and failing this last interview for another candidate. I'm really appreciative about your attitude to your candidates. I feel like some interviewers, given this position and ability to filtrate who gets in and who doesn't, have grown a big ego and suffer of some emotional issues. Then again, it might be just me, and I may too sensitive or have stupid expectations of them.
William is a genius! This kid has an amazing life ahead of him!
Great to see more graph-related coding interview questions, he is thoughtful, come up with ideas amazingly quickly.
im just truly amazed with his knowledge of data structures, he knows all these structures and their properties like the back of his hand
As a programming junior with not much experience this is so damn interesting to watch, even if I don't understand much. Impressive.
I love that you can tell how impressed Clement is, esp when William starts his pseudocode / outline. Holding back a big smile.
William Lin is so always so impressive to watch !
I also took the time to do this exercise in python with a totally different approach (took me a little over 1h though). I thought that using an object-oriented approach could work and it did rather well !
Since I have not done any programming studies I have yet to look into the complexity of my code so if anyone could give me feedback on it I'd appreciate it!
Here is the code (with comments) :
# Data given
airports = [
"BGI", "CDG", "DEL", "DOH", "DSM", "EWR", "EYW", "HND", "ICN",
"JFK", "LGA", "LHR", "ORD", "SAN", "SFO", "SIN", "TLV", "BUD"]
routes = [
["DSM", "ORD"],
["ORD", "BGI"],
["BGI", "LGA"],
["SIN", "CDG"],
["CDG", "SIN"],
["CDG", "BUD"],
["DEL", "DOH"],
["DEL", "CDG"],
["TLV", "DEL"],
["EWR", "HND"],
["HND", "ICN"],
["HND", "JFK"],
["ICN", "JFK"],
["JFK", "LGA"],
["EYW", "LHR"],
["LHR", "SFO"],
["SFO", "SAN"],
["SFO", "DSM"],
["SAN", "EYW"]]
Start = "LGA"
# Answer
class Airport():
# Initialize the class with the airport name, the list of airports, the list of routes
def __init__(self, name, airports=airports, routes=routes.copy()):
self.Connections = [name]
self.MissingAirports = airports.copy()
# Remove from the missing airports the starting airport
self.MissingAirports.remove(name)
# Find all connections in current routes not in the existing list of connections and remove them from the list of missingAirports
for i in routes:
if i[0] == name and i[1] not in self.Connections:
self.Connections.append(i[1])
self.MissingAirports.remove(i[1])
# Recursive method : when I add a connection to self.Connection it will be taken into account
for i in self.Connections:
for j in routes:
if j[0] == i and j[1] not in self.Connections:
self.Connections.append(j[1])
self.MissingAirports.remove(j[1])
# I now have the connections with the current routes.
# Find out the number of new connections obtained when connecting to a missing airport
def CountNewConnection(self, name):
newAirport = Airport(name)
Connections = self.Connections.copy()
count = 0
for i in newAirport.Connections:
if i not in Connections:
count += 1
return count
# Connect to an airport using its name and add the new connections to self.Connections
def ConnectTo(self, name):
newAirport = Airport(name)
for i in newAirport.Connections:
if i not in self.Connections:
self.Connections.append(i)
self.MissingAirports.remove(i)
# Create object using Airport class with the starting airport.
Start = Airport(Start)
#initialise the iteration count
iterations = 0
# #Loop : while the length of unique connections is different than the length of airports
while len(Start.Connections) != len(airports):
# Count the number of new connections when connecting to an airport for each missing airport
count = [Start.CountNewConnection(i) for i in Start.MissingAirports]
# Connect to the missing airport with the maximum of new connections
Start.ConnectTo(Start.MissingAirports[count.index(max(count))])
# add 1 to iteration count
iterations += 1
# return the number of iterations.
print(iterations)
# Possible to print to which airport it has to connect and in which order in the while loop.
yeah we totally dont get any of his algo hahahaha
Sorry, if I know this stuff I would have tried to help.
I Read your code carefully and after thorough examination I can say that I don't understand a single thing. Have a good day!!
Ya looks fine to me. *DON'T ASK QUESTIONS OR FEEDBACK*
Does it say hello world tho ?
I did a real coding interview when I was 16 for a remote job and I got my ass handed to me.
You tried, respect.
You got a coding interview when you were 16... That in itself is impressive. Hope your success continued in life! (success in just obtaining opportunities... not that you got ur ass handed to you lol)
@@SharmaGoopta123 Thanks man, you too
Atleast you tried
@@cap4081 just like riders said at least ya tried!
Have now subscribed to both channels. I programmed for about 10 years and then switched to Product (and have interviewed at Google). William's raw brainpower, problem understanding, high level solution description and coding while speaking/explaining (and while under pressure and being recorded) is impressive for anyone at any level and any age. Considering he won't hit his 'peak' for another 20-ish years, I suspect we'll be hearing/seeing more of him as a programming force of nature. Props!
Just because you posted when the interview actually starts, I decided to listen to the entire intro for your honesty.
*Title:* Google coding interview with high school student.
Apparantly, some college graduates are having hard time understanding this.
Really? This is algorithms class for Juniors
@@laggyfilms4768 I was replying to "Apparently grads have a hard time w this" and I was saying "Really? it should be easy for them". I am not talking about the "him" that you are talking about. I wasn't replying to the Title: line where Vitus is talking about the Title of the video but rather the next lines.
@@MaxRollison OoOoOoOOooOoOoOoOoOo.
@@MaxRollison ok Imma vanish...
I swear these gen z kids are smart as hell
Surprisingly, the graph he drew made it easier to follow. Thanks, William, you too, Clément.
Wait, this is the kid who is really ducking smart and won codeforces a couple times? Holy shit
He just got 1st place and a perfect score at the international Olympiad for informatics 😭😭
And he is like 16??
My solution to this problem would be, reduce our connections(A -> B) to just a list of B, create a map from our ports with each port mapped to False by default. Iterate through the list of B, turning ports[B] to True. our result is the length of a filter that filters ports(C, D) by not D
Note: This was completely inspired by finding the edges method he provisioned
I legit thought I was a good programmer before watching this video. Now im switching to Management.
Very elegant solution. Always fun to see William on the channel, and great interviewing on your part Clement!
let me just say that his text notification sounds really smooth
It should be noted that adding new nodes to cover in-degree 0 nodes will always at least preserve the number of total in-degree 0 nodes in the graph, or even increase the total number (if you add multiple nodes as the interviewer suggested briefly before retracting). Therefore, the incoming edges have to be from an existing node, and this node must be the Starting node if you care about preserving acyclity. Any other node would create a cycle if connected to the in-degree 0 nodes because of the topology of the graph.
Also to clarify, every node under the node that the Starting node points to can be disregarded because they are children of that node and thus can clearly be reached, and every parent node above the node that the Starting node points to (excluding the Starting node itself) will be able to be reached if the in-degree 0 ancestor nodes are taken care of.
22:10 Oh man. If that’s not the face of “he’s got the job” I don’t know what is.
@@Allie912 He is conducting a mock interview to which he will be given a result. His result was a “strong hire,” as per the interviewer’s feedback. I just pointed out the moment he seemed to have it in the bag. You don’t need to look into it that much.
@@Allie912 You don't need to graduate to get hired. Most people who graduate with a comp-sci are bumbling idiots anyway. Just like any STEM field. Let's not pretend that it actually has worth outside of getting you better chances of a job, if you're already competent enough, then it doesn't matter.
@@nizarch22 "bumbling idiots" 🤣 thats scary cause im planning to study comp sci
@@Allie912 he can be hired right away tf
More likely William will research at MIT or other prestigious college than work in an MNC. Yeah but you are right.
C: "How would you account for duplicate edges between two strongly connected components?"
W: "Doesn't matter."
C: "True."
Best part
As an applied mathematics student, it’s not too difficult of a problem; but approaching it from a cs point would make it more difficult with the syntax and algorithms tied to the language , but his understanding of graph theory is pretty impressive considering the level of abstract math it is and the level of math you’re taught in hs . Once you understand the graph theory approach tho , you’re setup for success. Great job to him !
Were you as good as him in high school?
@@rodney5269he never said he was
@@rayaanansari4834 He never said he wasn't ;)
So why did you assume he was
@@rayaanansari4834 I didn't that is why I asked him lol
He made the solution look so easy, and the explanation was just so easily digestable.
Me, thinking I'm really smart: Hah! That's a piece of cake! Just go through an array of all the connections and start by picking out the ones with the inputted destination as the second index of that connection. Now, from those, for each one connection, scan for those where index 1 equals index 2 in any other connection AND index 1 is equal to the departure airport in that connection. If no matches are found, it means there are no routes that short, and you just repeat the process but you go one step further until you find the departure airport.
While you do this you can list all the available routes, or just immediately display the minimum number of "jumps" you have to take to get to the destination, like this exercise asks.
**watches the solution**
Oh. I'm dum dum.
I like your idea more because I understood it XD
But O(n+m) time tho
I like ur solution better. Complex solution are always hard to understand and debug, even for adding new features.
Doesnt work...
I think your idea too would work equally well, it's also really simple and easy to understand. At some point in the process you described, you're bound to come across an airport in index 1 which isn't in index 2 in any of the other connections. This is equivalent to finding nodes with 0 inbound connections, and hence if you count such cases(excluding start point) you'll have the minimum number of connections to be made. One exclusion in this process though would be if there is such an airport in the 1st input list that has NO incoming or outgoing connections(and hence would not be taken care of in our first process), and for such an airport, an additional direct connection would be required. Even though William's brilliant graphical approach really helps visualize and provides an interesting approach, your solution would work just as well!
When a high school student can beat most graduates in the field -> the levelling is too much
I hope this shows people that a degree doesnt make someone good, This shows people that someone that put in the hours and the passion, that's what matters. He probably spent a lot of hours cracking leetcode questions.
To be a LGM like William it takes much more than just Leetcode questions.
@@Garentei Ofcourse you have to work on other stuff too, but still, the key is putting in a lot of hours, there is no magic there. Read/Practice repeat.
ikr, he probably doesen't even pay attention much in high school but do his own studying since, you know, high school is like 90 % memorization, 10% applying logic/skills.
EDIT: Danggg i'm right. looked at his channel right after this vid and look what i found th-cam.com/video/Q7p8nC_-qUo/w-d-xo.html
@@jgsource552 Actually pretty awesome, the path he was going was very good without university, he would have come equally far without it. Nothing against degrees, the problem of the whole educational system it is trash, it was and is designed to create workforces, people smart enough to "operate the machines" but dumb enough to not question the system. Anyway, if I had to choose a university it would be MIT.
And then you ask him to build a bridge, fix someone's aorta, or maximize your tax refund and he's like, "you mean with code right?"
Love how clement can't help himself and stop smiling every 5 seconds, its so exciting to be with a young genius ✨
Brilliant young man with a true gift for applicable visualization. I am now rethinking my life.
i like the way you said, "remind me and teach me !"
One minor mistake at the end, in the final if condition the last term should be: i != who[mp[startingAirport]])
Congratulations! You are now in Google now.
@@aviralsaxena2650 😂😂😂
Glad to see I was not the only one to spot it in my mind, but as both Clement and William did not notice, I was starting to wonder if I was correct !
I had to go through lots of comments to check whether I was right. lol
He says the correct thing but wrote the wrong thing, so just a typo
You smiled throughout his whole dissertation...
Very proud teacher.
Clement got taught a lesson here, by far the most detailed and complex interview on this channel and Clement's face said it all, gobsmacked.
I've been coding for over 30 years and I never would have come up with that solution. I can't wait to see what he becomes!
I learned a lot from you guys.
Clement, your acting is exactly as a interviewer, doing these little "ok" moments, where it always tickled me and made me think, "am I doing something wrong?".
Now I know that this is just the response from an interviewer to keep the neutrality so he can see if the interviewee is confident enough to support his argument.
And William, you just taught me how to be confident of supporting my argument.
Despite if the solution you're giving is not exactly what the interviewer expected (or otherwise), that doesn't mean it's not a better solution. It's actually very cool how you easily went through the problem with full confidence, and accepted possible failure, only to kill the task dead in its tracks. :D
I've been watching both of you for a long time, and I've learned very different things from both of you!
Happy to see you two in a single video.
Cheers!
I'm a programmer myself and I could not keep up with this kid! good stuff!
So 4 years of my math degree got wrecked by this high school student in an hour
was thinking the same thing bud
That ain't really Mathematic
This is incredible that a high school student has achieved this kind of a grasp on these algorithmic concepts. Virtually unheard of.
we get it man we fucking get it
When you tryna sound smart lol
Actually it's possible for lots of people, it's just that the things we learn in sch are different
If all you do is algorithms over and over in competitive challenges all of this becomes second nature. Is not virtually
unheard of.
@@nobytes2 Besides most high schools don't even offer Programming classes.
Probably went to some prestigious high school.
Thank u guys so much for uploading such valuable content, I learned a lot. As an Engineering Grad student I can't help but feel humbled by the later generations efforts and achievements, and I hope the open sourced collaborative environment continues to grow and become successful. ....but I'm not gonna lie, I also feel cheated by the system, for we pay a lot of money to get degrees and certifications, and even if we nail an interview, we still don't get hired.....esp, for decent positions that we worked hard for many years for....all in all, I wish everyone good luck and Godspeed.
His way of approaching the problem was amazing. So calm