Google Coding Interview With A Competitive Programmer

[@clem]

Hope you all found this coding interview insightful! And check out the video we made on Errichto's channel where we chatted about coding interviews, Math in Software Engineering, and more: kzbin.info/www/bejne/j2m5lqyCfJiBnrs

[@danielk8452]

Thank you, mock interviews like these are really great to share :)

[@akshatgupta1904]

Sir, I wanted to ask that can we practice competitive programming with Python or our only choice to go for CP is through C++ /Java?

[@aetherllama8398]

I was inspired by your midpoint idea to make an O(N^2) general solution. Two lines with the same length and midpoint form a rectangle. diagonals = {} #python dictionary count = 0 for Point A in points: for Point B in points: key = [ length(A,B), midpoint(A,B) ] If diagonals{ key } == NULL diagonals{ key } = 0 count += diagonals{ key } diagonals{ key } += 1

[@jishnugopakumar]

cant we just rotate all those points 45 degrees in any direction and make the diagonal lines horizontal or vertical. So we could use the same old code for searching diagonal rectangles also.

[@aetherllama8398]

@@jishnugopakumar No. They are the diagonals of the rectangles, they could have any angle so rotating them 45 degrees would not make them horizontal or vertical.

[@Errichto]

Spoiler: Google didn't hire me. Apparently, Clement is an ex-Google engineer and this wasn't a real interview :(

[@clem]

Double-spoiler: if this _had_ been a real interview, I would have given you a Strong Hire.

[@SajeelCodes]

You are hired, Errichto, start your job from 32 April, 1985 Lol

[@raghav4711]

@errichto: holy shit dude, you fucking killed the interview!

[@wulymammoth]

Raghav hahaha! He’s #50 on Codeforces (grandmaster). It’s like watching a superstar at their respective sport. Even with sheer hard work, it’s nearly impossible to reach that level without talent as well. Fortunately that’s not the expectation that top tech has. Google does employ Petr, though, who has always been top 5 in Codeforces

[@bunchofiitians5900]

Lol, If there would have been a Google interviewer who didn't hire Errichto, Google would have fired the interviewer.

[@Bharanivijay00700]

I just learnt to display "Hello world" in python. Now this video is recommended to me.

[@unitedasone9621]

Bharani Dharan 😂😂😂

[@danshao]

Didn't you know? You'll be a pro coder in about a week! Programming is easy :)

[@RabbitConfirmed]

Dan Shao fu

[@tawseeftaher9109]

@@danshao please suggest me some sites to learn Python/programming.

[@erniejeashvillahermosa5699]

hahaha

[@TheQA247]

Before Interview: Confident in Python skills During Interview: Draws a complete blank when given a code challenge After Interview: Crawls in hole and contemplates current career choices

[@yesaeses]

Learn c++ everything will make sense

[@coffeeenthusiast8774]

@@yesaeses should i learn C/java first before jumping to C++?

[@yafi2475]

@@coffeeenthusiast8774 No need.

[@evgiz0r]

Just try completing small to medium projects almost alone without googling how to for loop. If you are programming with copy-paste and 17 tabs open explaining the basic methods, then try without those.

[@Jp-ue8xz]

@@coffeeenthusiast8774 NO JAVA. Jumping from Java to C/C++ makes people whine when faced to pointers, pointer arithmetic, and other abstract concepts. I've seen it multiple times in 2nd year students who came from different colleges. You should learn C/C++ first, then go higher-lvl langs. And I wouldn't jump into Java unless I'm literally starving and can't get any other job xD

[@DaMainDude]

"I'm quite good at computational geometry" - well there is something I didn't know existed.

[@Ecell_2023]

Dude the first question was a basic combinatorics question in maths its extremely easy to implement

[@quadroninja2708]

A lot of games are filled with it

[@Tetrahfy]

Dude get your fucking shit togetther

[@geckogeico2212]

@UCvxbsNm-80mD0BggH-95rew go fuck yourself

[@HyrumCooper]

@@Ecell_2023 I know this is an older comment, but just wanted to mention that the first question wasn't actually a combinatorics problem because the points aren't necessarily arranged in a grid. If we could assume that the points formed an m x n grid, containing every (i, j) such i < n and j < m, (as in the example drawing), then we could solve it using combinatorics, but this would be a false assumption.

[@Hallden_]

Great idea for a video! His knowledge, the idea for the format of video and you as the interviewer is well worth the (as of writing this) 1.5+ million views. Nice work!

[@poisson6673]

Kalle sir omg! U r the python goat

[@techiedev7290]

OMG Kalle Hallden I love your videos!

[@loudsquad2324]

IMO: Get Kalle on here Clem :)

[@simonbachmann2120]

writing code in google docs brings cancer to my eyes

[@encrypted983]

Lol

[@mattmmilli8287]

Simon Bachmann IKR, there are a dozen websites for this now or live share in vscode even

[@PSUC3]

Interviews are conducted in pseudo code, so this is the most realistic way to conduct it.

[@cebulagner]

I had an SQL interview there, yeah its only in Google Docs and you have to imagine everything (scheme, db name, fields etc..)

[@xxstealerxx]

@@PSUC3 no it's not. Even on a whiteboard it wouldn't be as cancer as this as you have more width and can eyeball tabbing

[@saiprajeeth]

For every aspiring software engineers out there, watch the last 5 minutes of this video. It is GOLD and it will provide answer to all your insecurities about problem-solving abilities. I thank Clement and errichto for making this. Looking fwd to watch more

[@clem]

Love this comment, and I’m really glad you found the video so helpful!

[@nudeood]

