Google Coding Interview With A High School Student
HTML-код
- Опубликовано: 27 май 2024
- In this video, I conduct a mock Google coding interview with a high school student, William Lin, who's also a competitive programmer. As a Google Software Engineer, I interviewed dozens of candidates. This is exactly the type of coding interview that you would get at Google or any other big tech company.
Check out the other Google coding interview that we filmed on William's channel: • Acing Google Coding In...
AlgoExpert: www.algoexpert.io/clem
SystemsExpert: www.systemsexpert.io/clem
My LinkedIn: / clementmihailescu
My Instagram: / clement_mihailescu
My Twitter: / clemmihai
Prepping for coding interviews or systems design interviews? Practice with hundreds of video explanations of popular interview questions and a full-fledged coding workspace on AlgoExpert - www.algoexpert.io - and use the promo code "clem" for a discount on the platform! 
Наука
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: ruclips.net/video/-tNMxwWSN_M/видео.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?
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?
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
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....
@@nischayrawat682 2 = 10
No, B is for Binary Tree Reversing
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 ?
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'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 RUclips, 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
I used his code and it brought back my dead cat to life.
😂😂😂
😂
😂😂😂😂
I cannot deny that
Fr
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
Others programmers: "Hello World"
Me, as a noob programmer: "Goodbye World"
Why this has no likes?
JAJAJAJJAs same
Bro 🤣🤣🤣😂
I feel you man
@The tech q actually, depends on the language hes working with.
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.
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
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
“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?
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.
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.
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
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.
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"
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.
RUclips 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 RUclips red because I use RUclips for like all of my tv related entertainment
@@brentmadison7605 you must be over 40
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 made an extremely non trivial problem look...trivial. What a beast, well done William!
I love that you can tell how impressed Clement is, esp when William starts his pseudocode / outline. Holding back a big smile.
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 😂😂
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.
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
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?
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
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
to be honest his probably much smarter than the interviewer. He probably has an IQ above 130 and struggles to find people with the same intelligence level. My dad was the same way and always called everyone an idiot. I am not even with an average intelligence struggling in life.. D:
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.
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.
This interview gave me an unexpected and unnecessary stress.
same lmao
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
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.
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.
That's why he is a competitive programmer
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
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!
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.
He made the solution look so easy, and the explanation was just so easily digestable.
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?
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.
His way of approaching the problem was amazing. So calm
Just because you posted when the interview actually starts, I decided to listen to the entire intro for your honesty.
Congratulations to William Lin who just won the 2020 IOI championship with the only full score amongst the top competitors across the world.
The smart kid in math class explaining to me what math is
Wow!! He simplified the problem of having to deal with original "space" X into X/Q where Q is set of equivalence relations (aka strongly connected components). I wish I could have that much composure under stress, he's definitely going places!!
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 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.
Clement is so lucky to get taught by William!
William is a genius! This kid has an amazing life ahead of him!
When he was drawing out the graphs and reducing them down, I finally understood what he was talking about.
Real humbling to be taught by a high schooler as a 31 year old.
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
I find William's voice much more calming than the interviewer!
You smiled throughout his whole dissertation...
Very proud teacher.
Imagine interviewing the future CEO
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!
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.
Whoa….. I’m a true newbie!! Deep stuff and very interesting to watch the skill he had while solving it!! Excellent!!
I love how he programs like a normal human programmer and doesnt use tons of stupidly difficult jargon to explain his concepts, like I actually understand him wtfff
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!
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!
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.
Amazing. Clean, fun to watch and SO educational. Great job! Thanks you so much!!!!
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
*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 am not that competitive as Williams, but I do agree with the last comment part from Clement about naming variables. Because it’s a good to have for the future and for others who may read or even continue with the same task.
Damn, this kid can explain so well and concise. Even as a non-programmer, i able to understand.
Bruh, stop making me feel incompetent lmao
@ Gaurav G..right? Flip(positive side) is to be inspired.Easy to be de- motivated for sure but cool to see talent + hard wk.
Work hard bro i am sure we will achieve more than the william lin.
@@bigsmoke1179 I don't think so, William is intelligent. Some people are naturally smart. Like Einstein. He was too smart to be in school. Regardless, you should always work hard to achieve your dreams.
@Atharv Khatri hard work only beats talent if you assume that the talented person isn't working hard as well.
@Atharv Khatri Don't joke yourself, evidence as shown some people are naturally smarter than others. Yes hard work can make you good at a subject. But some people no matter how hard they work at a subject will not beat someone who has natural talent in that subject who put in minimal effort.
I am proud that my name is William, just because of this guy.
🤣🤣
Damn I’m jealous
LOL
😂🤣😂🤣
This is really impressive, I had python in college and the tests were kinda like this, it was rare for people to pass.
This is a problem I feel like I could solve (but not within 45 minutes, a few hours haha), this video is really helpful. Learned a lot of tricks and gained some confidence in my math/coding abilities back, thanks!
I can't imagine getting to a point where any of this make sense to me. But I'm trying.
Its beautiful how an interview turned into a lecture
These videos are awesome. Wish I had something available when I was in school/college. These is lot to learn from this.
This is really enlightening. What I learned from this interviewee is the importance of mapping out the problem as opposed to starting coding immediately, and also explaining it out loud. I couldn't understand everything discussed, but I got enough of the gist, that I knew what the solution would kind of look like
Yep creating a relational model and/or writing out your step process for the design is all very important as part of the pre-planning process.
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.
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.... 👍🏼
This is impressive and I cannot understand it completely. I came up a straight forward solution, please point out if if something is wrong.
1. build graph, iterate the routes and fill up 2 variables; the first is the "Map degree" (key is airport name, value is the total number of inbound airports), the second is Map directedConnection (key is airport name, value is the list of outbound airports).
2. iterate degree, pick up every airport with 0 value in degree. put them into queue, add queue.size() into output (an integer variable), and start BFS to traverse from this queue, use set visited to mark down the visited airport.
3. handle the airport those from cycle and without one airport with 0 degree, just iterate the airports array, if it is not visited, output++ and put it into visited.
4. return output, because of the set visited, we will avoid duplicated traversal.
Thank you for reading.
I'm a programmer myself and I could not keep up with this kid! good stuff!
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!
A few months later, Watch William Lin conduct the coding interview of Clement.
kid is amazing, love seeing a brain like that work through problems to solutions!
Love how clement can't help himself and stop smiling every 5 seconds, its so exciting to be with a young genius ✨
I didnt even understand the question lol
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)
dude, as soon as he started to explain the strongly connected group, that was like 5mins, i already realize the's going to nail this
It's an absolute pleasure to watch this kid decompose a seemingly complex problem into its most foundational form (directed graph), and then develop a solution to the most basic form of the problem, and then expand the solution to a more specific, more complex problem (airline). the basic steps should be
1) Formulate the problem into a directed graph with strongly connected elements where strongly connected elements are group of nodes (airports) that can connect to each other with its own subgroup so once we arrive in one node (airport), we can arrive in any other ones
2) redraw the directed graph into a simplified/compressed version where group of strongly connected nodes are now a single node
3) identify nodes that do not have any other nodes connected to itself (indegree 0), these are the nodes that we must create a connection from the node (airport) we started
4) where we started can also be indegree 0
If you follow this logic, it's really cool but extremely hard to get to such a simplified version of the problem as quickly as he did (unless you've already done a problem like this in the past). Each of the 4 steps he outlined in his plan can then be tackled without problems.
*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
Great to see more graph-related coding interview questions, he is thoughtful, come up with ideas amazingly quickly.
Likely he used korasuju to find scc(strongly connected components) ,and then labeled all node in each scc as one label.Then using Kahn to find topological order,and eventually find the answer in topological order. What a amazing !
I don’t know a single thing about coding, but I can kind of understand what’s happening. It’s just fascinating to watch his mind work
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
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 just saw my graph theory class come to life. It's beautiful.
Man this is crazy. It amazes me how people can be so smart.
I am just starting programming and finding it a bit difficult but this seems to be on a whole other level.
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.
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’m watching this video and i have no clue what was going on for the large majority of it but i watched the whole thing, this guy is insane with his skill. I’m 16 and this makes me feel like i’m wasting all my time and i’m not learning anything. This is really inspiring though