• Write code to detect if two rectangles overlap or not?.

For this question, the first thing your interviewer would notice is how you represent a rectangle in code. Even if you have naive experience with geometry you would know that a rectangle can be represented by two of it's opposite corners. That is given any two opposite corners of a rectangle you can completely determine the other two corners and hence the rectangle.

There are two ways of solving this question. First you write checks for all cases when two rectangles can overlap. This is how I solved it in my interview. However this isn't how the interviewer would want you to solve the question. The other way is to only check when two rectangles don't overlap. This is much simpler. However the asymptotic compelxity for both the solution is the same i.e. O(1) since there are no loops just a couple of if statements.

Consider the following diagram. Consider all the four colored rectangles around the black one:

The rectangles don't overlap if one of the colored rectangles is either to the right or left of the black rectangle. Similarly, the colored rectangles can't overlap with the black one if they above or below the colored rectangles. A rectangle can also be both above and to the right of the black rectangle and that is just fine. However our main concern is that the colored rectangles need to be either to the left or right or above or below the black rectangle. If more than one conditions are satisfied we still declare the rectangles to be non-overlapping.

The colored rectangle will be to the left of the black rectangle if both x-coordinates of the colored rectangle are less than both the x-coordinates of the black rectangle.

The colored rectangle will be to the right of the black rectangle if both x-coordinates of the colored rectangle are greater than both the x-coordinates of the black rectangle.

The colored rectangle will be above the black rectangle if both y-coordinates of the colored rectangle are greater than both the y-coordinates of the black rectangle.

The colored rectangle will be below the black rectangle if both y-coordinates of the colored rectangle are less than both the y-coordinates of the black rectangle.

We just code up these four if statements and we are done. The other solution has much more if statements then this one and that's why interviewers generally