@@clem Thank you for this video and advice. I just dropped out of a computer science PhD to get a developer job and I feel so out of practice with coding. I immediately thought of ways to approach the first problem but I don't think I could engineer a working solution with good use of data structures in a high-pressure interview. You saying that you wouldn't expect a working solution really put my mind at ease.. even so I definitely need to do some practice

[@peterlucas6732]

"I'm quite good in computational geometry"... you sure you want to ask me such a stupid question?

[@ItsAllEnzynes]

Peter Lucas for someone who is good at computational geometry he sure picked a really complex solution... For no diagonals where n = amount of rows and m = amount of columns the solution is (n-1)!(m-1)! With diagonals it’s (n-1)!(m-1)!+ (n-2)!(m-2)! You could optimize both those equations pretty easily with some simple dynamic programming and get the runtime to O(n). Edit: my solution answered the wrong question incorrectly. Rip.

[@kieranhorganmallow]

@@ItsAllEnzynes You're given a list of (x,y) coordinates. Not the dimensions of a grid.

[@Bunny99s]

@@kieranhorganmallow Right. Also no one said the coordinates are limited to whole numbers, just that they are axis aligned. So the points (10.123, 5.321), (10.456, 5.321), (10.123, 7.5), (10.456, 7.5) do form an axis aligned rectangle. James "solution" seem to only address the number of rectangles in a full grid of n x m points. This was not the question. If you go back to 03:20 they actually make it clear that in order to form a rectangle you need 4 points in the array. They even discussed the example of deleting the middle top point in which case there is only one instead of 3 rectangles. Rectangles could even overlap / intersect. Optimising factorial calculation is also pretty pointless. It would only work with relatively small numbers anyways. The result of "12!" is already larger than what a 32bit uint can hold. (21! doesn't fit into a 64bit integer) About how to speed up the actual solution, the only thing I could think of is if you have many points it might be worth to first sort the points on one axis (at least for the axis aligned case). The arbitrary rectangle case could possibly simplified by first constructing all "edges" and put them in a map based on the slope. Therefore you can easily find parallel edges as well as perpendicular edges. Though the worst case is probably still O(n^4).

[@ItsAllEnzynes]

Bunny83 Bunny83 my solution was also wrong. The actual solution of a grid formed with nxm points would be f(n,m) = (((n-1)/2)*n) * (((m-1)/2)*m)) I had generating functions in my mind when I was solving and got careless :| Also yeah, I jumped the gun and skipped though the video, my solution is not for the problem specified

[@radrad5119]

@@ItsAllEnzynes I was thinking something like that as well... except mine was something along the lines of sum(width-1)*sum(height-1) where sum is just the summation of all the numbers leading up to it. It kinda looks like his in the video was more versatile. Like it was actually counting the rectangles instead of calculating them. At the start though I was also thinking about factorials before realizing they weren't working for me.

[@shreyanshsingh2627]

I like the confidence @Errichto has here. He very clearly stated he is good at computational geometry and even asked for something harder. Not for nothing grinding Topcoder and Codeforces for years is a pretty big deal!

[@FredericJardon]

For the second part, the diagonals were the way to go. If two segments intersect in their middle and have the same length they are the diagonals of a rectangle. Just modify the code for the first solution by using the center of the segment and its length as the key in your map. Solution would be O(n²).

[@visskiss]

Came here to say this.

[@rajeswarynarasimman3728]

+ The diagonals should not have a degree of 0 between them.

[@SteezyMD]

I agree that this is the most intuitive solution. Not sure if this approach could get better than N^3. I imagine looping over pts A and making lines with pts B, then for each C, we check if the distance to the midpoint of AB is equal to 1/2 distance of AB. Then we check for pts D in hashmap if Cx-midABx == midABx -Dx and Cy - midABy == midABy - Dy Im new to complexities but it seems like N^3. Maybe checking those D coordinates with hashmap and if statements makes it N^4

[@antonistrychalski5125]

This ended up being Errichto giving tutorial on algorithms to Clement

[@yunjiehong4649]

Antoni Strychalski And Clement is fired cuz he didn’t hire Errichto aha

[@smcalpha]

You can obviously see that Errichto has tons of experience in solving these kind of problems

[@abrarulhaque4614]

well duhh! Errichto is not just any competitive programmer you know? he is one of the best in the world out there so yeah obviously this was gonna happen

[@saedyousef]

He is familiar with algo since he was 16 Just watched the interview video on Joma Tech channel This guy is an algo beast

[@iamnoob7593]

@@saedyousef gennady korotkevich - Let me introduce myself.

[@Fgcbear15]

This gives me anxiety even though I have a job now.

[@tulsikhatri8694]

What type of ?

[@Fgcbear15]

@@tulsikhatri8694 Process Eng. My degree is not Comp Sci. Interviews in gen still give me anxiety.

[@charles-y2z6c]

I am old, have contracted short term 3-9 month projects my entire carerr of 40 years, i work 11 months a year. I have done so many interviews. My advice? You are a smart person, just go on as many interviews as you can with the atittude you dont care. I guarantee you will get hired.

[@ScylockeX]

@@charles-y2z6c I'd be fascinated to hear more about a career like that. What have you been doing all your life?

[@saddiqjeelani563]

@@charles-y2z6c It means a lot to hear this right now. Thank you.

[@hoagiesandwich]

My self-esteem doesn’t need this

[@AbCd-zo5tb]

Thank god i am not the only one.. phewww

[@AmanDeepSingh-xe9of]

Didn't follow much of the problem, but the composure of this guy is something to learn from. I'm super impressed :)

[@ShaliniNegi24]

+1

[@thane9]

I haven't written code in 40 years, but as a mathematician I could definitely walk someone through several ways to execute this counting, both cases. This was very interesting to see the code/shorthand in a modern programming language.

[@criptik5208]

What have you been doing since 40 years then

[@DoccyStars]

@@criptik5208 not coding

