Paypal OA 面试真题解析：Finding Squares（Letter Grid 中的正方形）

Finding Squares

Square employees are internally referred to as "squares." Recruiting is about finding quality squares. In this exercise, you will be finding valid squares in a letter grid.

Part 1: Creating a Letter Grid

A letter grid is defined as a rectangular grid with one letter at each position. Create a data structure for a letter grid that can be instantiated from a string.

For instance, the string "ABBA UBBU ALAN ALDA" becomes the following grid:

A B B A
U B B U
A L A N
A L D A

Part 2: Locating Valid Squares

A valid square is defined as four points in the letter grid in the shape of a square (equal length sides, 90 degree angles) with the same letter at each corner. The letter grid above has two valid squares:

• a B square with a side length of 1
• an A square with a side length of 3

Create a program to locate all valid squares in a letter grid.

这题分两部分：先把输入字符串构造成一个二维字母网格，再在网格中找出所有“有效正方形”——即四个顶点坐标构成正方形、四角字母相同。实现时通常先把每个字符的位置收集起来，按字母分组；然后枚举同一字母的点对，把它们当作正方形的一条边，利用向量旋转或几何关系推导另外两个顶点是否存在。重点是正确处理边长、方向与坐标边界，并避免重复计数。