Q. Given X-Y coordinates of two rectangles, determine if they intersect or not.
I'll try for an answer -- I looked up nothing, and it took longer to type in the answer than it took to think of it!
A. Given positive integers m and n and m points A(i) = (a_i1, a_i2), i = 1, 2, ..., m and B(j) = (b_j1, b_j2), j = 1, 2, ..., n, determine if the convex hull of the points A(i) intersects the convex hull of the points B(j). So, look for a line that has all the points A(i) on one side and all the points B(j) on the other side.
Suppose we have numbers u, v, w, and consider the set of all (x,y) such that
ux + vy = w
Then those points (x,y) form a line, and every line can be written in this form.
Then we seek u, v, w so that all the A(i) are on one side of the line and all the B(j) are on the other side. So, without loss of generality, we seek u, v, w so that for all i
ua_i1 + va_i2 >= w
and for all j
ub_i1 + vb_i2 <= w
Or, we seek u, v, w to solve the linear program
maximize z = u + v + w
subject to
ua_i1 + va_i2 >= w
ub_i1 + vb_i2 <= w
for all i, j.
The simplex algorithm will determine if this linear program is feasible, that is, if u, v, w exist to satisfy the m + n linear constraints, or not feasible. If the program is feasible, then the two convex hulls are separated by the line the set of all (x,y) such that
ux + vy = w
Else the linear program is not feasible, no line exists separating the convex hulls, and the two convex hulls overlap.
Yes, we could tweak this simple formulation to something a little more involved and, then, determine if the two convex hulls just touch but otherwise don't overlap.
This solution solves the problem about rectangles in the OP as a special case.
Let's see: Given a closed convex set C with points A(i), is the convex hull of the points A(i) also in C?
Well, the intersection of any collection of closed sets is closed (the union of any collection of open sets are open). The intersection of any collection convex sets is convex. Then, the intersection of any collection of closed, convex sets is closed and convex.
The convex hull of a set of points is the smallest closed convex set that contains all the points, that is, the intersection of all closed convex sets that contain all the points and, thus, is closed and convex. Here convex hull is well defined since the intersection is unique. A line in X-Y and one side of that line is closed and convex. So the convex hull of a set of points on the line and some one side of it is closed, convex, and a subset of the line and that side of it. Our algorithm needs this result.
If I was an interviewer I wouldn't like this response for most jobs, although it would be fine for a small subset of jobs. The overlap of two rectangles is an easy question with an easy answer and a long, more complicated answer would indicate that the interviewee missed social queues about what is expected in the answer and may be a difficult person to work with.
Looking at the "solution" in the OP, there was a HUGE assumption NOT stated, implied, etc. in the statement of the question: The assumption was that the sides of the rectangles were parallel to the orthogonal X-Y axes. So, the question was badly stated.
For how the question was STATED, my solution may be about the easiest.
> The overlap of two rectangles is an easy question with an easy answer
You have an "easy" answer to how the question was stated? Until I hear or think of a much easier answer, I have to conclude that your statement of an "easy question" is false.
The OP certainly did NOT have a solution to the question as stated.
> If I was an interviewer I wouldn't like this response for most jobs, although it would be fine for a small subset of jobs.
The interview questions were to be for "most jobs". Then "most jobs" should prefer a correct answer, that is, correct for the question as stated.
Or, the question could be important for many jobs working with graphics, rectangles, triangles, etc., and there commonly we won't have specific orientations, say, rectangle sides parallel to the X-Y axes.
> social queues about what is expected
The interview questions are supposed to be challenging and to let the candidate show their capabilities. In that context, "what is expected" should not limit the power of an answer.
If the company wants only people who know not much more and not much less than the people already there, then the company, should not be looking for new people, is on the way downhill, also because of that should not be hiring, and no good candidate should want to work there.
The OP questions were to be about "data structures and algorithms". Well, I used the simplex algorithm, seriously ranked as one of the best pieces of engineering in the 20th century. A special case of that algorithm is min cost capacitated flows on networks, and there is a really cute algorithm there and a cute use of a spanning tree on a network. So, my answer was good for "algorithms and data structures".
Easy answer (even if the sides aren't orthogonal):
Step 1 - Find all pairs of line segments where there is overlap on the x and y planes. This step is O(n^2) but since we're dealing with rectangles it's only 16 checks.
Step 2 - For the line segments that do have overlap check to see if the intersection occurs within the line segments or outside of it. If there is a line intersection within a pair of segments then there is an overlap of rectangles.
For the question as STATED (4 sides) this will run quickly and a first year CS student could implement it, or read it and understand what is happening. I could use a whiteboard and explain this algorithm to high school students.
When you hire for a company you do want programmers that will have a correct code solution. You also want programmers that will write code that is easy for others to maintain, you want programmers who are pleasant to work with, aren't difficult people, etc. In an interview, the technical questions are only part of the interview process. There is also the underlying question of "is this a person I want to work with?".
But since I studied a lot of optimization, I saw my linear programming answer first. On an interview, typically want to give the first correct answer do find.
My answer is more general, and that is goodness. Indeed, you mentioned that your answer solves a more general question than intended in the OP. So, you seem to like the generality of your answer but not the generality of mine.
The generality of my answer applies to convex polytopes, convex hulls, in any finite dimension, and dimension 3 should be of interest in some cases, e.g., see if two objects intersect. That might be of interest in some of robotics.
If the polytopes are determined by points, then my answer solves the problem and we are looking for a separating hyper plane. If each polytope is determined by the intersection of half spaces determined by hyperplanes, then we are looking for a point in common, and again we can use linear programming. So, given points we are looking for a separating hyper plane, and given hyper planes we are looking for a point. Smells like a nice case of duality.
Farkas lemma, a special case of my solution, is central to the Kuhn-Tucker conditions in nonlinear optimization. Since the ML people are interested in optimization, they might welcome Farkas lemma and my more general solution.
And, again, my answer really is part of "algorithms and data structures" which was the focus of the questions.
So, now we are into what is commonly called computational geometry, commonly regarded as part of computer science, and heavily about algorithms. E.g., doing nearest neighbor searches via k-D trees (in Sedgwick) and cutting planes is part of computer science, computational geometry, trees, data structures, and algorithms.
For the linear programming, just call a subroutine, e.g., IBM's old OSL (optimization subroutine library).
My more general answer indicates that I would be a good person to work with.
The question is a separation problem. Well, so as to have readers be more comfortable, I did omit mention of the Hahn-Banach theorem. For curious readers, there are lots of applications of that classic result in D. Luenberger, Optimization by Vector Space Methods.
"Hard to work with ...". How 'bout hard to please?
Q. Given X-Y coordinates of two rectangles, determine if they intersect or not.
I'll try for an answer -- I looked up nothing, and it took longer to type in the answer than it took to think of it!
A. Given positive integers m and n and m points A(i) = (a_i1, a_i2), i = 1, 2, ..., m and B(j) = (b_j1, b_j2), j = 1, 2, ..., n, determine if the convex hull of the points A(i) intersects the convex hull of the points B(j). So, look for a line that has all the points A(i) on one side and all the points B(j) on the other side.
Suppose we have numbers u, v, w, and consider the set of all (x,y) such that
ux + vy = w
Then those points (x,y) form a line, and every line can be written in this form.
Then we seek u, v, w so that all the A(i) are on one side of the line and all the B(j) are on the other side. So, without loss of generality, we seek u, v, w so that for all i
ua_i1 + va_i2 >= w
and for all j
ub_i1 + vb_i2 <= w
Or, we seek u, v, w to solve the linear program
maximize z = u + v + w
subject to
ua_i1 + va_i2 >= w
ub_i1 + vb_i2 <= w
for all i, j.
The simplex algorithm will determine if this linear program is feasible, that is, if u, v, w exist to satisfy the m + n linear constraints, or not feasible. If the program is feasible, then the two convex hulls are separated by the line the set of all (x,y) such that
ux + vy = w
Else the linear program is not feasible, no line exists separating the convex hulls, and the two convex hulls overlap.
Yes, we could tweak this simple formulation to something a little more involved and, then, determine if the two convex hulls just touch but otherwise don't overlap.
This solution solves the problem about rectangles in the OP as a special case.
Let's see: Given a closed convex set C with points A(i), is the convex hull of the points A(i) also in C?
Well, the intersection of any collection of closed sets is closed (the union of any collection of open sets are open). The intersection of any collection convex sets is convex. Then, the intersection of any collection of closed, convex sets is closed and convex.
The convex hull of a set of points is the smallest closed convex set that contains all the points, that is, the intersection of all closed convex sets that contain all the points and, thus, is closed and convex. Here convex hull is well defined since the intersection is unique. A line in X-Y and one side of that line is closed and convex. So the convex hull of a set of points on the line and some one side of it is closed, convex, and a subset of the line and that side of it. Our algorithm needs this result.
Is that a sufficiently good answer?