[@robinder_]

@@criptik5208 probably counting

[@g33xzi11a]

I guess C++ is modern by comparison to BASIC.

[@stevenborik3026]

@@robinder_ day made thank u

[@pratiksingh8650]

What a guy! The way he approaches the questions is just amazing.

[@artkuts4792]

So basically you're being challenged with leetcode exercises, pass the interview and then end up in a team writing yet another JS/Android framework where you won't use any algorithms at all.

[@DanAaronWhite]

100% accurate

[@rooberry-music]

How i wish tech tests would reflect the development work you'd be expected to do on the job. You don't interview a doctor by asking them to dissect a frog. Sigh.

[@TonyDemetriou]

I've been team lead on web/js/PHP/MySQL projects, and while I agree that you don't NEED to use algorithms like this to get the job done, I disagree that you won't use it. I've never searched for rectangles, but the same general problem solving mindset is useful for other real coding situations where you need to loop back over the same lists of data. You use the skills that you practice. About once a month I'll use this sort of mindset to write something more efficient, or to simplify the logic, or to mentally figure out the efficiency of a database query before running it to know if it'll impact service. Even then, mostly we'd be fine without doing this. But maybe once every six months I'll write an algorithm that makes a big impact, such as delaying the need for a $2M hardware upgrade by three years. The thing is.... You gotta know how to write solutions like this before you're able to know where you can use them. I've never learnt this because I think it'll be useful. I learnt it because it was part of my course (that I never thought I'd use) and then continued learning because it's interesting.

[@PerisMartin]

The point of this exercises is not to find out if you know algorithms or not, it is to test your attitude when facing a challenge and your problem-solving thinking process.

[@ItsAllEnzynes]

Tony Demetriou Tony Demetriou Ehh... especially in the case of Web Dev Id rather have: 4 engineers with a deep understanding of JS/PHP/MySQL and no sense of algorithms and 1 person who can write complex algorithms than who knows nothing about the tools used but is good at algorithms Instead of: 1 person who deeply understands the js/PHP/MySQL and 4 people who know can write complex algorithms but know very little about the actual task Ofc the argument can be made that teaching the algorithms people js/whatever is easier than teaching the js people to write algorithms, but depending on the task is that time investment really worth it? Wouldn’t you be worried those algorithm people would move on to bigger and better things?

[@JLRide]

This was entertaining to watch. I liked how Errichto remained so calm and composed during the mock interview. I've had an interview recently where I was asked an extremely simple question and I blankly stared at the screen for minutes before regaining my composure and completing the problem. I have a lot of respect for you and many of the software engineers who have done excellent during these interviews with those large companies. It takes a lot of knowledge, skill, and composure. Respect.

[@DavidAttenbraai]

5:06 The only part I can do...

[@chiedzacaroline9647]

😂 Same here!

[@andreihututui2619]

Had a good laugh ty :)))))))

[@Player-ix7rx]

How do you do it ?

[@uzimanamegabe3311]

Lol

[@amritnalam9994]

@@Player-ix7rx ctrl + scroll

[@sthubbar]

Amazing. It is like watching professional athletes. I know they are doing something that I can't and I respect their skills.

[@mikejohnstonbob935]

that moment when your interviewee finds a more elegant solution than your best solution in the first 15 min of the interview

[@ZimZam131]

Actually, I think they had an n^2 solution. Errichto's solution was n^3. But it was pretty clever, that's for sure.

[@numbdigger8558]

@@ZimZam131 Dude, it's clearly O(n^2 log n). Or even O(n^2) with hash table.

[@bigsassyster]

This happens. Sometimes the interviewer will have to think for a second if what the interviewee wrote actually works because they wrote something that is more simple than what they wrought.

[@iurigrang]

I doubt it was better than the interviewers solution. If you simply iterate through diagonal points, checking if the other points are on the hash table, that gives us O(N²) time and O(N) space, which is probably the solution he had in mind, since it's pretty simple.

[@m13m]

The way he was solving the problem it felt like a poet reading his poem. Thanks Clement for an awesome episode.

[@hoffie7456]

I don’t know a single lick of coding, how did I get here

[@mikeg8343]

Ex Hoffie I’m not even good at math

[@mariqstigler2197]

😂

[@Michi9609]

I guess Google wants you to learn coding, Demand is high and the future system will need many people capable of coding

[@hoffie7456]

Adestrix96 big brain answer

[@Michi9609]

@@hoffie7456 thx ^^"

[@hououinkyouma5372]

HOLY SHIT! They're on a whole different level.. I have so much more to learn. Just watching them discussing stuff I have no idea about is freaking exciting!

[@arunarkamukhopadhyay6443]

Clement: never interviewing a Competitive Programmer again!!

[@jishudohare9141]

Errichto is a super cool guy, he is totally chill and always ready to help you. He is awesome.

[@shrad6611]

I really love the attitude of errichto even with so special talent he dont have pride at all love you errichto

[@Zzznmop]

The awesomeness complexity of this channel is growing factorially. Haven’t even started the video but want to thank you for what I know will be AMAZING content. Thanks again Clément and Errichto! :)

[@clem]

They should test you on your awesomeness complexity in interviews! Who cares about time and space complexity when you've got awesomeness complexity?

[@shaekmrsyahoocom]

"I'm quite good in computational geometry".. when clement reminded only 2 mins left ''Take it easy".... Erricho is a gangster!

[@manishsharma2211]

Clement gets surprised every min when errichto writes code😍😍

[@michaeltolsma7717]

When the Google interviewer is completely overwhelmed by the interviewee...

[@Adam-cn5ib]

that's a bad thing cause it makes teamwork hard. It's better that everyone is on the same level

[@skilz8098]

@@Adam-cn5ib Not true because you need someone to lead the herd...

