Count Squares in a Grid | Dataford Interview Questions

Count the number of squares in a figure of points connected by horizontal/vertical edges; a square only counts if all its edges exist, including squares spanning multiple points. Inputs cannot be string, char, image or binary.

Asked in the onsite coding stage.

Input and Output

Implement count_squares(points, edges). points is a list of unique [x, y] integer coordinates. edges is a list of horizontal or vertical unit segments, each represented by two endpoint coordinates. Return the number of axis-aligned squares whose four sides are completely formed by the provided segments. A side may contain multiple consecutive segments, and every required segment must exist.

Constraints

1 <= len(points) <= 500
0 <= x, y <= 10^4
0 <= len(edges) <= 2,000
Every edge is horizontal or vertical and has unit length
Every edge endpoint appears in points

Function Signature

def count_squares(points, edges):

Your question is Count Squares in a Grid. Start with the requirements in the Question tab.

Run and submit as often as you like. When you're ready, talk me through your approach or go straight to the code.

Problem