Data Structure and Algorithms Interview Questions for Programmers
Apparently one of the questions was:<p>Q. Given X-Y coordinates of two rectangles, determine if they intersect or not.<p>I&#x27;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!<p>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.<p>Suppose we have numbers u, v, w, and consider the set of all (x,y) such that<p>ux + vy = w<p>Then those points (x,y) form a line, and every line can be written in this form.<p>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<p>ua_i1 + va_i2 &gt;= w<p>and for all j<p>ub_i1 + vb_i2 &lt;= w<p>Or, we seek u, v, w to solve the linear program<p>maximize z = u + v + w<p>subject to<p>ua_i1 + va_i2 &gt;= w<p>ub_i1 + vb_i2 &lt;= w<p>for all i, j.<p>The simplex algorithm will determine if this linear program is <i>feasible</i>, 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<p>ux + vy = w<p>Else the linear program is not feasible, no line exists separating the convex hulls, and the two convex hulls overlap.<p>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&#x27;t overlap.<p>This solution solves the problem about rectangles in the OP as a special case.<p>Let&#x27;s see:  Given a closed convex set C with points A(i), is the convex hull of the points A(i) also in C?<p>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.<p>The <i>convex hull</i> of a set of points is the <i>smallest</i> 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 <i>convex hull</i> is <i>well defined</i> 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.<p>Is that a sufficiently good answer?