Find horizontal cut balancing square areas
Company: Google
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
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.
Quick Answer: 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.
Part 1: Balanced Horizontal Cut in Non-Overlapping Squares
You are given n axis-aligned squares on a 2D plane with a top-left origin, so y increases downward. Each square is represented as [x, y, s], where (x, y) is the top-left corner and s is the side length. The squares do not overlap in area, though they may touch at edges. Find the smallest horizontal cut y* such that the total square area strictly above the line y = y* equals the total square area strictly below it. Because the line itself has zero area, points exactly on the line do not matter. Return y* rounded to 5 decimal places.
Constraints
- 1 <= len(squares) <= 200000
- Each square is [x, y, s] with x and y real-valued and s an integer
- 1 <= s <= 10^6
- Squares do not overlap in interior area
- 0 < eps <= 1e-3
Examples
Input: ([[0, 0, 2]],)
Expected Output: 1.0
Explanation: A 2x2 square has total area 4, so each side must contain area 2. The cut is halfway down the square at y = 1.0.
Input: ([[0, 0, 2], [3, 4, 2]],)
Expected Output: 2.0
Explanation: The first square contributes area 4 above y = 2, and the second square starts at y = 4. Any cut in [2, 4] balances the areas, so the smallest valid cut is 2.0.
Hints
- Let F(y) be the total area of all squares above the cut. What shape does F(y) have as y moves downward?
- A valid search interval is from the smallest square top to the largest square bottom.
Part 2: Balanced Horizontal Cut in Overlapping Squares Using Union Area
You are given n axis-aligned squares on a 2D plane with a top-left origin, so y increases downward. Each square is represented as [x, y, s]. Unlike Part 1, squares may overlap. The cake area is the area of the union of all squares, so overlapping regions count only once. Find the smallest horizontal cut y* such that the union area strictly above the line y = y* equals the union area strictly below it. Return y* rounded to 5 decimal places.
Constraints
- 1 <= len(squares) <= 20000
- Each square is [x, y, s] with x and y real-valued and s an integer
- 1 <= s <= 10^6
- Squares may overlap arbitrarily
- Coordinates have absolute value at most 10^9
Hints
- Sweep along y. Between two consecutive top/bottom edges, the set of active squares does not change, so the covered x-length is constant.
- To get union width quickly for active x-intervals, coordinate compression plus a segment tree is a standard approach.
Part 3: Balanced Horizontal Cut in Non-Overlapping Rectangles
You are given n axis-aligned rectangles on a 2D plane with a top-left origin, so y increases downward. Each rectangle is represented as [x, y, w, h], where (x, y) is the top-left corner, w is width, and h is height. Rectangles do not overlap in area, though they may touch at edges. Find the smallest horizontal cut y* such that the total rectangle area strictly above the line y = y* equals the total rectangle area strictly below it. Return y* rounded to 5 decimal places.
Constraints
- 1 <= len(rectangles) <= 200000
- Each rectangle is [x, y, w, h] with x and y real-valued
- w > 0 and h > 0
- Rectangles do not overlap in interior area
- Coordinates have absolute value at most 10^9
Hints
- Between consecutive rectangle top/bottom edges, the area gained per unit of y is constant.
- In each horizontal strip, that rate is the sum of widths of all rectangles crossing the strip.