One of my interview questions:
There's a table, and the top-left corner of the table is the origin (0, 0). On the table there are countless non-overlapping square cakes of different sizes.
The question: how do you make one horizontal cut (parallel to the x-axis) so that after the cut, the total cake area on each side is equal?
The interesting part is that all the coordinates are floats, but the side length of each cake is guaranteed to be an integer (e.g. 1.0). A cake's position, though, could have its top-left corner at something like (1.2, 2.1). So the y-coordinate where you make the cut could end up being a float (e.g. y = 2.3).
My approach:
Binary search. Search for the cut position between the origin and the bottom edge of the lowest cake. The time complexity depends on how precise you want to be — in some cases the cut position might come out to 1.1, or 1.11, or 1.111..., depending on how many decimal places you want the binary search to stop at.
Discussion
Loading comments…