[@milanstevic8424]

@@Ricardo-C what I'm seeing as horrible is that there are people in power with an opinion like this. that means that hindering more capable staff is not simply a malign action from the position of envy, it is also a deeper mental organizational fallacy. from what I've experienced so far, yes, there are two fallacious modi when it comes to evaluating peers/employees: "I hate that you are so much better than me, I won't help you, in fact I see you as a threat to my status." "I believe that you should be a greater team worker than this, you should slow down a little for the others to catch up with you, you're just showing off and are too laid back, thus your behavior is unacceptable." I can accept the former, because it is always served incognito and can be deemed a personal fault. but the latter one is typically a formal statement, as evident by that comment, the guy is absolutely rational and firmly believes in this. this is unfathomable in my mind, yet quite a lot of big and essential organizations are fundamentally run by this mantra. horrible. no wonder the world is a mediocre place at such large scales. regression to mediocrity is a real, human-induced, effect. it definitely helps to explain the "bozo horizon" as well. for more on "bozo horizon": blogs.harvard.edu/waldo/2012/07/27/the-bozo-event-horizon/

[@milanstevic8424]

@@Ricardo-C Though the amount of likes you got, restores my faith in humanity to an extent.

@@milanstevic8424 that's deep in so many ways. Think about how this relates to minorities and victmism

[@sudosai]

2:10 "i can handle upto 10 dimensions". - Errichto

[@arkros1]

and yet right at 22:50 he can't even handle 2 dimensions correctly

[@justicechukwuemeka8138]

@@arkros1 You sound stupid (no offense).

[@rtubleiii]

Arkros wow so brash of you to say that

[@chhabisarkar9057]

@@arkros1 bruuh -__-

[@thegeekandthegedik]

@@arkros1 what's wrong with the formula?

[@RimantasLiubertas]

Solutions based on fundamental geometry: "hacky". Ok, then. Btw, if diagonals intersect in the middle and are of the equal length, you've got a rectangle there. This property is very often used by craftsmen.

[@ajuc005]

I was screaming at the screen. But then I'm doing 2d vector math all the time cause I make games :)

[@359Aides]

Had the same thought with finding center point of all lines and add them to a map. As soon as you find a an entry already contained in the set that should form a rectangle (and there should not be any duplicates +- floating point imprecision). Didn't think the implementation all the way through but it should come down to O(n^2)

[@nacl3470]

@@359Aides Yeah, there's an O(n^2) solution. You keep a dictionary mapping each pair to a counter. Then you have N choose 2 rectangles for each N diagonals with the same center and length. Here's a quick python solution: def num_rectangles(points): diag_dict = {} for i in range(len(points)): for j in range(i + 1, len(points)): p1 = points[i] p2 = points[j] length_sq = (p1.x - p2.x)**2 + (p1.y - p2.y)**2 midpoint = Point((p1.x + p2.x)/2, (p1.y + p2.y)/2) if (length_sq, midpoint) in diag_dict: diag_dict[(length_sq, midpoint)] += 1 else: diag_dict[(length_sq, midpoint)] = 1 num = 0 for v in diag_dict.values(): num += v * (v - 1) // 2 return num

[@briceparent593]

I may be wrong, but you could also just check for one square angle. If diagonals meet in their middle and there's a square angle, I believe you have a rectangle. I believe it just adds the same complexity though. (I'm speaking about the problem itself, in woodworking, it would definitely be more precise to compare the measures, unless you have a square that is at least as big as the shape you're checking)

[@xakkep9000]

TY, your "interview" helps me to get over the fear of interviews! You provide an excellent experience that I can try on myself. Now interview looks more like a predictable conversation, than a challenge full of surprises!

[@TGRRG]

In the 2nd problem, after finding the diagonal lines AB, you could attempt to rotate the axes to make the new cordinate systems for all diagonal lines AB, and then run the same logic that you used in the first problem. This way you iteratively run the simpler solution for varying coordinates based on the different diagonal pairs that you discover.

[@filip14528]

I think you almost nailed it, but you dont even need to run the simpler solution iteratively. You can use the same map structure but with more information in it. For example map where the angle is the angle and the pair is the pair that defines a line that goes through origo. You get the same O(N^2) time complexity.

[@DanT-iu6oc]

"I can handle two dimensions" IS FOUR DIMENSIONAL BEING

[@sparky5543]

You know, you just confused the heck out of a bunch of viewers :) Most people can barely handle a single dimension! For you coders, think logically beyond what I am saying, it makes sense :)

[@jan7751-o4w]

@@Maca64N May well be a lot more dimensions than that according to some theoretical physicists, but usually we like to think we live in 3 spatial dimensions and that's just about what our brains can handle. Time isn't a spatial dimension - it's just convenient to think of it as a fourth dimension in some cases. When it comes to math any finite amount of dimensions is usually no harder than 2 or 3. Infinite amount of dimensions can be a bit trickier sometimes.

[@rtubleiii]

James K. I think there is this animated TedED video that explain dimensions simply. It also mentioned a book and references for further reading

[@batmanarkhamcity3684]

no one literally no one errichto: ” Are you sure this problem is hard enough “ ? 😂😂

[@harshdobariya3858]

😂😂

[@hasantaz7832]

I don't even know programming but I can understand that this guy knows his stuff

[@brandonfremin6186]

I think the diagonal midpoint idea was the best approach. You can take every pair of points and calculate their midpoint and distance apart and make a pair where the first entry is the location of the midpoint and the second is the distance between the points. Then use a map to store how many pairs of points have the same midpoint and distance. Then iterate through all of the midpoints to count how many rectangles there are. If there are 6 pairs of points with the same midpoint and distance, you add 6 choose 2 (equals 15) to your answer, and if 1 pair of points have the same midpoint and distance, you ignore it. This should produce the answer in O(n^2) with a hashmap

