Construct the Rectangle

Construct the Rectangle

What is this problem about?

In the Construct the Rectangle interview question, you are a web developer who needs to design a rectangular area. You are given the total area, and you need to find a length L and a width W such that:

1. L * W = area
2. L >= W
3. The difference L - W is as small as possible.

Why is this asked in interviews?

This Construct the Rectangle coding problem is a common "Easy" question at Amazon and Google. It tests your ability to use basic math properties (square roots) to optimize a search. It’s a simple test of whether a candidate will use a naive O(area) loop or an optimized O(sqrt(area)) approach.

Algorithmic pattern used

This utilizes the Math interview pattern.

• To minimize the difference L-W, W should be as close to sqrt(area) as possible.
• Start W at floor(sqrt(area)) and count down to 1.
• The first W that divides the area evenly is your optimal width.
• Then, L = area / W.

Example explanation

Suppose area = 12.

1. sqrt(12) is approximately 3.46. Start W = 3.
2. Is 12 divisible by 3? Yes.
3. W = 3, L = 12 / 3 = 4.
4. Check conditions: 4 * 3 = 12, 4 >= 3, difference is 1. Result: [4, 3]. If you started from W=1, you would find [12, 1], but the difference is much larger.

Common mistakes candidates make

• Starting from 1: Iterating W from 1 to area is unnecessary and slow.
• Ignoring L >= W: Returning the width as the larger number.
• Incorrect loop bound: Not stopping at the square root, or using a float comparison instead of integer division.

Interview preparation tip

For problems involving finding pairs of factors, always consider the square root as the "middle ground." It is the point where the factors are closest to each other.