In a x-y cartesian plane , squares are made with axes paralled to x-axis and y- axis, their topleft corner x,y is given and edge length a is given for each,, we have to tell a horizontal axis that divides the area of all squares in 2 equal halves.
l=[(1,2),(2,4)] //topleft coordinates
sizes=[5,10] //edge lengths
She told me i can just give on how would i solve it, i don'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 felt we can take range for y coordinates , then we could simple check in O(n) time for how much area is above A1 and how much is below the proposed axis A2 .
this would be O(nlogy) solution.
The interviewer wasn't satisfied and told me to think of a better
solution.
Wasn't able to do in the remaining time and she ended the round.
Later , i thought of the this solution..
It involves calculating weighted average.
l=[(1,2),(2,4)]
sizes=[5,10]
so for each square you can assume it as point weight equal to its area at average of their y coordinate (2+(-3))/2=-0.5. so at y coordinate=-0.5 we can assume 25(area) weight, similarly at -1 a weight of 100(area)
ans =(-0.5 25-1100)/125 =-0.9
O(N) solution


