Valid Square

Valid Square

What is this problem about?

The "Valid Square" interview question asks you to determine if four points in a 2D coordinate system form a valid square. A square must have four equal sides and two equal diagonals. Additionally, the area must be non-zero (the points cannot all be the same).

Why is this asked in interviews?

Companies like Google and TikTok use the "Valid Square" coding problem to evaluate a candidate's ability to apply geometric principles to programming. It's more than just a coordinate check; it's about identifying the unique properties of a geometric shape and translating them into a simple, robust algorithm.

Algorithmic pattern used

The "Math and Geometry interview pattern" for this problem involves calculating the squared distance between every possible pair of points. With four points, there are (4 * 3) / 2 = 6 unique distances. In a square, there should only be two distinct distance values: the side length squared and the diagonal length squared.

Example explanation

Points: p1(0,0), p2(1,1), p3(1,0), p4(0,1).

1. Calculate all 6 squared distances:
   • dist(p1,p3) = 1, dist(p1,p4) = 1, dist(p2,p3) = 1, dist(p2,p4) = 1 (Sides)
   • dist(p1,p2) = 2, dist(p3,p4) = 2 (Diagonals)
2. Collect distances: {1, 1, 1, 1, 2, 2}.
3. Number of unique distances: 2. (1 and 2).
4. Since there are exactly two unique positive distances, and the smaller one appears 4 times (sides) and the larger one appears 2 times (diagonals), it is a valid square.

Common mistakes candidates make

A frequent mistake is not checking for zero distances; if all points are (0,0), there is only one unique distance (0), which is not a square. Another error is assuming the points are given in order (e.g., clockwise). A robust solution must work regardless of the order in which the points are provided.

Interview preparation tip

For the "Valid Square" coding problem, using the squared distance ((x2-x1)² + (y2-y1)²) is better than using the actual distance because it avoids square root calculations and floating-point precision issues. It keeps your logic entirely within the realm of integers.