[@maartena5169]

I agree. This is a slightly better version than what I thought of, I just looped through again and again, which is just a longer process for finding a combination of n pairs on a circle choose 2.

[@KurtVanBever]

I think most people overlook the most important takeaway from this interview : communication and teamwork. As you couls see in the second part, Clement shifted from being an interviewer to becoming a collaborator. Bringing different ideas to the table, putting in a different perspective and poning real time critiques... All of these contribute heavily to a deeper and more complete understanding of the problem by everyone involved. Great video guys.

[@Slimehardtshawty]

So is it normal for interviewers to help the interviewee along?

[@maherhayek9696]

For the second problem, use same code as first problem with the following changes: - remove if statement (get all pairs of points, not just vertical) - for each pair of points, instead of storing their y-coordinates, think of the pair as a line segment, find the 2 perpendicular lines that pass through each endpoint of this segment (let's call them P1 and P2). - Store the slope of P1 (sP1) and the intercept (iP1). Same for P2. So for each pair of points, instead of storing coordinates, store ((sP1, iP1), (sP2, iP2)). - And the rest of the code stays the same from problem 1. Everytime you find a new pair of points with same sP1,iP1,sP2,iP2, then increment the counter. - This is the same time complexity from Problem 1's code.

[@EnrahimRPG]

You get some serious numeric trouble with low or high slope pairs this way though..

[@Spiritusp]

His solution to part 1 basically solves part 2, u just need to have the right key (angle + 2 projections).

[@stephenhousman6975]

33:30 What you were looking for is that the 2 diagonals intersect at their midpoint and are the same length. If you are doing this approach the slopes of the 2 diagonals are opposites.

[@KPkiller1671]

The slopes are only opposites if the sides of the rectangle are parallel to the x and y axis.

[@-hero-5882]

I have a dream, and I don't care how challenging the field is, this is my inspiration

[@criptik5208]

Wgat does that mean

[@fredschneider7475]

For the second half, my idea was to create a map where the doubles are line segment length, slope and x-intercept resp. where the slope is zero or more but not infinite (a vertical line). The x-intercept is where the perpendicular (to the line segment) through the left point in the pair hits the x-axis. If the slope is zero, the x-intercept is just x. Otherwise, it's y+x/m where m is the slope. Then you could use the similar count trick from the first half. I think that would be unique. That would have O(N^2 * (log N)^3) complexity and O(N) space used. To get down to O(N^2), maybe you could use an unordered map (hash table) and have constant lookup time with a hash function, perhaps based on the sum of the three doubles. Maybe Errichto could weigh on that idea.

[@benjaminschulz2377]

the formula for checking right angle is actually x*x2 + y*y2 = 0 :) You can see this also for his example values:D Also this is calles the dot product or inner product. This is very much differetn from the cross product which is only defined in 3 dimensions and is something different:D

[@jwy4264]

Yeah this was a pretty weird mistake

[@RedEyedJedi]

The only time I felt, even slightly smart watching this video, is when I said slope before Errichto did.

[@parinjasoliya7836]

I feel ya bro

[@Ballltas]

Best solution that I can think of is: For every 2 points check every third point if draw lines makes 90 degree angle. If it does, then check if 4th point exists where it should be.

[@bitzartdev]

Wow that's elegant

[@gabriel-lyra]

If I am not mistaken he said something similar with option 1, but gave up on it, as looking for A and B points require N^2 complexity. Looking for a C point in an line requires N complexity. Looking for D requires a some very simple computation. Everything together and we still have N^3. Honestly I also can't think of anything better myself. Maybe you can do just like problem 1 and look for two pairs but with some kind of offset? I dunno.

[@devups6391]

Yeah I did thee same thing

[@SchweineSchnitzlBallerina]

i think, when you connect two dots, there will be a line

[@a_llama]

gg

[@violetviolence3358]

Got a "work as a taxi driver" add before this video. That's the best burn I've received this year :D

[@darksypnosis8171]

Damn

[@amazingvipul8392]

Hahaha

[@alexnezhynsky9707]

2:34 How many rectangles are formed on the plane... Why are we still here? Just to suffer

[@masindi5969]

😂😂

[@VideoArchiveGuy]

The sad thing is that these gotcha coding interviews weed out a lot of really good experienced programmers who just don't think this way. Sure it's great for vetting new college hires, but if say you're hiring a storage engineer they probably haven't done coding like this in decades. However, ask the person who does well on this test to write a bit of kernel code and they will likely stare at you with a deer in the headlights look.

[@guntandy]

isnt this test meant to test more about the algorithm than the syntax knowledge

[@JayLooney]

@@guntandy The point is basically that it tests that a graduate of a CS program learned CS, but that knowledge isn't necessarily fresh in someone who has a lot of experience actually doing software development work.

[@DanAaronWhite]

I agree 100%. I run my own software dev company and make myself a six figure salary, I’d never be able to pass this interview.

[@lorenzocabrini]

Not sure I agree with you there. First, I don't see this as a gotcha question, it is a fully normal algorithm example. Second, I think you make the mistake of treating all software development the same. If you're going to work on AI code, for instance, you are going to have to think this way. If, on the other hand, you are going to write storage code, kernel code or standard business applications, you need a different set of skills. By analogy, a nurse a general practicioner and a surgeon all work in the medical field. That doesn't mean they all perform the same tasks or even that they have the same specialized skills.

[@VideoArchiveGuy]

@@lorenzocabrini The problem is companies for the most part don't work that way. Whether you want to work designing UIs or doing development work on OS internals, you get asked the questions about sorting two dimensional arrays and how to write a program that generates BINGO cards.

