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

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?

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

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.

@@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.

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

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

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

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

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

Bharani Dharan 😂😂😂

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

Dan Shao fu

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

Haha 😁😁😁😁

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

A lot of games are filled with it

Dude get your fucking shit togetther

@UCvxbsNm-80mD0BggH-95rew go fuck yourself

@@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.

Kalle sir omg! U r the python goat

OMG Kalle Hallden I love your videos!

IMO: Get Kalle on here Clem :)

Learn c++ everything will make sense

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

@@coffeeenthusiast8774 No need.

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.

@@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

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.

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

@@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).

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

@@jamespond3668 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.

Lol

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

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

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

@@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

Thank god i am not the only one.. phewww

+1

😂😂

100% accurate

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.

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.

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.

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?

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

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

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

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

@@saedyousef gennady korotkevich - Let me introduce myself.

What have you been doing since 40 years then

@@criptik5208 not coding

@@criptik5208 probably counting

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

@@robinder_ day made thank u

Came here to say this.

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

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

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

@@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

😂 Same here!

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

How do you do it ?

Lol

@@Player-ix7rx ctrl + scroll

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

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

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.

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.

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

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

@@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/

@@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

What type of ?

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

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.

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

@@charlesbaldo It means a lot to hear this right now. Thank you.

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

Ex Hoffie I’m not even good at math

😂

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

Adestrix96 big brain answer

@@hoffie7456 thx ^^"

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

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)

@@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

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)

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 :)

@@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.

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

The only way to do it 😛

@@clem BTW how are you managing your FTJ with UKposts 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.....

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

@@clem oh, nice to hear that.🙂

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

@@arkros1 You sound stupid (no offense).

Arkros wow so brash of you to say that

@@arkros1 bruuh -__-

@@arkros1 what's wrong with the formula?

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.

Hahaha, it should be a little bit of both 😛

gg

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

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.

How many u solved??

Yeah this was a pretty weird mistake

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

same here!

Damn

Hahaha

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

@@Slimehardtshawty no: those two are friends and the are making an intertaining video.

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.

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

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

He is; really impressive problem solver!

I should've subscribed to him long ago. That's pretty cool!😁

Do I need to be as good as Errichto to get a job in software engineering?. I am not referring to google but any medium sized companies. I am sure I cannot even come near to Errichto or clement but I know some c++ and algorithm stuff and I just wish a software engineering job in medium sized companies

@@VC-kj9yx There are plenty of companies that will hire you if you have decent programming skills. No worries, you got this 😉👌

Wow that's elegant

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.

Yeah I did thee same thing

Welcome

I feel ya bro

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?

😂😂

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

@@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.

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.

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.

@@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.

it's not just 90° we can have different slope rectangles too. plus you would rotate by 45° for counting those 90° rectangles

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.

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)

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

Ja w sumie po twarzy poznałem że Polak, nie wiem jakim chujem

Wgat does that mean

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

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

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.

​@@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.

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.

@@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.

@@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.

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

Cancelling my Google interview opportunity right now.