Google L3 Onsite
Summary
I had an onsite interview round at Google where I encountered a challenging geometry problem about finding the largest rectangle from a given set of points.
Full Experience
Hey everyone 👋, I came across a really interesting and challenging geometry-based problem during my Google onsite round.
Interview Questions (1)
You're given a list of distinct 2D points on a Cartesian plane. Your task is to find the area of the largest rectangle that can be formed by selecting any four points from the list such that those four points form the corners of a valid rectangle.
🔹 Important Constraints:
The rectangle does not need to be axis-aligned.
The rectangle can lie in any orientation (e.g., rotated at 45 degrees).
All four corners of the rectangle must be present in the input point list.
Your goal is to compute the maximum possible area of any such rectangle.
points = [
[-5, -5], [-5, 0], [0, -5], [0, 0],
[-3, 2], [-2, 3], [1, 2], [0, 1],
[-4, -1], [1, -6], [1, -1], [-4, -6],
[2, 2], [3, 3], [4, 4],
[-2, -2], [-1, -1], [0, 0], [1, 1],
[5, 5], [-5, 5], [5, -5], [-5, -5]
]