Paypal OA Interview Question: Finding Squares in a 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.

This problem has two parts: first, build a 2D letter grid from a string representation; then find all valid squares whose four corners contain the same letter. A practical solution is to group coordinates by character, enumerate point pairs for each letter, and use geometric relationships or vector rotation to derive the other two corners of the square. The main challenges are handling orientation, side length, grid bounds, and avoiding duplicate square counts.