Google | L4 | Phone | U.S | Rejected
Summary
I interviewed for an L4 position at Google via phone and was rejected. I tackled a geometric problem involving finding squares from 2D coordinates but couldn't optimize my solution as requested.
Full Experience
I recently had a phone interview with Google for an L4 position in the U.S. The interviewer presented me with a geometric problem involving 2D integer coordinates. I had to identify all unique squares whose four corners were present in the input list of points and return their top-left corner and side length. I managed to come up with an O(n*m) solution, but the interviewer pressed for optimizations. Unfortunately, I wasn't able to devise a better approach within the given time. The interview concluded with my rejection.
Interview Questions (1)
Given a list of 2D integer coordinates, look for squares whose four corners occur in the input. Return the upper left corner and the side length of all such unique squares, in any order.
Input:
points = [
{"x": 2, "y": 4}, # top-left
{"x": 4, "y": 4}, # top-right
{"x": 2, "y": 2}, # bottom-left
{"x": 4, "y": 2}, # bottom-right
{"x": 5, "y": 5}, # extra random point
{"x": 0, "y": 0} # extra random point
][{'x': 2, 'y': 4, 'side': 2}]