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: ua-cam.com/video/Y8VeyLG3NhY/v-deo.html
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.
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
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
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
@@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.
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!
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 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
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 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
@@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.
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.
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?
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
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²).
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
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.
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.
@@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/
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!
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.
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.
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.
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)
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.
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.
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! :)
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 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.
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.
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!
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
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
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.
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.
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
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.
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.
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.
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.
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!
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.
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.
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.
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...
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.
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.
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).
@@clem BTW how are you managing your FTJ with UA-cam 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.....
Still to figure out for me, was this interview motivating or demotivating ;)... He nailed it completely. Loved to see this entire interview.. very inspirational..
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.
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?
@@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.
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.
@@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.
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
@@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?
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
At 31:40 Clement asked Errichto to avoid solutions that use clever math properties. But you will never be able to solve this problem in O(N^2) time without using clever math properties. The reason is that the count of rectangles itself is more like O(N^3) and not O(N^2). If your solution amounts to iterating over rectangles, you're already too slow. You need something more clever.
Was he really struggling with “how do I know from diagonals wheter it’s a rect or a rombus”?? Just check if diagonals have equal length... Iterate through points in your plane From every point Project pair to any other point Calculate middle coord Create perpendicular vector with same middel point Check if new vectors endpoints are both in hashmap
satyam pandey this is, in a google interview you’ll first take time to define the problem, this guy went straight in and proved he knew an easy answer on the first problem quickly. But that’s not the way to go about it in an interview, it’s for more important to prove that you fully understand and are able to break down the problem itself. First this you’d do is start writing down what makes a rectangle a rectangle, what makes the coordinates work. After that you’d be able to explain to the interviewer what you will try to do in code and then code it out. The way he lost the interviewer in what he was doing was his own fault. I know this is a mock interview with a speed coder, but for anyone looking up “google onterview” these are some free tips 😉
baseballboy you can indeed do exactly the same as I dit but starting with two neighbour corners instead of opposites, thing is that the rectangle can go much further so there is no definite way to calculate this for a hash map and thus your big O would be considerably larger. Thank you for coming to my TED talk
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.
@@AntonioLicon : I did manual recomputation on paper, and found 44 rectangles. Here is an illustration of the 9+6+6+3+3+2+2+1+4+2+2+4 = 44 rectangles I found: pasteboard.co/IRWnxBc.jpg
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.
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.
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
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.
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.
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
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....
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)
I'm just commenting my approach here, and am ready to criticism ok here we go: Given a grid of points we can easily count the number of any type of rectangles formed using combinations, for which we get a straightforward formula that can be solved in constant time given the number of vertices in the grid. Given that the grid at tight angles. Now to get a grid we can loop over every pair of points in N² time and find the slope between points and store pairs with the same slope in a map. Then we just count the number of pairs of points with same slope and run it through our formula and done.
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!!
I am sad that he was discouraged from the A-C option in the second half. That definitely seems like a super simple way to get this down to N^2. Even if we ignore the midpoint bit, you can take any two points, treat them as A and C. Imagine a line between them. Then imagine vectors out from each point, at +45 and -45 angles to the line between a-c. Where the lines from A intersect the lines with C, there should be points to a square. Check those in a hash set and bam, n^2
@@thomas2446 Not so; I wrote square incorrectly, but it's the points to a rectangle. No, the part I neglected is that it's not trivial to check if/where two arbitrary lines intersect - or at least, I don't know how off the top of my head The basic idea is that it takes only two points to define a rectangle, and so for any two given points you can determine what two other corners would be required to complete a rectangle
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
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: ua-cam.com/video/Y8VeyLG3NhY/v-deo.html
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.
Spoiler: Google didn't hire me.
Apparently, Clement is an ex-Google engineer and this wasn't a real interview :(
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.
I just learnt to display "Hello world" in python. Now this video is recommended to me.
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.
hahaha
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
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
"I'm quite good at computational geometry" - well there is something I didn't know existed.
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.
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!
Kalle sir omg! U r the python goat
OMG Kalle Hallden I love your videos!
IMO: Get Kalle on here Clem :)
writing code in google docs brings cancer to my eyes
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
My self-esteem doesn’t need this
Thank god i am not the only one.. phewww
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
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
5:06 The only part I can do...
😂 Same here!
Had a good laugh ty :)))))))
How do you do it
?
Lol
@@Player-ix7rx ctrl + scroll
Didn't follow much of the problem, but the composure of this guy is something to learn from. I'm super impressed :)
+1
He's an LGM on Codeforces, have to have nerves of steel for that
"I'm quite good in computational geometry"... you sure you want to ask me such a stupid question?
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.
@@ItsAllEnzynes 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
@@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.
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.
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?
This ended up being Errichto giving tutorial on algorithms to Clement
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.
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²).
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
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.
This gives me anxiety even though I have a job now.
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.
@@charles-y2z6c I'd be fascinated to hear more about a career like that. What have you been doing all your life?
@@charles-y2z6c It means a lot to hear this right now. Thank you.
When the Google interviewer is completely overwhelmed by the interviewee...
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
Clement: never interviewing a Competitive Programmer again!!
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!
that moment when your interviewee finds a more elegant solution than your best solution in the first 15 min of the interview
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.
I don’t know a single lick of coding, how did I get here
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 ^^"
What a guy! The way he approaches the questions is just amazing.
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.
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
no one
literally no one
errichto: ” Are you sure this problem is hard enough “ ? 😂😂
😂😂
The way he was solving the problem it felt like a poet reading his poem. Thanks Clement for an awesome episode.
I really love the attitude of errichto even with so special talent he dont have pride at all love you errichto
2:10 "i can handle upto 10 dimensions". - Errichto
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?
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.
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)
i think, when you connect two dots, there will be a line
gg
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.
The slopes are only opposites if the sides of the rectangle are parallel to the x and y axis.
Errichto is a super cool guy, he is totally chill and always ready to help you. He is awesome.
2:34 How many rectangles are formed on the plane... Why are we still here? Just to suffer
😂😂
"I'm quite good in computational geometry".. when clement reminded only 2 mins left ''Take it easy".... Erricho is a gangster!
What do you do for a Living?
Before the interview: I am a software engineer!
After the interview: I am selling weed niga!
lol
😂😂😂😂😂😂
"I can handle two dimensions"
IS FOUR DIMENSIONAL BEING
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 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! :)
They should test you on your awesomeness complexity in interviews! Who cares about time and space complexity when you've got awesomeness complexity?
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.
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.
Amazing. It is like watching professional athletes. I know they are doing something that I can't and I respect their skills.
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!
The only time I felt, even slightly smart watching this video, is when I said slope before Errichto did.
I feel ya bro
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
Yeah this was a pretty weird mistake
The UA-cam algorithm letting me know I haven’t got a clue what I’m looking at by showing me an advert for glasses midway through.
Clement gets surprised every min when errichto writes code😍😍
Why am I nervous?! I'm not even the one being interviewed!
so true dude! :) we all feel the same here
Cancelling my Google interview opportunity right now.
His solution to part 1 basically solves part 2, u just need to have the right key (angle + 2 projections).
It’s stuff like this that depresses me because I’d probably fail the first question in an interview.
Try to solve one algorithm problem every day. In a couple of month you'll be amazed how far you can go.
Git gud
@@IgorAntarov nice advice ty
Mike G This isn’t Dark Souls dude....
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
I don't even know programming but I can understand that this guy knows his stuff
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.
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.
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
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.
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.
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
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.
You get some serious numeric trouble with low or high slope pairs this way though..
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!
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.
If I ever get asked this question in any interview, I would just start searching for other jobs.
😂
36:22 You know shits about to get real when
Clément sips some coffee.
Got a "work as a taxi driver" add before this video.
That's the best burn I've received this year :D
Damn
Hahaha
I have a dream, and I don't care how challenging the field is, this is my inspiration
Wgat does that mean
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.
So is it normal for interviewers to help the interviewee along?
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.
Come on Clement ! I was studying algorithms and I had to stop because I can't resist watching this video !
My mission is to distract algorithm studiers with mock coding interviews!
same here!
I’m planning on studying computer science and this shit scares me.
Don't be. The journey of a thousand miles starts with a step. Sometimes it's good to be confused but keep at it.
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...
I have 2 degrees, this shit still scares me. Interviews are like tests, they're scary and they suck.
under presthure
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.
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.
True. They're are also perpendicular to each other.
@@AashayS Actually no. Only if it was a square.
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.
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).
const counter = require('count-rectangles');
echo counter(point-tuples);
// done
Nice to have winner of Codejam on channel.
Liking before watching it Clement!
🙂
The only way to do it 😛
@@clem
BTW how are you managing your FTJ with UA-cam 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.🙂
Yes! This guy is awesome! I first saw him in an interview with Joma. Im glad you got him in. What an awesome video 😁👌
I feel like I'm being spat at constantly
evil
Or like that shame scene from Game of Thrones, which is far easier to handle than having to attempt this in an interview..
Underrated
60 seconds into interview I pull my internet cable out
Still to figure out for me, was this interview motivating or demotivating ;)... He nailed it completely. Loved to see this entire interview.. very inspirational..
Hahaha, it should be a little bit of both 😛
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.
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?
Fun fact: you can actually solve the problem pretty easily with idea #2.
just need to verify halves of the intersecting diagonals are equal length :)
@@daliborduric992 Yep, I thought of checking the length pretty immediately and it is O(N) and rather simple.
@@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.
@@julianelischer edit: it's actually n(n-1)/2 + n which simplifies to n^2 although it will never reach n^2
Dalibor Duric that is way too much work for me. It has two loops inside each other so I go for n^2. 😊
things like these make me reconsider trying to major in computer science lmao
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.
@@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.
Good, if you're scared of difficulty then don't major in something difficult.
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
I don’t know why I watched this video, I’m a beginner lol
I'm not even a beginner. I just stumbled upon this video. I don't...understand.
of course you should watch it.as begginer strong foundation on algorithmic & daya structure is a must
Instant anxiety
@@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?
@@Twe4ke you want to feel smart because you watched the whole thing.
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?
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
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.
How many u solved??
@Errichto This is a legendary solution. It gets as beautiful as it can get.
Welcome
At 31:40 Clement asked Errichto to avoid solutions that use clever math properties. But you will never be able to solve this problem in O(N^2) time without using clever math properties. The reason is that the count of rectangles itself is more like O(N^3) and not O(N^2). If your solution amounts to iterating over rectangles, you're already too slow. You need something more clever.
Was he really struggling with “how do I know from diagonals wheter it’s a rect or a rombus”??
Just check if diagonals have equal length...
Iterate through points in your plane
From every point
Project pair to any other point
Calculate middle coord
Create perpendicular vector with same middel point
Check if new vectors endpoints are both in hashmap
To take out doubles, instead of raycasting in all directions, only take pairs in one quadrant
This happens in programming, you sometimes forget the small things
satyam pandey this is, in a google interview you’ll first take time to define the problem, this guy went straight in and proved he knew an easy answer on the first problem quickly. But that’s not the way to go about it in an interview, it’s for more important to prove that you fully understand and are able to break down the problem itself.
First this you’d do is start writing down what makes a rectangle a rectangle, what makes the coordinates work. After that you’d be able to explain to the interviewer what you will try to do in code and then code it out.
The way he lost the interviewer in what he was doing was his own fault.
I know this is a mock interview with a speed coder, but for anyone looking up “google onterview” these are some free tips 😉
Ah, I somehow forgot this too. Instead I considered calculating the two slopes of the sides and seeing if the negative inverses match.
baseballboy you can indeed do exactly the same as I dit but starting with two neighbour corners instead of opposites, thing is that the rectangle can go much further so there is no definite way to calculate this for a hash map and thus your big O would be considerably larger.
Thank you for coming to my TED talk
I thought coding is all about "HELLO WORLD!"
@@tanishcqmehta9984 You might think I'm not ambitious but let me stick to moving company.
No you didn't, you just wanted some likes on a stupid comment
@@nielsliljedahlchristensen4924 Ok Boomer
@@TopAhmed1 Says boomer and has Messi as their picture. I'm guessing you're offended because you also never had an original thought yourself
@@TopAhmed1 ok millennial
why didn't he start off with 'Hello World !!'?
But in assembler
He is still learning that
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.
"I don't know if you know, but this is like a baby problem for me, are you sure you want me to go through the motions"? haha, love that guy
For a rectangle, the diagonals are equal and bisecting each other.
Yep, I had the same idea and drafted a solution based on that: scastie.scala-lang.org/clQ2xWZ2TzOT5F9pxsriuQ
@@IlariVallivaara Your code says a 4x4 grid has 44 rectangles. I'm only getting 42 (on paper and in code)
@@AntonioLicon : Ok, let met check what's wrong.
@@AntonioLicon : I did manual recomputation on paper, and found 44 rectangles. Here is an illustration of the 9+6+6+3+3+2+2+1+4+2+2+4 = 44 rectangles I found:
pasteboard.co/IRWnxBc.jpg
@@AntonioLicon : What I think you are missing those two non-straight-or-45-degree rectangles.
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.
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.
When a lengend enters the room you know because they don't need to think about any problem "THEY ARE GOOD IN COMPUTATIONAL GEOMETRY'.
gennady korotkevich - Let me introduce myself.
Clement please do interviews with Competitive Programmers more.
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
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.
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.
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
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....
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)
For the squares one just do (n+n-1+n-2...)(m+m-1+m-2...), where n and m are the side lengths of the rectangle
I'm just commenting my approach here, and am ready to criticism ok here we go:
Given a grid of points we can easily count the number of any type of rectangles formed using combinations, for which we get a straightforward formula that can be solved in constant time given the number of vertices in the grid. Given that the grid at tight angles. Now to get a grid we can loop over every pair of points in N² time and find the slope between points and store pairs with the same slope in a map. Then we just count the number of pairs of points with same slope and run it through our formula and done.
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!!
Errichto’s “professional problem solver” remark is really underrated
This man has serious skills! Love the idea Clément, keep up the great work 👍
I am sad that he was discouraged from the A-C option in the second half. That definitely seems like a super simple way to get this down to N^2. Even if we ignore the midpoint bit, you can take any two points, treat them as A and C. Imagine a line between them. Then imagine vectors out from each point, at +45 and -45 angles to the line between a-c. Where the lines from A intersect the lines with C, there should be points to a square. Check those in a hash set and bam, n^2
this would only find squares not all rectangles like the question is asking.
@@thomas2446 Not so; I wrote square incorrectly, but it's the points to a rectangle.
No, the part I neglected is that it's not trivial to check if/where two arbitrary lines intersect - or at least, I don't know how off the top of my head
The basic idea is that it takes only two points to define a rectangle, and so for any two given points you can determine what two other corners would be required to complete a rectangle
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