Find horizontal cut balancing square areas

Q: Find horizontal cut balancing square areas

This question evaluates computational geometry and algorithm design skills, focusing on area computation, monotonicity reasoning, existence proofs, root-finding under floating-point constraints, and considerations of numerical stability and complexity.

Q: How do I approach Coding & Algorithms interview questions?

Coding & Algorithms questions require understanding of core concepts and practice. PracHub provides solutions with explanations to help you master coding & algorithms interviews.

Question

Given a 2D table with top-left origin (0, 0), you are provided a finite set of n non-overlapping, axis-aligned square cakes. Each square i has real-valued top-left coordinates (x_i, y_i) and an integer side length s_i ≥ 1. Design an algorithm to find a horizontal cut y* (parallel to the x-axis) such that the total cake area strictly above the line equals the total area strictly below it. Specify the search interval, prove a solution exists, and argue monotonicity needed for your approach. Provide the time and space complexity in terms of n and precision ε, and discuss numerical stability and stopping criteria when coordinates are floats. If multiple y* exist, explain how you would return one. Finally, discuss how your method would change if (a) squares could overlap, or (b) shapes were axis-aligned rectangles instead of squares.

Find horizontal cut balancing square areas

Overview

Comments (0)