[@SumitKumar-fn3gj]

This Is Kind a Motivation For me. Today I messed up very badly in Codechef Lunchtime. But i will keep fighting again and again and learn new Things.

[@shroud3354]

How many u solved??

[@hippopotopuss]

This is so clean and beautiful. Dude wasn't lying about his geometry skillz. Had to pause and catch up as well but really it's mad elegant handling of pairs.

[@basirahmed5431]

since last month i watch every day this guy Errichto i just love this guy the way he solves the problem and think. i love his confidence and he is the coolest and humble guy i have ever seen

[@SanixDarker]

The video just started, so i wanted to do the challenge too before seeing Errichto's solution, so this is the algorithm i propose in 3 steps : 1- I calculate the distance between all the points between them in the plane (x, y). 2- I recover points 3 by 3 in a loop that respect the Pythagorean theorem(finding the right angle). 3- For each triot, I look for a fourth point that respects the same law and I get my rectangles avoiding duplicates. Let's see his solution now....

[@SanixDarker]

Really Nice approach using vectors ! After thinking twice i could also use affixes (complex representation of each point X + iY ) of each point to get angles between them preventing me to loop throught 3 per 3 to get distances.

[@ruslikaici]

The distance idea is nice, especially because you could store the square of the distance and avoid rounding : map. I would use those distances to partition problem into smaller ones - (all 4 points from a rectangle should be have the same distance from them, so they should be all mentioned in the same list)

[@treqqqq2850]

I wish you do more of these youtube sessions with top coders or professional problem solvers :😂: and solve hard problems. It is quite educational and interactive and love to pay for that.

[@BigTimeCharley1956]

There are people who do screen dump videos of solving problems, I think searching for topcoder, adventofcode, codeforces, etc. on youtube would do it. I just watched on earlier today, it was hilarious because they had a few typo (that I noticed right away) and spent a lot of effort finding it; the *sigh* when they finally got it was precious.

[@jonathanconte1395]

Come on Clement ! I was studying algorithms and I had to stop because I can't resist watching this video !

[@clem]

My mission is to distract algorithm studiers with mock coding interviews!

[@abhinavraut3099]

same here!

[@lol_perry6835]

If I ever get asked this question in any interview, I would just start searching for other jobs.

[@FrazyNondoTV]

😂

[@yoursubconscious]

People like this are so fascinating to me, as an ESL language teacher. Just amazing how much "memory" a person like this "possesses". respect.

[@indiansoftwareengineer4899]

Nice to have winner of Codejam on channel. Liking before watching it Clement! 🙂

[@clem]

The only way to do it 😛

[@indiansoftwareengineer4899]

@@clem BTW how are you managing your FTJ with KZbin and managing Algoexpert too?? You are very hardworking, I too try to work more n more but brain shuts down after FTJ. Can't leetcode after coming from office. What can you suggest, to stretch more hours in "breathing n coding"? Maybe this would be good topic for your next video.....

[@clem]

@@indiansoftwareengineer4899 This is a great video topic; already planning on doing it!

[@indiansoftwareengineer4899]

@@clem oh, nice to hear that.🙂

[@joseortiz_io]

Yes! This guy is awesome! I first saw him in an interview with Joma. Im glad you got him in. What an awesome video 😁👌

[@reshulw884]

Clement please do interviews with Competitive Programmers more.

[@victornaut]

Why am I nervous?! I'm not even the one being interviewed!

[@MauriceBoulard]

so true dude! :) we all feel the same here

[@andrewilliams1974]

Cancelling my Google interview opportunity right now.

[@sumeetbhujang2756]

Still to figure out for me, was this interview motivating or demotivating ;)... He nailed it completely. Loved to see this entire interview.. very inspirational..

[@clem]

Hahaha, it should be a little bit of both 😛

[@Exeedo.]

I think the second solution also works in O(N^2). A rectangle can be defined as two diagonals with the same length and same midpoint.

[@AashayS]

True. They're are also perpendicular to each other.

[@Exeedo.]

@@AashayS Actually no. Only if it was a square.

[@lucianbicsi1636]

Fun fact: you can actually solve the problem pretty easily with idea #2.

[@daliborduric992]

just need to verify halves of the intersecting diagonals are equal length :)

[@pHuzi0n]

@@daliborduric992 Yep, I thought of checking the length pretty immediately and it is O(N) and rather simple.

[@julianelischer]

@@daliborduric992 yes generate all possible vector mid points and store them in a hash along with originating points (and length) (in lists), That would be ON^2 I think.. Then run through the hash, stopping only at those points with multiple entries. then you need to find clusters of lengths... For each cluster, the number of rectangles is I think (N-1).. Maybe you could move items from the first hash/list to a second one only when they get second entry.. so that last pass might be a very short list to traverse.

[@daliborduric992]

@@julianelischer edit: it's actually n(n-1)/2 + n which simplifies to n^2 although it will never reach n^2

[@julianelischer]

Dalibor Duric that is way too much work for me. It has two loops inside each other so I go for n^2. 😊

[@GiTsticker]

For the second part: 1) Find all vectors that share equal length with another. 2) Find all equal length pairs that bisect each other exactly in the middle. Also works for the first part.

[@viniwittke]

I'm not actually a programmer (so idk about performance using this method), but this seems like a smart and elegant solution to the problem. At least to my ignorant eyes. Can Clément take a look at this and dive deeper?

[@pweddy1]

Second problem: Facts: rectangles diagonals are equal length. Rectangle diagonals intersect in the center of each other. For all lines count the number of equal length lines that bisect each other in the center, plus or minus rounding tolerance. I think a divide by 2 should give the answer. I may have to look at it on pen and paper.

[@asandax6]

