Google Question #2

In a x‑y cartesian plane, squares are made with axes parallel to the x‑axis and y‑axis. Their top‑left corner (x, y) and edge length a are given for each. We have to tell a horizontal axis that divides the area of all squares into two equal halves.

l = [(1,2),(2,4)] // top‑left coordinates
sizes = [5,10] // edge lengths

She told me I can just give an outline of how I would solve it; I didn’t have to code it since we didn’t have enough time.

Solution – I was able to come up with a binary‑search solution. I thought we could take a range for y‑coordinates, then simply check in O(n) time how much area is above a proposed axis A1 and how much is below it A2. This would be an O(n log y) solution.

The interviewer wasn’t satisfied and told me to think of a better solution.

I wasn’t able to do it in the remaining time and she ended the round.

Later, I thought of this solution…

It involves calculating a weighted average.

l = [(1,2),(2,4)]
sizes = [5,10]

So for each square we can assume it as a point with weight equal to its area at the average of its y‑coordinates. For the first square the average y is (2 + (2‑5)) / 2 = -0.5, weight 25 (area). For the second square the average y is (4 + (4‑10)) / 2 = -1, weight 100 (area).

ans = (-0.5 * 25 - 1 * 100) / 125 = -0.9

This yields an O(N) solution.