It would make much more sense not to return False if they don't overlap, but to return a 0 area. Not only does this make it a consistent interface (always return a number, as opposed to a number or a boolean), but it simplifies a lot of your code.
@@mikiii880 If the area is 0 then they don't overlap. Sides touching means the actual rectangles don't overlap. No need to have a special case to check if they overlap in that case.
it is easy to throw an exception and you need a little math skill to translate a 0 answer to "not overlap", however, everyone would understand that False means its not happening.
You guys all miss the point of this video. Obviously, the solution is easy and could be written in 2 mins, but THIS IS AN INTERVIEW. You need to show your ability to think about the problem, to write understandable code, to consider possible scenarios and most importantly to clearly express your thought process. You can't just sit down and spit out the solution without saying a word. The point of this video is not the overlapping rectangles problem but Irfan's communication with the interviewing person.
Your articulation in the video is horrible. You clearly don't understand what you're actually doing, and you're just repeating the geeksforgeeks.org example.
Yeah this guys is an idiot. You can tell he got that response from somewhere and had to say it to a group of people. Cause no one mentioned what he is complaining about
“Can I draw it out for a visual?” Immediately plots the first point in the wrong location. Points for catching it, though, because being out in the spot in an interview session usually gives you blinders where you can’t even catch the most obvious clues. Great video
This works if Rect1 and Rect2 are neatly isolated to any one coordinate fragment. But it falls apart if they are over top of the Origin (0,0). You need to adjust the logic in distance() to account for that. Can't just use min(R1txy, R2txy) - max(R1bxy, R2bxy).
Assuming that they are using two coordinates for the rectangle that means no twisted rectangles. Assuming all integers such as the case. Then list all points in rectangle 1 => as tuple. e.g. List List all points of rectangle 2 => same way as for list 1 The area is the number of points in the intersection of the two lists.
Maybe I missed it but isn't it a big assumption to consider rectangles edges will be parallel to the x, y-axis? or rather two rectangles will be parallel.
It's addressed early in the video that the rectangles will be composed of lines oriented parallel to the xy axis. You're right in that it is a big assumption, but if you think about it, it's implicit in the input format. "Sloped rectangles" embedded in a plane need to describe at least 3 vertices, so the two edges required to form a 90° corner (a vertex) are represented. The corner becomes the local origin, use pythagoras to get the edge lengths, multiply for area. For "non-sloped rectangles" you just need 2 opposing vertices to find the edges required to calculate area. This is because rectangles by definition are composed of 4 congruent interior angles of 90°, and 2 sets of 2 congruent edges. It'd occasionally useful to consider a square as a special case rectangle. If it were a rhombus, all 4 vertices are required to find area. So the question in my opinion to ask is not, "are there sloped rectangles?" but rather "is the input format stable or variable? Will all rectangles be described with two vertices?". From that you should be able to describe the system's capacity for rectangles to the interviewer, demonstrating an awareness of how a rule, in this case the geometric identity of a rectangle, is used to omit unnecessary data from a model without losing any information about the object the model describes.
Real world problems are much much harder than this (think multiple n-dimensional polyhedrons, instead of just 2 rectangles). If you can't solve this under pressure, you can't solve harder ones in your empty room either.
I solved it by sorting the 4 x coordinates and the 4 y coordinates, the overlapping area is the product of the difference between the 2 middle xs and the 2 middle ys, and it's invariant to permuting the two rectangles.
@grinflur you can check that, by seeing if the first two x coordinates are from different rectangles. If they are from the same, you can return by saying that they don't overlap
The rectangles used in this problem are formed by 2 points, to represent a specific rotated rectangle you'd need at least coordinate 3 points, so I think it's safe to assume that this problem doesn't encompass that :) EDIT: also listen at like 3:45, no rotated rectangles
It's actually O(1), since the number of coords being sorted is constant. That said, you've got to check if there's no overlap before using this method.
Hello Irfan , i just found your videos and it's so good and especially the way you communicate and spill out the idea that you are thinking infront of the interviewer because many of them can solve a particular problem but how to approach as well as in the meantime communicate with the interviewer is something the people is lacking behind...so thank you for you effort ...keep it up👍😄
This is a 2-minute solution. All you need are the vertices of the intersecting rectangle. Both the vertices are already known (3,2) and (5,5). So the area is given by: 1/2*(3-5)*(2-5) = 3. Now in order to generalize the area of the intersecting rectangle: A = 1/2*(x2-x1')*(y2-y1') where vertices are labeled R1: ((x1,y1), (x1',y1')) and R2: ((x2,y2), (x2',y2'))
Oh yeah! Don't know why I put 1/2 there, was I probably thinking of triangles and vertices? Thanks for pointing that out. On your other point, please give me an example where my formula won't hold. It holds even when there's no intersection and when the rectangles are located on other quadrants. But please show me! Maybe you are right, I am open to possibilities that there might be cases where it may not hold.
What if they overlap at corners (diagonally)? you find the intersection points by equalizing linear functions of each side of each rectangles. If you have a solution, then you have an intersection. Knowing 2-rectangular intersection points, and the points for rectangle angles, it is easy to get the area. And it works in any situation.
The sides are parallel to the axes really make the question a lot easier. Otherwise you will have to draw circles with the end points of each rectangle as diameter. If sides are parallel to each other you are left with only a single possibility for other vertices.
the first solution I thought of is like thid: 1-find the coordinates of the possible cells inside each rectangle 2-check the common cells coordinates between the tow rectangle and then the area is just the number of those common cells
my approach would be to use sets. Set for all x cords in r1. Set for all x cords in r2. set of all y cords in r1. Set for all x cords in r2. If the intersect for x r1/r2 doesnt yield values or intersect of y r1/r2 doesnt yield values or its one item, the rectangles dont overlap. if intersect of x and y are 2 or more each, we take the (max - min) for x subset * (max - min) for y subset for the area overlap. note that both of the intersects must yield 2 or more values in order for it to be considered overlap. If intersect yields 1 value, they are perpendicular. If the intersect is empty for either they are not touching at all
What if we translate both rectangle to first quadrant such that most bottom-left point of most bottom-left rectangle lies on origin Then apply your concept to solve problem
Calculate all 4 corners amd check if any of the corners fall in the other rectangle. If any do, depending on the corner take the min/max of each axis then multiply them and it's done. If no corners in the rectangle, return false or - 1 because no overlap.
This is very simple. Take the max of the x coordinate of the given botton left coordinate of both rectangle and take the min of the x coordinate of the top right coordinate. Now we have x coordinates of the overlapping rectangle. Repeat it for getting y coordinates. Now to check overlapping, pick any coord in between these coord and use min and max logic. If no overlap, find the area.
lol I got this problem for an interview with Rakuten except I had to return the area of both rectangles excluding the area of overlap. I got it but Jesus it was not easy at first.
x of one between x-x of other for both xx points of first rectangle similar for y and then area overlap is x1-x2 × y1-y2
5 років тому
At 5 min I saw that was way easier to notice that the rectangles would overlap only if Rect1.UR.x < Rect2.DL.x (UR = up-right, DL = down-left), or some variation of this And the area is just another rectangle which DL point is Rect1.UR and UR point is Rect2.DL. Of course, cleaning off the edge cases such as one containing another, and considering they might be swapped, and, first of all, normalizing the coordinates to cover negative coordinate cases.
This is a problem that could appear in a school exam. And the other problem, the max square of 1s in a binary matrix, is a problem of the first course in university... And I was afraid to fail in this kind of interviews.
Arguments for min and max should be absolute values so that this works in other quadrants. When you say min you mean closest to the axis, and when you say max you mean the furthest from the axis.
Hi Irfan, I just found your videos and I really like what you're doing! For a while I've wanted a UA-cam channel which goes through an actual mock interview. I was wondering if you were thinking of doing a more advanced interview for one of your videos. One of my main goals is to ace a Google interview. I always think that I can improve my interview skills and it would be nice to see a mock interview where everything is done to "Google expectations". I think it would great for learning and something people can aspire to do.
Thank you for the video, it's really helpful for people who want prepare a bit. Just i hope you will nor mind some constructive critics: 1. The requirement to return "false" if they do not overlap IMHO does not apply for cases where they overlap on border. If rectangles share at least one point technically they do overlap, just overlapping area is 0. 2. About naming: width and length are ok. "Bottom" and "top" not precise - i would recommend to be more precise naming and use "bl", "tr" and earlier start use x and y. 3. Naming of function is not optimal: from function with name "overlaps" i expect boolean value, not an area. You should be more precise and name it "overlapingArea" or similar. Technically you solved problem, and solution is ok, but if you passed interview for me it would depend which level position you are seeking - for junior it would be ok, for mid maybe ok, for senior i would have my doubts if to hire candidate with such solution. Semantics maters!
Hi I have three years of experience as software developer, could you please guide how to get job in Big companies like Microsoft,FB Google etc.. how do I start preparation also do I need to have min % in 10th 12th and engineering to get job in these companies?
Hi Irfan , Could please explain the below problem in your next video Nikita has a family tree T consisting of N members number from 1 to N. Each of the edges in the tree represents a directed relationship. Basically if there is an edge from member a to b, it means b was born before a. Now, Nikita knows that these members were born in last M days and only 1 person was born on a single day, She is interested in calculating the number of ways to assign birthdays to each of the N family members. 1
He has missed out on so many aspects of this problem, and still so many people think that it was a nice solution, I don't even think it is the right solution 😂
I never considered myself good enough for FANG, but if this is one of their interview questions and if answering a simple question like this actually is allowed so much time, damn I sold myself short all these years
+Irfan Baqui Hey I think for this question the information given is insufficient. Question : The inputs are 2 points for each rectangle(2 rectangles) bottom left and top right. we need to find the overlapping area. (please correct me if i am missing anything here) let me explain.. consider a single rectangle and the information we have on it is one diagonal's points(bottom left and top right). so what can be possible points for remaining two . They lie on the perimeter of the circle with this diagonal(input) as diameter(since angle formed by diameter on perimeter is 90 deg so is the angle by adjacent sides of rectangle). lets get back to our question.. here we have 2 diagonals for each rectangle. if we construct 2 circles with these 2 diagonals as diameters. lets consider there is a small overlapping region for these 2 circles. Now consider 2 scenarios 1.if both rectangles have their 3rd of the point outside the intersecting arcs. here there wont be any overlapping. see image i.imgur.com/ZCV9xFW.png 2. if both rectangles having their 3rd of the point inside the intersecting arcs. here we can say they easily intersect. see image i.imgur.com/ih167pG.png so with same inputs we are getting contradicting scenarios. so i feel this is insufficient data.. please correct me if there is any mistake in my assumptions or if i am missing anything.
How bout we sort the x and y indexes accordingly (since there are only 4 points it wouldnt take much time), then if the first 2 indexes belong to the same rectangle they dont overlap, and if they dont, just subtract 2nd index from 3rd index and multiply the distances you have found for the x and y sorted arrays.
Basically, you're given two rectangles. The rectangles are denoted by the bottom left and top right coordinates (so they are made up by only horizontal and vertical lines.) Imagine they overlap. Shade that overlapped region. You now have to write a function that gives the area of that shaded region. To do it, first figure out how that could be done by pen and paper, or just figure out the steps that you need. Then try writing the programme. It's not that hard of a programming problem, you just have to get the maths behind it. GOOD LUCK :)
the best thing you can do in interviews is to walk through your reasoning and not just give the answer as someone who just memorized the solution from a cookbook. They want people that can use math and logic to solve problems that may come up, you won't be able to do so if you just repeating something you memorized because real world problems are much more complex. DUDM , Do Understand, Don't Memorize
such a difficult solution for an easy problem ! Dude just intersect all 8 lines to get 4 unique points using equations .. and there u are .. it can be solved in 2 mins !
Ashutosh Patel I havent study it hard, but if the overlaped surface is not a rectangle probably you need more than two points per rectangle to define well them
lol.. the whole point is to get something wrong and eventually finding out the correct answer. The agenda is *mock interview* , not an algorithm for area of overlapping rectangles
var findAreaOfOverlap = function(rect1, rect2){ var maxX = Math.max(rect1[0].x, rect2[0].x); var maxY = Math.max(rect1[0].y, rect2[0].y); var minX = Math.min(rect1[1].x, rect2[1].x); var minY = Math.min(rect1[1].y, rect2[1].y); var area = (minX - maxX) * (minY - maxY); return (area > 0) ? area: false; } findAreaOfOverlap( [{x: 2, y: 1}, {x: 5, y: 5}], [{x: 3, y: 2}, {x:5, y: 7}] ); The only issue I have with this solution is that it only works if you know which points are on the bottom-left and which are on the top-right.
@@chaigtin259 We can specify a non parallel rectangle just by the two corner points. We don't need any rotation angle or anything like that. It would have been a different cas if the input was one point and the rectangle's length and width.
@@chaigtin259 My thoughts, exactly. When she said they can be rotated. Given the input, that's impossible for a couple of reasons: 1) Two points create a line - a the diagonal of a rectangle in this case, the other two points for creating a rectangle are deduced by the assumption, that the rectangle's sides are parallel to the X and Y axes. 2) Given s diagonal, a rectangle can be constructed in infinite ways, the other two corners lie on the circumscribed circle with centre in the middle of the diagonal and radius half the diagonal; it doesn't matter which other line, bisecting the circle, is picked for the other diagonal, the result of those two lines (the diagonal and the arbitrary other line) results in a rectangle. 3) Terms like bottom-left and top-right do not apply, once the rectangle is rotated in degrees other than 90, 180, 270, each corner gets accordingly the bottom, the left, the top and the right positions; bottom-left and top-right apply only in the case when the sides of the rectangle are parallel to the X and Y axes. I've seen interviewers , who invent cases for a problem as they go, without actually completely understanding the problem themselves. They are not required to understand the problem or to know a fully functional solution. In some cases with more advanced problems, they don't even want a complete solution. They usually consider the interviewee's thought process, communication skills, analytical skills, reasoning, and translation from thoughts to code. I personally don't like the human-processor/debugger part, some of them require, but it is what it is - a white board interview. Someone, probably an author in one of the ThoughtWorks anthology books, in his role as an interviewer, seeking for Java developers, had been asking the candidates, who knew Java well, whether they knew Smalltalk as well... He did not explain much about his question and whether he received a satisfying answer in those interviews or not. It's not a question to throw candidates off, although many were thrown off by it. It's more like "I see you are well prepared for the interview, can we just have a chat now?". Java, being a coffee, and small talk usually go well together... It's a meta-question and a joke, but it's not an easy thing to catch, especially if one is stressed out from the interview... Also considering the cultural gap, the interviewees were from India, and he was from the USA. In India the traditional beverage is tea, not coffee. I give him 8 out of 10 for trying to break the form called "an interview" and 0 out of 10 for not taking into consideration the cultural differences. One can not know everything (probably), yet he insists in his writings later on about them not getting his question by mentioning it. His company needed the people, so he hired them. I've talked with many HR representatives from different companies and recruitment agencies, even just listened to some of them (one sided thing) on UA-cam, reading their blogs and interviews in the press. Some of them are really funny people. Some expect from the candidates things that have nothing to do with the job, they are applying for. And those things are bleeding the interviewers' personalities or what they miss in their own job. In the end of the day, they need to hire people and they do. As UA-cam personnel likes to joke - "A team of highly trained monkeys has been dispatched to deal with the situation.". Then Netflix stepped up the game and created an actual "team" of monkeys, who do not deal with situations, but create them. At least that was what the first couple of them were doing. Later on they created even more for fixing and monitoring stuff. :-)
I'm just spitballing here, what if we just vectorised the given coordinates, find the other corners, then take dot product, if not zero we continue, else return false, then calculate the projection coordinates of overlap through equation factorisation? 😛
This is a GCSE question. Literally, find the area of two overlapping rectangles? Got to be kidding? GCSE algebra with an if statement rammed in to make it 'programming'.
It would make much more sense not to return False if they don't overlap, but to return a 0 area. Not only does this make it a consistent interface (always return a number, as opposed to a number or a boolean), but it simplifies a lot of your code.
-1 -> no overlap. 0+ -> actual area
@@mikiii880
If the area is 0 then they don't overlap. Sides touching means the actual rectangles don't overlap.
No need to have a special case to check if they overlap in that case.
Mixed returns are crap
Return value should be if not overlapped return zero otherwise non-zero.
it is easy to throw an exception and you need a little math skill to translate a 0 answer to "not overlap", however, everyone would understand that False means its not happening.
You guys all miss the point of this video. Obviously, the solution is easy and could be written in 2 mins, but THIS IS AN INTERVIEW. You need to show your ability to think about the problem, to write understandable code, to consider possible scenarios and most importantly to clearly express your thought process. You can't just sit down and spit out the solution without saying a word. The point of this video is not the overlapping rectangles problem but Irfan's communication with the interviewing person.
Your articulation in the video is horrible. You clearly don't understand what you're actually doing, and you're just repeating the geeksforgeeks.org example.
Yeah this guys is an idiot. You can tell he got that response from somewhere and had to say it to a group of people. Cause no one mentioned what he is complaining about
“Can I draw it out for a visual?” Immediately plots the first point in the wrong location. Points for catching it, though, because being out in the spot in an interview session usually gives you blinders where you can’t even catch the most obvious clues.
Great video
It actually made it more relatable. You might do stupid mistakes like this due to nervousness.
This works if Rect1 and Rect2 are neatly isolated to any one coordinate fragment. But it falls apart if they are over top of the Origin (0,0). You need to adjust the logic in distance() to account for that. Can't just use min(R1txy, R2txy) - max(R1bxy, R2bxy).
mann its incredible how you boil down the problem to something so elementary
for this question i will use slope to indicate the direction and connect them between the origin of each rectangle
u can find the overlap very easily
Assuming that they are using two coordinates for the rectangle that means no twisted rectangles.
Assuming all integers such as the case.
Then list all points in rectangle 1 => as tuple. e.g. List
List all points of rectangle 2 => same way as for list 1
The area is the number of points in the intersection of the two lists.
Maybe I missed it but isn't it a big assumption to consider rectangles edges will be parallel to the x, y-axis? or rather two rectangles will be parallel.
It's addressed early in the video that the rectangles will be composed of lines oriented parallel to the xy axis.
You're right in that it is a big assumption, but if you think about it, it's implicit in the input format.
"Sloped rectangles" embedded in a plane need to describe at least 3 vertices, so the two edges required to form a 90° corner (a vertex) are represented.
The corner becomes the local origin, use pythagoras to get the edge lengths, multiply for area.
For "non-sloped rectangles" you just need 2 opposing vertices to find the edges required to calculate area.
This is because rectangles by definition are composed of 4 congruent interior angles of 90°, and 2 sets of 2 congruent edges. It'd occasionally useful to consider a square as a special case rectangle.
If it were a rhombus, all 4 vertices are required to find area.
So the question in my opinion to ask is not, "are there sloped rectangles?" but rather "is the input format stable or variable? Will all rectangles be described with two vertices?".
From that you should be able to describe the system's capacity for rectangles to the interviewer, demonstrating an awareness of how a rule, in this case the geometric identity of a rectangle, is used to omit unnecessary data from a model without losing any information about the object the model describes.
get me in an empty room Ill solve it in 2 minutes. With someone watching me .... not a chance
Real world problems are much much harder than this (think multiple n-dimensional polyhedrons, instead of just 2 rectangles). If you can't solve this under pressure, you can't solve harder ones in your empty room either.
the same thing for me, i would love to found a solution for that lol
Agree. i don't like people judging at the very moment i decide the steps. makes anyone nervous.
@@mildtime1995 can solve it in 1mins :)
@@owenyang9543 No way :(
I solved it by sorting the 4 x coordinates and the 4 y coordinates, the overlapping area is the product of the difference between the 2 middle xs and the 2 middle ys, and it's invariant to permuting the two rectangles.
unless rectangles dont overlap)
How about rectangles are rotated ? :D
@grinflur you can check that, by seeing if the first two x coordinates are from different rectangles. If they are from the same, you can return by saying that they don't overlap
The rectangles used in this problem are formed by 2 points, to represent a specific rotated rectangle you'd need at least coordinate 3 points, so I think it's safe to assume that this problem doesn't encompass that :)
EDIT: also listen at like 3:45, no rotated rectangles
It's actually O(1), since the number of coords being sorted is constant. That said, you've got to check if there's no overlap before using this method.
Just would like to point out that the edges of a rectangle don't have to be parallel to the axises. That seems like a much harder problem.
@@charitablecitizen2332 yes, cause we won't know the location of third coordinate. If it ain't parallel, it can be anywhere
Hello Irfan , i just found your videos and it's so good and especially the way you communicate and spill out the idea that you are thinking infront of the interviewer because many of them can solve a particular problem but how to approach as well as in the meantime communicate with the interviewer is something the people is lacking behind...so thank you for you effort ...keep it up👍😄
wait at 3:07 we're returning false in the case rectangles don't overlap? I thought this was finding the area of the rectangles
You’re have a point, it makes more sense to return 0 instead of false if the rectangles don’t overlap.
This is a 2-minute solution. All you need are the vertices of the intersecting rectangle. Both the vertices are already known (3,2) and (5,5). So the area is given by: 1/2*(3-5)*(2-5) = 3. Now in order to generalize the area of the intersecting rectangle:
A = 1/2*(x2-x1')*(y2-y1')
where vertices are labeled
R1: ((x1,y1), (x1',y1')) and
R2: ((x2,y2), (x2',y2'))
Rectangle area is b*h, not 1/2*b*h. Also there is no guarantee that the rectangles are always constructed so that x1
Oh yeah! Don't know why I put 1/2 there, was I probably thinking of triangles and vertices? Thanks for pointing that out. On your other point, please give me an example where my formula won't hold. It holds even when there's no intersection and when the rectangles are located on other quadrants. But please show me! Maybe you are right, I am open to possibilities that there might be cases where it may not hold.
What if they overlap at corners (diagonally)? you find the intersection points by equalizing linear functions of each side of each rectangles. If you have a solution, then you have an intersection. Knowing 2-rectangular intersection points, and the points for rectangle angles, it is easy to get the area. And it works in any situation.
The sides are parallel to the axes really make the question a lot easier. Otherwise you will have to draw circles with the end points of each rectangle as diameter. If sides are parallel to each other you are left with only a single possibility for other vertices.
the first solution I thought of is like thid:
1-find the coordinates of the possible cells inside each rectangle
2-check the common cells coordinates between the tow rectangle and then the area is just the number of those common cells
I like the way you think! When coding it may be a bit slow for larger rectangles.
Do we have a case where one rectangle is parallel to x axis and the other not parallel (both in quadrant 1)?
my approach would be to use sets. Set for all x cords in r1. Set for all x cords in r2. set of all y cords in r1. Set for all x cords in r2. If the intersect for x r1/r2 doesnt yield values or intersect of y r1/r2 doesnt yield values or its one item, the rectangles dont overlap.
if intersect of x and y are 2 or more each, we take the (max - min) for x subset * (max - min) for y subset for the area overlap.
note that both of the intersects must yield 2 or more values in order for it to be considered overlap. If intersect yields 1 value, they are perpendicular. If the intersect is empty for either they are not touching at all
Am I the only one that noticed that the first point is not well marked?.... should start in 2,1 not 1,1!!
hoo I see he noticed also!
I quitted the video at that point
He corrects it and moves on to the solution, you "quitted" too soon
Bugged me so much i quit watching.
@@tylercrummett9091 thats quite pathetic actually. a common mistake.
I'm new to computer science. Should i learn programming languages 1st or data structure and algorithm????
What if we translate both rectangle to first quadrant such that most bottom-left point of most bottom-left rectangle lies on origin
Then apply your concept to solve problem
What if both rectangles span across the quadrants
Calculate all 4 corners amd check if any of the corners fall in the other rectangle. If any do, depending on the corner take the min/max of each axis then multiply them and it's done. If no corners in the rectangle, return false or - 1 because no overlap.
This is very simple. Take the max of the x coordinate of the given botton left coordinate of both rectangle and take the min of the x coordinate of the top right coordinate. Now we have x coordinates of the overlapping rectangle. Repeat it for getting y coordinates. Now to check overlapping, pick any coord in between these coord and use min and max logic. If no overlap, find the area.
I didn't get this can you elaborate this? Please It seems quite easy.
Now to check overlapping, pick any coord in between these coord and use min and max logic. If no overlap, find the area.
This line only.
lol I got this problem for an interview with Rakuten except I had to return the area of both rectangles excluding the area of overlap. I got it but Jesus it was not easy at first.
In what language can a method return either boolean or int?
@1:02... that's not the point (2,1)
keep watching?
What happens if the rectangles are not parallel to the X axis?
Cry loudly
x of one between x-x of other for both xx points of first rectangle similar for y and then area overlap is x1-x2 × y1-y2
At 5 min I saw that was way easier to notice that the rectangles would overlap only if
Rect1.UR.x < Rect2.DL.x (UR = up-right, DL = down-left), or some variation of this
And the area is just another rectangle which DL point is Rect1.UR and UR point is Rect2.DL.
Of course, cleaning off the edge cases such as one containing another, and considering they might be swapped, and, first of all, normalizing the coordinates to cover negative coordinate cases.
What if it is asked to calculate the area of the overlap of more than two rectangles?
Can just apply recursion
How to get the minimum no. of groups of non overlapping rectangles ????? , just give me an idea
This is a problem that could appear in a school exam. And the other problem, the max square of 1s in a binary matrix, is a problem of the first course in university...
And I was afraid to fail in this kind of interviews.
its not about to solve it , its about HOW you solve it
I've got a long road ahead of me /sigh
Arguments for min and max should be absolute values so that this works in other quadrants. When you say min you mean closest to the axis, and when you say max you mean the furthest from the axis.
That wouldn't work if the rectangles were in different quadrants, though.
Pick’s Theorem (classic math polygon problem)
Hi Irfan, I just found your videos and I really like what you're doing! For a while I've wanted a UA-cam channel which goes through an actual mock interview.
I was wondering if you were thinking of doing a more advanced interview for one of your videos. One of my main goals is to ace a Google interview. I always think that I can improve my interview skills and it would be nice to see a mock interview where everything is done to "Google expectations". I think it would great for learning and something people can aspire to do.
really fool?
easy if you are a game programmer ;-)
Liang Barsky and Cohen Suther land Line Clipping algorithms
Thank you for the video, it's really helpful for people who want prepare a bit.
Just i hope you will nor mind some constructive critics:
1. The requirement to return "false" if they do not overlap IMHO does not apply for cases where they overlap on border.
If rectangles share at least one point technically they do overlap, just overlapping area is 0.
2. About naming: width and length are ok. "Bottom" and "top" not precise - i would recommend to be more precise naming and use "bl", "tr" and earlier start use x and y.
3. Naming of function is not optimal: from function with name "overlaps" i expect boolean value, not an area. You should be more precise and name it "overlapingArea" or similar.
Technically you solved problem, and solution is ok, but if you passed interview for me it would depend which level position you are seeking - for junior it would be ok, for mid maybe ok, for senior i would have my doubts if to hire candidate with such solution. Semantics maters!
Not really
Hi I have three years of experience as software developer, could you please guide how to get job in Big companies like Microsoft,FB Google etc.. how do I start preparation also do I need to have min % in 10th 12th and engineering to get job in these companies?
Hi Irfan , Could please explain the below problem in your next video
Nikita has a family tree T consisting of N members number from 1 to N. Each of the edges in the tree represents a directed relationship. Basically if there is an edge from member a to b, it means b was born before a. Now, Nikita knows that these members were born in last M days and only 1 person was born on a single day, She is interested in calculating the number of ways to assign birthdays to each of the N family members.
1
He has missed out on so many aspects of this problem, and still so many people think that it was a nice solution, I don't even think it is the right solution 😂
Saying something like that is easy. Mind telling why?
7:30 is this assuming that the rectangles have the same area?
Idk I’m confused will it be zero if the rectangles are directly on top of each other?
I never considered myself good enough for FANG, but if this is one of their interview questions and if answering a simple question like this actually is allowed so much time, damn I sold myself short all these years
I thought it was only me who considered this to be too easy :)
+Irfan Baqui
Hey I think for this question the information given is insufficient.
Question :
The inputs are 2 points for each rectangle(2 rectangles) bottom left and top right. we need to find the overlapping area. (please correct me if i am missing anything here)
let me explain..
consider a single rectangle and the information we have on it is one diagonal's points(bottom left and top right). so what can be possible points for remaining two . They lie on the perimeter of the circle with this diagonal(input) as diameter(since angle formed by diameter on perimeter is 90 deg so is the angle by adjacent sides of rectangle).
lets get back to our question..
here we have 2 diagonals for each rectangle. if we construct 2 circles with these 2 diagonals as diameters. lets consider there is a small overlapping region for these 2 circles. Now consider 2 scenarios
1.if both rectangles have their 3rd of the point outside the intersecting arcs.
here there wont be any overlapping. see image
i.imgur.com/ZCV9xFW.png
2. if both rectangles having their 3rd of the point inside the intersecting arcs.
here we can say they easily intersect. see image
i.imgur.com/ih167pG.png
so with same inputs we are getting contradicting scenarios. so i feel this is insufficient data..
please correct me if there is any mistake in my assumptions or if i am missing anything.
at 3:40 she says that the rectangles are always parallel to the axis
Very nice Irfan.
Lenth of egde of rectangle can not be negative ..so no need to consider other quadrant s
How bout we sort the x and y indexes accordingly (since there are only 4 points it wouldnt take much time), then if the first 2 indexes belong to the same rectangle they dont overlap, and if they dont, just subtract 2nd index from 3rd index and multiply the distances you have found for the x and y sorted arrays.
What to do for oblique rectangles?
Doesn't it suck to work at Amazon?
I did not understand the question,can some one explain me the question.
Basically, you're given two rectangles. The rectangles are denoted by the bottom left and top right coordinates (so they are made up by only horizontal and vertical lines.) Imagine they overlap. Shade that overlapped region.
You now have to write a function that gives the area of that shaded region.
To do it, first figure out how that could be done by pen and paper, or just figure out the steps that you need.
Then try writing the programme.
It's not that hard of a programming problem, you just have to get the maths behind it. GOOD LUCK :)
3:06 ... Why would you write a function that can return either a bool or int? Wouldn't it make more sense to just return 0?
he is not a teacher at all, he knows for himself.
very clear and natural, well done mate!
What particular job requires you to pass this interview question? I need to know so I can avoid it 😂😂😂
Software engineer or any IT jobs involving coding mostly
@@noorclean2915 not most of them. Heck, not even all the Amazon software engineering jobs ask this kind of stupid question.
Please make a video on System Design problems
Why have you stopped making videos?
Thank you so much, being a fresher , I needed this much elaborated explanation and I got one through this video.
I like his Channel. Don't know why he has stopped making videos. Maybe because of less subscribers ans no earnings
[(Max of the first x's) - (Min of the second x's)] * [(max of the first y's) - (min of the second y's)]
Would generate negative values
RL87 that’s when you take into account that area can never be negative and take the absolute value. That’s what I was thinking
If either width or height (as calculated above) are negative, there is no overlap between the rectangles.
If there are more than two rectangles?
Then, how will the formula hold?
the best thing you can do in interviews is to walk through your reasoning and not just give the answer as someone who just memorized the solution from a cookbook. They want people that can use math and logic to solve problems that may come up, you won't be able to do so if you just repeating something you memorized because real world problems are much more complex. DUDM , Do Understand, Don't Memorize
Better do an integral of the rectangle function with initial and final points as limits
say
can you solve the problems of 25 Horses and 5 Track Puzzle
such a difficult solution for an easy problem ! Dude just intersect all 8 lines to get 4 unique points using equations .. and there u are .. it can be solved in 2 mins !
it does not have to be 4
This was among one of the first exercise questions we were given in an intermediate level college course. Too easy to be an Amazon interview question.
Great channel !!! Keep on posting!!!
Can you do the ‘Trap the Trouser Snake’ interview question. Its a modification of the snake game.
what if the overlapped area is not a rectangle?
how? except when they don't overlap at all. if given that sides are always parallel to x & y respectively.
Ashutosh Patel I havent study it hard, but if the overlaped surface is not a rectangle probably you need more than two points per rectangle to define well them
the overlapped area will never be 'not a rectangle'.. it will always be a rectangle.. reason as given by Ankit Yadav..
That's not possible. If one of the two figures are not rectangle, then it's false, otherwise the area under two rectangles is always rectangle.
U still call it a rectangle...because a rectangle with all equal sides is called a square :)
Come on.. this is asked in amazon? I'm confused
is this question for amazon guard .. because its piece of cake for programmers thr
intersection over union? how would that work! nice work tho
Awesome break down!
Very clear...
What i remember the Most is the Nike ads
Class 9 , did it within 2 minutes by clock
hii i loved your series...Please upload more videos
I am looking forward for more videos like this
lol doing my masters in comp sci still I don't know hot to solve it
Where are you doing your masters again? :P
Lmao
Madara Uchiha yikes, this is pretty simple.
Better to have a rehearsal before doing the actual video. that saves a lot of time for viewers.
you completely missed the point
lol.. the whole point is to get something wrong and eventually finding out the correct answer. The agenda is *mock interview* , not an algorithm for area of overlapping rectangles
Keep those videos coming
This solution wont be possible if the rectangles not parallel to the coordinates(x,y).
Whoever that lady is, she is from India :P
And she has awesome voice..
I think both of them are from South Asia..
thank you
a lot of these questions are basic ML. sliding windows, knn... etc
17teacmrocks basic ml?
lol this is a funny comment !!
I simply used a deep neural network to solve. Took a few weeks to train though.
Thanks Irfan.
Jesus jobs nowadays with such a tough interview and your job is not even secure
too easy for an Amazon interview. Maybe for interns or something.
not really
var findAreaOfOverlap = function(rect1, rect2){
var maxX = Math.max(rect1[0].x, rect2[0].x);
var maxY = Math.max(rect1[0].y, rect2[0].y);
var minX = Math.min(rect1[1].x, rect2[1].x);
var minY = Math.min(rect1[1].y, rect2[1].y);
var area = (minX - maxX) * (minY - maxY);
return (area > 0) ? area: false;
}
findAreaOfOverlap( [{x: 2, y: 1}, {x: 5, y: 5}], [{x: 3, y: 2}, {x:5, y: 7}] );
The only issue I have with this solution is that it only works if you know which points are on the bottom-left and which are on the top-right.
You should get a Jamboard to do your whiteboarding. I can get you a discount on one. ;)
Only if it's 100% off ;)
That’s a 5th grade math... not sure why they solving it like it’s a rocket 🚀 science
AWESOME
And...I am still thinking how come a rectangle has only two coordinates. :D
I'm you only need 2
4:02 should've been the first question lol
@@chaigtin259 We can specify a non parallel rectangle just by the two corner points. We don't need any rotation angle or anything like that. It would have been a different cas if the input was one point and the rectangle's length and width.
@@chaigtin259 My thoughts, exactly. When she said they can be rotated. Given the input, that's impossible for a couple of reasons: 1) Two points create a line - a the diagonal of a rectangle in this case, the other two points for creating a rectangle are deduced by the assumption, that the rectangle's sides are parallel to the X and Y axes. 2) Given s diagonal, a rectangle can be constructed in infinite ways, the other two corners lie on the circumscribed circle with centre in the middle of the diagonal and radius half the diagonal; it doesn't matter which other line, bisecting the circle, is picked for the other diagonal, the result of those two lines (the diagonal and the arbitrary other line) results in a rectangle. 3) Terms like bottom-left and top-right do not apply, once the rectangle is rotated in degrees other than 90, 180, 270, each corner gets accordingly the bottom, the left, the top and the right positions; bottom-left and top-right apply only in the case when the sides of the rectangle are parallel to the X and Y axes.
I've seen interviewers , who invent cases for a problem as they go, without actually completely understanding the problem themselves. They are not required to understand the problem or to know a fully functional solution. In some cases with more advanced problems, they don't even want a complete solution. They usually consider the interviewee's thought process, communication skills, analytical skills, reasoning, and translation from thoughts to code. I personally don't like the human-processor/debugger part, some of them require, but it is what it is - a white board interview.
Someone, probably an author in one of the ThoughtWorks anthology books, in his role as an interviewer, seeking for Java developers, had been asking the candidates, who knew Java well, whether they knew Smalltalk as well... He did not explain much about his question and whether he received a satisfying answer in those interviews or not. It's not a question to throw candidates off, although many were thrown off by it. It's more like "I see you are well prepared for the interview, can we just have a chat now?". Java, being a coffee, and small talk usually go well together... It's a meta-question and a joke, but it's not an easy thing to catch, especially if one is stressed out from the interview... Also considering the cultural gap, the interviewees were from India, and he was from the USA. In India the traditional beverage is tea, not coffee. I give him 8 out of 10 for trying to break the form called "an interview" and 0 out of 10 for not taking into consideration the cultural differences. One can not know everything (probably), yet he insists in his writings later on about them not getting his question by mentioning it. His company needed the people, so he hired them.
I've talked with many HR representatives from different companies and recruitment agencies, even just listened to some of them (one sided thing) on UA-cam, reading their blogs and interviews in the press. Some of them are really funny people. Some expect from the candidates things that have nothing to do with the job, they are applying for. And those things are bleeding the interviewers' personalities or what they miss in their own job. In the end of the day, they need to hire people and they do.
As UA-cam personnel likes to joke - "A team of highly trained monkeys has been dispatched to deal with the situation.". Then Netflix stepped up the game and created an actual "team" of monkeys, who do not deal with situations, but create them. At least that was what the first couple of them were doing. Later on they created even more for fixing and monitoring stuff. :-)
Great
This is amazing..
I'm just spitballing here, what if we just vectorised the given coordinates, find the other corners, then take dot product, if not zero we continue, else return false, then calculate the projection coordinates of overlap through equation factorisation? 😛
Did you pass on this interview? :)
That's a virtual interview
The question said you're given overlapping rectangles. And then the interviewer says it's possible they don't overlap. Bad attention to details.
I like it but it’s terribly rough to watch.
Same as watching 99% of interviewees. Being able to solve generic problems like this is only the baseline of the hiring process..
hey sir i wanna talk to Safiya Pathan i've seen that she's working at apple and i need a bit help in refferal please
This is a GCSE question. Literally, find the area of two overlapping rectangles? Got to be kidding? GCSE algebra with an if statement rammed in to make it 'programming'.