This post is in continuation of my prev one https://leetcode.com/discuss/interview-question/5584385/Google-interview-experience-or-L4-Software-engineer-or-All-rounds.

Screen round question
Gven set of points in a X-Y plane representing rectangles, find a vertical line which divides the plane into two halfs of equal areas.

NOTE:
Given rectangles can overlap with each other
The veritical line can pass through the rectangles
It was an open ended question and things were expected to get clarified by asking questions. I pictured out the question as shown below.

Solution
The main part of this problem was to figure out how to calculate the area of rectangles, mainly for the cases where the required vertical line passes through the rectangles.

If we consider a given points as [x1, y1, x2, y2] where (x1, y1) represents the bottom left vertex of the rectangle and (x2, y2) represents the top right end of the rectangle. Then for a given line x = x3, there are 3 possibilities

1. The line lies to the right side of the rectangle i.e. x3 > x2 : In that case the entire rectangle area (x2 - x1) * (y2 - y1) will be added to the leftArea.
2. The line lies to the left side of the rectangle i.e. x3 < x1 : In that case the entire rectangle area (x2 - x1) * (y2 - y1) will be added to the rightArea.
3. The line divides the rectange into 2 parts : In this scenario, the leftArea is going to be incremented by (x3 - x1) * (y2 - y1) and rightArea is going to be incremented by (x2 - x3) * (y2 - y1)

We have to apply the same logic with all the given points and eventually compare the leftArea and rightArea and at any point, if both becomes equal, we have the required line.

Now, if we keep on checking for each line from 1 to x to find the required vertical line, the complexity will be quadratic.

To further optimize the same, binary search can be used where the left bound can be 1 and right bound will be x (where x can be found by iterating over the entire set of points & storing the maximum x-coordinate among it). Then for each iteration (i.e. mid = (left + (right - left)/2 ), the above logic can be applied and then,

1. if leftArea > rightArea, then the line needs to be moved to the left side i.e right = mid - 1
2. if leftArea < rightArea, then the line needs to be moved to the right side i.e left = mid + 1
3. thats the answer

Time complexity : O(N logX), where N : number of given points & X : max value of x-axis coordinate.
Space complexity: O(1) (Only original given array of points was used)

I hope this post would help others to prepare well for their upcoming interviews.