How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a medium difficulty Coding & Algorithms question, commonly asked during Onsite rounds at Google.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Google during technical interviews.

Find horizontal cut balancing square areas

Quick Overview

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.

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.

Input: ([[0, 0, 1], [2, 0, 1], [0, 2, 2]],)

Expected Output: 2.5

Explanation: The two 1x1 squares contribute area 2 above y = 2. The total area is 6, so we need area 3 above the cut. That requires 1 more unit from the 2x2 square, which happens after going 0.5 units into it: y = 2.5.

Input: ([[5, -5, 5]],)

Expected Output: -2.5

Explanation: The square spans from y = -5 to y = 0. Its midpoint is y = -2.5, which splits its area equally.

Input: ([[0, 0, 2], [3, 0, 1]],)

Expected Output: 0.83333

Explanation: The total area is 5, so the target above-area is 2.5. From y = 0 to y = 1, the combined active width is 3, so the cut is at 2.5 / 3 = 0.83333 after rounding.

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.

Quick Overview