How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a medium difficulty Coding & Algorithms question, commonly asked during Onsite rounds at Purestorage.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Purestorage during technical interviews.

Determine whether points form squares | Purestorage Coding Question

Quick Overview

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.

Determine whether points form squares

Company: Purestorage

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Onsite

## 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).

Quick Answer: 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.

Validate a Single Square

You are given exactly 4 points on a 2D plane with integer coordinates as a list `points = [[x1,y1],[x2,y2],[x3,y3],[x4,y4]]`. Determine whether these 4 points can be the vertices of a **non-degenerate square**. The square may be rotated (sides are not necessarily axis-aligned). A set of points where two or more coincide, or where the points are collinear, is **not** a valid square. Return `true` if they form a square, otherwise `false`. **Approach hint:** Compute all 6 pairwise squared distances. A square has exactly 4 equal smallest distances (the sides) and 2 equal largest distances (the diagonals), where diagonal² = 2 × side², and side² must be greater than 0. Using *squared* distances keeps everything in integer arithmetic and avoids floating-point error.

Constraints

Exactly 4 points are provided.
Coordinates fit in 32-bit signed integers.
Coincident points or collinear points do not form a square.
The square may be rotated (not necessarily axis-aligned).

Examples

Input: [[0,0],[0,1],[1,1],[1,0]]

Expected Output: True

Explanation: Unit axis-aligned square.

Input: [[0,0],[2,1],[3,-1],[1,-2]]

Expected Output: True

Explanation: Rotated square with side² = 5 and diagonal² = 10.

Input: [[0,0],[0,2],[3,2],[3,0]]

Expected Output: False

Explanation: A 3x2 rectangle — sides unequal, not a square.

Input: [[0,0],[1,1],[1,0],[0,0]]

Expected Output: False

Explanation: Two vertices coincide (degenerate).

Input: [[0,0],[0,0],[0,0],[0,0]]

Expected Output: False

Explanation: All points identical — fully degenerate.

Input: [[1,0],[-1,0],[0,1],[0,-1]]

Expected Output: True

Explanation: Square rotated 45 degrees, centered at origin.

Input: [[0,0],[0,3],[4,0],[4,3]]

Expected Output: False

Explanation: A 4x3 rectangle, not a square.

Hints

Avoid floating point: compare *squared* distances so all math stays in integers.
Collect all 6 pairwise squared distances and sort them.
A valid square: the 4 smallest are equal (sides, > 0) and the 2 largest are equal and equal to 2× the side² (diagonals).

Count Squares in a Point Set

You are given `N` points on a 2D plane with integer coordinates as a list `points = [[x,y], ...]`. The input may contain duplicate coordinates; duplicates should be collapsed (they cannot help form a square). Count how many **distinct squares** can be formed whose **4 vertices are all present in the set**. A square is the same regardless of the order of its vertices, and squares may be rotated. **Optimization story (this is exactly the interview follow-up):** - Brute force: try every 4-tuple of points and test if they form a square — about `O(n^4)`. - Better: fix one side (a pair of points) and derive the other two vertices — about `O(n^3)`. - Best (implemented here): iterate over every **pair of points treated as a diagonal**, derive the other two vertices via the perpendicular-diagonal formula, and check membership in a hash set — about `O(n^2)` with O(1) average lookups. Each square is discovered via both of its diagonals, so divide the final count by 2. Given a diagonal with endpoints `(x1,y1)` and `(x2,y2)`, the other two vertices are `((x1+x2 + y1-y2)/2, (y1+y2 + x2-x1)/2)` and `((x1+x2 - y1+y2)/2, (y1+y2 - x2+x1)/2)`. They count only when those coordinates are integers and both are present in the set.

Constraints

1 <= N <= 2e4 for the optimized discussion.
Coordinates fit in 32-bit signed integers.
Duplicate coordinates are collapsed and cannot form a square.
A square counts once regardless of vertex order; rotated squares count.

Examples

Input: [[0,0],[0,1],[1,1],[1,0]]

Expected Output: 1

Explanation: A single unit square.

Input: [[0,0],[0,1],[1,1],[1,0],[2,0],[2,1]]

Expected Output: 2

Explanation: A 2x3 grid of points forms two adjacent unit squares.

Input: [[0,0],[0,1],[0,2],[1,0],[1,1],[1,2],[2,0],[2,1],[2,2]]

Expected Output: 6

Explanation: 3x3 grid: four 1x1 squares, one 2x2 square, and one rotated square (0,1),(1,2),(2,1),(1,0).

Input: [[0,0],[2,1],[3,-1],[1,-2]]

Expected Output: 1

Explanation: Four vertices of one rotated square.

Input: []

Expected Output: 0

Explanation: No points, no squares.

Input: [[0,0]]

Expected Output: 0

Explanation: A single point cannot form a square.

Input: [[0,0],[5,5],[5,0],[0,5]]

Expected Output: 1

Explanation: One 5x5 axis-aligned square.

Input: [[0,0],[0,0],[0,1],[1,1],[1,0]]

Expected Output: 1

Explanation: Duplicate point collapses; still exactly one unit square.

Input: [[0,0],[1,0],[2,0],[3,0]]

Expected Output: 0

Explanation: All collinear points — no square possible.

Hints

Put all distinct points in a hash set for O(1) average membership tests.
Treat each pair of points as a diagonal of a candidate square; the perpendicular bisector of equal length gives the other two vertices.
Derived vertex coordinates may be non-integer (half values) — skip those (a real lattice square would land on integer coordinates).
Each square has two diagonals, so it is counted twice — divide the total by 2.

Quick Overview