google logo
Google· SDE I

Google L3 Onsite

Posted
3 May 2025
429 reads

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.

How it went

Hey everyone 👋, I came across a really interesting and challenging geometry-based problem during my Google onsite round.

Questions asked (1)

  1. 01

    Largest Rectangle from Points

    Data Structures & Algorithms · Hard

    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] ]

Know someone preparing? Send it to them:WhatsAppLinkedInX

Interviewed at Google recently?

Write up your rounds while you still remember the questions. It helps the next person more than you would think.

Share your experience
Discussion 0

Questions for the author, or how your own interview compared.

Join the discussion

Sign in with Google to comment or ask the author a question.

No comments yet

Be the first to share your thoughts and start the discussion!