## Google Interview Question for Software Engineers

Country: United States

Comment hidden because of low score. Click to expand.
0
of 0 vote

special case: lines of rectangles may not always be horizontal or vertical. e.g. (0, 0), (1, 2), (-3, 4), (-4, 2)

assumption: set of points are store in a hashed table. let's call it pointsSet

solution steps:
1. select any point
2. iterate through the rest of the points. O(n)
3. for each points in step 2, calculate the slope of the 2 points from step 1 and 2. using the slope(double, x/y) as key, store the point from step 2 into a hash table(let's call it slopeSet) and check if there's a tangent slope exists from previous points(by checking positive and negative of the inverse slope. if slope is represented as x/y, then check for -y/x and y/x)
4. if a previous slope is found in the slopeSet. use the 3 points to check if the fourth point exists in pointsSet(by calculating x and y displacements of the 3 points to get the fourth point). if it does compare the area with the current smallest area store in a variable(initialized as -1. if the value is -1 then replace the value with current area. else compare the area)
5. remove the point selected in step 1. and start from step 1 again until all points are compared. return smallest area. if -1 is returned then it means there's no rectangle formed from the points. O(n)

Performance evaluation:
O(n^2) since there are 2 for loops with O(n)

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.