Bloomberg LP Interview Question Software Engineer / Developers
Draw a line connecting the 2 centers. See at what pts they intersect the rectangle. Take a look at the order in which make the intersection.
Please refer Programming interviews exposed book. It has a very good explaination on this.
I m sure rectangles positions or location(co-ordinates) must be given.
then it's a co-ordinate geometry problem where u have to figure out whether particular point lie over or below nd similarly left or right. based on that we can tel rectangle has got area common with other rectangle or not.
Find the line equation for every edge in the two rectangles. (y = mx+c)
Then see if any two lines (one from each rectangle) intersect (http://ozviz.wasp.uwa.edu.au/~pbourke/geometry/lineline2d/)
Let me borrow this idea and make it work.
Assuming the coordinates of four vertexes of each rectangular are given.
1) calculate the four line equations for one rectangular.
2) check each vertex of the other one to see if it is inside the first rectangular.
notes: 2) can be done as follows: say line equations are denoted as l1,l2,l3,l4, where l1 and l3 are parallel, similarly for l2 and l4.
To see one point (x0,y0) is between l1 and l3, by checking l1(x0)<y0<l3(x0) or the other direction.
this is like a matrix search problem.represent rectangle as a matrix
find the four vertices of one rectangle, search each vertex to see if within the other's matrix.
vice versa
This is not a complete test. You can have intersecting rectangles without having any of the vertices of either rectangle not residing inside the other.
When the above test is inconclusive we can do the following...
check if any of the lines of rectangle one intersect with any of the lines of the other rectangle. If yes, check if the point of intersection lies between the corresponding vertices of both the lines.
These 2 tests put together will tell us if the rectangles overlap.
Get the equations of the 4 edges of one rectangle. If the rectangle edges are not parallel to the x, y axis, then they should have this form:
y-m1x= c1, y-m1x= c2 (assume c1 < c2) ; y - m2x = c3, y - m2x=c4 (assume c3 < c4)
If the other rectangle intersects with this rectangle, then one of its points must call in side this rectangle. That is, when you substitute point X,Y into the left hand side of the equation, you mush have Y-m1X = C1 where c1< C1 < c2, Y- m2x=C2, c3 < C2 < c4.
If the edges are parallel to x and y axis, then it is even easier to decide whether a point is inside a rectangle; that is , L < X < R, B < Y < T, where L,R are the left and right of the rectangle, B, T are the bottom and top of the rectangle
How are the rectangles represented? Or is that part of the problem?
- Anonymous March 08, 2009