When a lengend enters the room you know because they don't need to think about any problem "THEY ARE GOOD IN COMPUTATIONAL GEOMETRY'.

[@iamnoob7593]

gennady korotkevich - Let me introduce myself.

[@skyrius5568]

I'm 99% sure in the second part when he said cross product, he meant to say dot product. The formula for a dot product is (x1*x2)+(y1*y2) and it equals 0 for right angles. A cross product would give you an angle perpendicular to the plane created by those two vectors (and we'd also be working in 3D instead of 2D at the point lol). But other than that, clever answer

[@jaydunn6859]

The KZbin algorithm letting me know I haven’t got a clue what I’m looking at by showing me an advert for glasses midway through.

[@Shri7hari]

We can find the slope and distance of all two points where X2> X1 and store them in a map. For each slope and for each distance check all the pairs in the loop where they make 90° with the bottom point

[@ManishSharma_msinvent]

@Errichto This is a legendary solution. It gets as beautiful as it can get.

[@manishsharma2211]

Welcome

[@brillianceplayground]

This man has serious skills! Love the idea Clément, keep up the great work 👍

[@soumyasengupta7018]

This is insane! The solution to the first problem was so elegant and simple. However, for the second problem when he mentioned the tilting way to bring nback the point in reference to (0,0), i fainted. It's just not fair to be this good and have so many solutions up for for sleeve! You cannot emulate this, nor should you try to. This is just courtside view of programming GODS!

[@huey1153]

You’re reaching

[@asense8152]

Yoga stretch. He’s good but I also like how humble he is. Which to me suggests he knows more people of his kind, some even superior in talent and aptitude then him.

[@Xaxxus]

It’s stuff like this that depresses me because I’d probably fail the first question in an interview.

[@IgorAntarov]

Try to solve one algorithm problem every day. In a couple of month you'll be amazed how far you can go.

[@mikeg8343]

Git gud

[@grizius4123]

@@IgorAntarov nice advice ty

[@jthymesthree602]

Mike G This isn’t Dark Souls dude....

[@CHROMIUMHEROmusic]

check out project euler, its a website with loads of problems like these. I myself must admit I haven't done any in a while but when I did, they were fun and useful

[@RedCurlyHead]

You killed it maan, you're my competion programmer hero! Regards from Bulgaria!

[@zedzempai123]

Approaching this with vectors is absolutely an incredible idea!!! I was amazed when he used the condition of colinearity! Thank you for sharing this :D

[@alexander14994ever]

Could you make a video on how to prepare for this and improving your skills. Also what resources do someone as good as him used to reach this level of skill! Great video!!

[@HAWXLEADER]

22:51 You were close, pretty sure it's the dot product you're looking for. x1*x2+y1*y2=0 when perpendicular. Also the thing you are looking for in 30:50 is 4 points with lines that intersects in the middle and are of same length. (distance from corners and the fact that they intersect in the middle).

[@DogeCharger]

things like these make me reconsider trying to major in computer science lmao

[@VortechBand]

Don't worry. These guys are handling just one field in software development. A very difficult one at that, and only represents like 1 % of all software development. In about 99 % of software development jobs, you will *never* have to deal with algorithms, O-complexity, compiler optimization, etc. And most of that 99 % is far easier than what these guys are doing in the second part of the video. So don't be afraid :) Backend development is mostly about creating data queries (database, cloud services, or similar) and returning the data in a specific format, and frontend development is about displaying and styling that data. Very simple stuff, that pays well.

[@cgme7076]

@@VortechBand :: Are you employed? I absolutely love programming, but I have been reconsidering my career choice for about 6 months now. I was in college and was doing nothing but acing all of my programming and math classes. However, I halted and took stock in what I was doing when I got burnt out from all of the classes I was taking at once; I wasn't sure if that field was for me. Sure, I could stay up all night and write a beautiful program. Yet I had the feeling, after pushing myself really hard, that it simply wasn't for me.

[@MonsterhunterFTWWTF]

Good, if you're scared of difficulty then don't major in something difficult.

[@patrickmarshall6594]

It is enjoyable to have watched this when this video first came out and been so perplexed that I was taken aback, to now where 5 years later a majority of what he is saying makes sense and the confidence to code it would be within grasp. 5 years ago I couldn't print to screen.

[@fr4nk777]

I would personally go for an approach based on diagonals. The diagonals of a rectangle can be stored as their mid-point and their length. ( map ) Then iterating through each pair of points for(A) for(C) and storing the pair if does not exist. Then each time we find another pair which has the same Center point and Length as one in the map, we found a rectangle.

[@EhrenmannMitDepressionen]

He did this so fast and understandable! He would be a great team member in my opinion.

[@Rx7man]

While the guy is no doubt smart (and has a computational geometry background), it also means he's probably solved a few puzzles like this already.. this may not have been any new concept at all to him

[@rtubleiii]

Rx7man He is in the competitive programming universe. He is also like a top puzzle solver in a famous competitive programming website

[@farhanhaider5652]

I don’t know why I watched this video, I’m a beginner lol

[@eh7931]

I'm not even a beginner. I just stumbled upon this video. I don't...understand.

[@aryanadiazcakasana4414]

of course you should watch it.as begginer strong foundation on algorithmic & daya structure is a must

[@danielmateofitness7618]

Instant anxiety

[@Twe4ke]

@@eh7931 I fucking hate math of literally any kind and for some ungodly reason, I sat here and watched the entirety of this video. What in the actual fuck is wrong with me?

[@SG-ek2zw]

@@Twe4ke you want to feel smart because you watched the whole thing.

[@MrAntarpreets]

