Help with Jane Street Interview Question

[Lexee]

I'm having a hard time wrapping my mind around this problem. I understand perfectly well the general Lagrange multiplier solution offered by financeguy, but given the way this problem is stated, I just don't think it could be the right answer!

The rectangle needs to be large enough to accommodate at least these 2 scenarios:
-- both squares are equal, each with side=sqrt(2)/2
-- one square has a side nearly 1 and the other is very small (for example, x~0.99 and y~0.141)

The 1st scenario implies that one side of the rectangle needs to be at least sqrt(2).
The 2nd implies that the other side needs to be at least 0.99.
How can a rectangle with area=1.2071 satisfy both? Where is the fallacy in my reasoning?

 

[AndrewChang]

it cannot. area 1.2071 is not the solution such that the dimensions are fixed but rather it is the solution such that given the area of the squares will be 1, if I have a rectangle where I can manipulate the dimensions but keep the area fixed, 1.2071 is the minimum area needed such that I can fit all squares with sum area 1.

 

[Lexee]

Crystal clear now - thank you Andrew!

 

[liber]

I don't understand why you start with the assumption that squares have to be side by side. The worst case situation is to have both squares only with one vertex in common.

In that case, the worst case rectangle is when you have two squares of sides 1/sqrt(2). The area of the rectangle containing both squares is then (1/sqrt(2)+1/sqrt(2))^2=2. So with that rectangle I assure that any squares not overlapping will be contained.

to find the side of the biggest rectangle you solve: max (x+y) subject to x^2+y^2=1.

 

[aaronhotchner]

We don't assume the squares have to be side by side. The problem asks for the smallest rectangle that can hold any two squares with total area 1. If you start spreading out the squares to cover the largest perimeter, you're not following the objective of the question. That is, the smallest rectangle necessary will always have the squares touching fully along an edge. This is a property of the answer, and not an assumption.

In fact, your rebellious idea to have the squares touch at a vertex isn't a constraint implied by the problem at all. You could place the two squares on opposite sides of the world. It doesn't change the problem, though, and your solution will definitely be wrong if you ever have a rectangle that large.

Max(x+y) s.t. x^2+y^2 = 1 would be x=1/sqrt(2), y=1/sqrt(2), and thus x+y = sqrt(2) ~= 1.414. But we already have shown an answer of 1.2071 to be valid, and your suggestion is larger than that.

 

[liber]

I didn't understand the problem correctly. Yeah, it's Area=1.20. you have to solve the max x(x+y) st. x^2+y^2=1, x>y

 

[G_CAM]

The answer hardly requires any math.
Condition 1 : the sum of the surfaces of the squares needs to be 1
Condition 2: the squares are not allowed to overlap
Condition 3: the rectangle should enclose both squares and should be minimal.

From condition 1 and 2 and 3: The surface of the rectangle needs to be at least 1, and optimally (if possible) 1.

Can we find a rectangle with surface exactly 1? Yes, this means there are no dead spaces when the rectangle encloses both squares. if we fit 2 equally sized squares with sides 1/sqrt(2) next to each other then they form a rectangle with surface 1 (and there are no dead spaces). This means it must be the optimal solution!

So 2 squares of side 1/sqrt(2) side by side.

 

[Karth]

This is a bit late, but it looks like there's still a bit of confusion about this problem. I viewed this problem as a game.

1. You are asked to pick some fixed rectangle size, width W and height H.
2. An adversary comes over and gives you two squares whose areas sum up to 1.
3. You take those squares and place them in your W by H rectangle in any way such that they both fit without overlapping.

What's the minimum value for W * H?

To solve this, suppose that the sides of the squares are r and s where r > s without loss of generality. As most folks have seen, making the squares axis parallel makes the most sense (easy to show via contradiction -- draw it out and convince yourself if you don't see why this is true). In this case, the minimum possible rectangle area is r * (r + s). The adversary tries to screw you over as much as possible, so we need to maximize this quantity.

max r*(r+s)
s.t. r^2 + s^2 = 1

There are many ways to solve this (e.g. Lagrange multipliers). I chose to solve via trig + calc. Let r = cos x and s = sin x so that the constraint goes away. Letting cx = cos x and sx = sin x, we then have the single variable function f(x) = cx * (cx + sx) = cx*cx + cx*sx. Differentiating, f'(x) = -2*sx*cx + cx^2 - sx^2 = -sin 2x + cos 2x. Maximizing thus means we must set 2x = 45 degrees, so x = 22.5. Using the half angle identities, we have that the total area is (1 + sqrt(2)) / 2.