Count Squares from Points in the Plane

Question

The question asks the candidate to determine how many squares can be formed from a given list of 2D points on a plane by selecting any four points.

Codemia · Accepted Answer

To count the number of squares that can be formed by four points, we can leverage the properties of squares in geometry. A square can be defined by its center and the distance from the center to its corners. By iterating through all pairs of points, we can determine potential square centers and check if the other two corners exist.

1. Store all points in a set for O(1) lookup.
2. For each pair of points (p1, p2), calculate the potential positions of the other two corners of the square using rotation formulas.
3. Check if these calculated points exist in the set.
4. Count valid squares and ensure each square is only counted once.

The time complexity of this solution is O(n^2), where n is the number of points, due to the nested iteration over pairs of points. The space complexity is O(n) for storing the points in a set.

```python
def count_squares(points):
    point_set = set(map(tuple, points))
    count = 0
    for i in range(len(points)):
        for j in range(i + 1, len(points)):
            p1 = points[i]
            p2 = points[j]
            # Calculate potential square corners
            dx = p2[0] - p1[0]
            dy = p2[1] - p1[1]
            p3 = (p1[0] - dy, p1[1] + dx)
            p4 = (p2[0] - dy, p2[1] + dx)
            if p3 in point_set and p4 in point_set:
                count += 1
    return count // 4  # Each square is counted 4 times
```
This code iterates through all pairs of points and calculates the other corners of the square, checking for their existence in the set.

Interviewers look for a clear understanding of geometric properties, the ability to devise an efficient algorithm, and effective coding skills. They also assess how well candidates can explain their thought process and handle potential edge cases.

Count Squares from Points in the Plane

6Sense

What the Interviewer Expects

Key Topics to Cover

How to Approach This

Possible Follow-up Questions

Sharpen Your Skills on Codemia

Sample Answer

Approach

Algorithm

Submit Your Answer

6Sense Software Engineer Interview Guide

Related Questions

Binary Search on graph

Count kth largest element in array

Find connected components in string

Merge Three Sorted strings

Binary Search on string