4 ms·

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) b

by MRD85 8y ago

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?".

graycat 8y ago
Nice answer. 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?

by MRD85 8y ago

graycat 8y ago

Nice answer. 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?