I loved his first solution, for the first part I just wanted to create a set (O) for original points and then iterate over points to find a pair {x,y}, {x1,y1} with x > x1 and y > y1 such that O also contains the points {x, y1} and {y,x1}. Return the count of such pairs found as the answer. For the second, I am not familiar with vectors like he described but I realized that 1. the diagonals intersect at their midpoints and 2. the diagonals are equal in length. So iterate over all points and complete a map. At the end just iterate over the entries in the map and calculate answer += count_slopes*(count_slopes - 1) / 2 for each map entry.

[@gyan1010]

I'm not sure why you store the slope, as I don't think you need it. My solution for that was to do the same thing at first, but only map the midpoint and length of each line segment, and just keep a count of each unique entry. Then since any 2 line segments with matching midpoint and length can form a rectangle, you need to take each different result and get the combination of n choose 2, where n is how many of that mapped pair were counted. So if 4 lines (8 coordinates) have matching midpoint and length, then you could actually make 6 rectangles because 4 choose 2 is 6. Anyway, you can add the combinations to get the result.

[@MrAntarpreets]

​@@gyan1010 The slope is just to avoid duplicates (and save some memory from keeping 4 coordinates) since a line segment can be uniquely specified by mid point, length and slope. If you don't care for those, you'll at least have to restrict the selection of point pairs in a way to avoid same set twice.

[@gowthamchandanraju]

Well, i shld say i didn't get shit out of it but for the first question if they made it lol bit complex we can actually get it in a easier ways. Let's say there r n points then no.of lines formed will be nC2 so considering only slopes of all the lines, if 2 slopes are equal then inserting 1 amongst 2 into an array and then multiplying those 1 to any other and if the product is -1 then the count is increased to +1 That is all it is they made it much more complex to look.

[@gyan1010]

@@MrAntarpreets you wont need to avoid duplicates as long as you only store and compare diagonals once. Two different matching diagonals means a different rectangle, and by taking the combination formula on the matching length/midpoint diagonals, and choose 2, you get (n! / ( (n-2)! * 2! )) = number of unique sets of 2. Do that for each match and add the results and should be no duplicates.

[@MrAntarpreets]

@@gyan1010 How do you store a diagonal uniquely ? I am using slope to do this. Also nC2 = n*(n-1)/2 , which is what I used.

[@namanjain8458]

Errichto is like a god to students in high school. I have seen many people having his posters in their dorm rooms.

[@smashed5826]

I share the same feelings when you understand others and agree with others' solutions, how cheerful!

[@kareha0]

const counter = require('count-rectangles'); echo counter(point-tuples); // done

[@michaelphoscar7509]

I feel like I'm being spat at constantly

[@is1hair]

evil

[@astwas]

Or like that shame scene from Game of Thrones, which is far easier to handle than having to attempt this in an interview..

[@AnkitJosh]

Underrated

[@ISmellMopWho]

I’m planning on studying computer science and this shit scares me.

[@RM-gm7lu]

Don't be. The journey of a thousand miles starts with a step. Sometimes it's good to be confused but keep at it.

[@jaytrivedi8422]

Forget about coding at first. just read the problem statement and think about how you would try to solve it in real life. Coding is just a language representation of how a computer will execute instructions your instructions.. remember you are in control..always...

[@Cobrax101]

I have 2 degrees, this shit still scares me. Interviews are like tests, they're scary and they suck.

[@Ryuudo123]

under presthure

[@trousersnake81]

There are many ways to interview and many ways to solve this problem. Just break it down into small steps. After you take a couple courses, the problem itself won't be the issue anymore as you will see many ways to solve it. It will then become about doing it in the most efficient way, both in terms of the time it takes you to write, and how long it takes to run, as well as conducting yourself appropriately for an interview - as with any other job.

[@LaserArmor]

Could you do more (fake) coding interview videos with Errichto? This was super-interesting to watch!

[@therockfan10001]

I love that second question. My solution would have just been to use distance formula to compare the distance of opposite corners of four points. A rectangle must have all 90 angles and how we can confirm that is by comparing the hypotenuse of both triangles that can be made from within the rectangle. Then verify using trig functions and knowing that there is a 30/60/90 triangle within every rectangle or a 90/45/45 in every square. If the angles result in the proper output from being put inside cos, we can verify that the mirror triangle would be congruent and therefore make a rectangle.

clement is like mind == blown

[@clem]

Those first ~15 minutes of the interview were just 🤯

[@derda3209]

@@clem if you don't mean he is true, but he blew your mind, mind.isBlown = true would be a better fitting analogy

[@onokr705]

der da wow bro, you're a genius

[@JackBond1234]

@@derda3209 Since it's a statement rather than an assignment or a comparison, it'd probably be more like: print mind.isBlown; // true

[@derda3209]

@@JackBond1234 Sure, if it's a statement. I interpreted his comment so that the video was assigning his isBlown boolean in mind to true

[@tekk7989]

Why didn't Google recruit Errichto after he won second place at the Google coding competition? Or maybe they did, and he wasn't interested?

[@jaysondemarco]

Tekk he was not interested he prefers competitive programming and gaming you can find this out by watching out his interview on jomatech channel. Interview with a competitive programmer

[@kamalhm-dev]

The default was hard enough, the bar raiser was insane!

[@TheJFKWahoo]

as a solution to the second part. I would: pick a point, make it my center of coordinates rotate all the points 45 degrees around the center run the algorithm that solved the first half. Rotating can be done by converting to polar coordinates and then adding a theta of pi/2 and then converting back to cartesian

[@mykolapokhylets3105]

There is very simple and elegant N^2 solution for the follow-up question. Structurally, it is very similar to the very first solution (axis-aligned), but uses a different key for dictionary lookup. Tetragon is a rectangle iff its diagonals intersect at the center, but also have the same length. So if we group pairs of points by (center, length), then any two pairs would form a rectangle. answer = 0 counts = {} for A in points: for B in points: if B