Algorithm · Google · Hard
You are given a list of points in the 2D plane. Find the rectangle with the largest area such that all four of its corners are points from the list, and return that area. The sides of the rectangle are not required to be parallel to the coordinate axes, so tilted rectangles count as well. Performance expectation: a first idea that runs in O(N^3) is a reasonable starting point, but you will be pushed to improve on it and reach a better complexity. Interview Notes Candidates…