Katkat
Back

Determine whether points form squares

PurestorageSoftware Engineer · Onsite
MediumSoftware EngineerOnsiteCoding & Algorithms

Last updated

This question evaluates computational geometry, combinatorial counting, and algorithmic optimization skills by requiring validation of a non-degenerate square from four 2D integer points and counting distinct squares in a larger point set, and it falls under the Coding & Algorithms category.

Problem: Square detection and counting from point coordinates

You are given points on a 2D plane with integer coordinates.

Part A — Validate a single square

Given exactly 4 points [(x1,y1), (x2,y2), (x3,y3), (x4,y4)], determine whether these 4 points can be the vertices of a non-degenerate square (square may be rotated; sides are not necessarily axis-aligned).

Output: true if they form a square, otherwise false.

Part B — Count squares in a set (with optimization)

Given N points (may contain duplicates; treat duplicates as separate inputs but they should not create degenerate “squares”), count how many distinct squares can be formed whose 4 vertices are all present in the set.

  • A square is considered the same regardless of the order of its vertices.
  • Squares may be rotated.

Follow-up:

  1. Describe a brute-force approach (e.g., around (O(n^4))).
  2. Improve it to about (O(n^3)).
  3. Further improve to about (O(n^2)) time (assume hash set / hash map lookups are (O(1)) average).

Constraints (assume typical interview constraints)

  • 1 <= N <= 2e4 (for the optimized discussion)
  • Coordinates fit in 32-bit signed integers

Clarify any additional assumptions you need (e.g., whether duplicates should be ignored by converting to a set).