Find Repeated-Value Patterns in a Matrix
Company: Capital One
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Online Assessment
Find every placement of a small symbol matrix inside a larger integer matrix that preserves the pattern of equal and different values.
Implement `find_pattern_positions(grid: int[][], pattern: string[]) -> int[][]`. Each pattern string is one row of uppercase letter symbols. Return the zero-based top-left coordinate of every matching window, ordered by row and then column.
### Matching contract
For each candidate window independently, there must be a one-to-one mapping between symbols and integer values:
- Every occurrence of the same symbol must match the same integer.
- Different symbols must match different integers.
- The mapping can differ between windows.
The report illustrates `AT/TB` matching `1,2/2,3` but does not explicitly resolve whether different symbols may share a value. This practice version chooses the one-to-one interpretation above.
### Constraints & Assumptions
- The grid is rectangular, with 1 through 50 rows and columns.
- The pattern is rectangular, with 1 through 5 rows and columns, and symbols `A` through `Z`.
- Grid values are integers between -1,000,000,000 and 1,000,000,000.
- A window must fit fully inside the grid. If the pattern is larger in either dimension, return an empty list.
- Do not rotate, reflect, or resize the pattern.
### Examples
```text
grid = [[1,2,4,5],[2,3,6,7],[6,4,2,2]]
pattern = ["AT","TB"]
result = [[0,0]]
```
```text
grid = [[7,7],[7,7]]
pattern = ["AA","AA"]
result = [[0,0]]
```
The first example's upper-left window maps `A -> 1`, `T -> 2`, and `B -> 3`.
```hint Enforce both directions of the mapping
Remember both the integer assigned to each symbol and the symbol assigned to each integer. Checking only repeated symbols does not enforce distinctness between different symbols.
```
Overview: Match a symbol pattern inside an integer matrix using per-window bijections, repeated values, distinct symbols, and ordered match coordinates.
Read the full Capital One Software Engineer interview experience this question came from
Find every placement of a small symbol matrix inside a larger integer matrix that preserves the pattern of equal and different values.
Implement `find_pattern_positions(grid: int[][], pattern: string[]) -> int[][]`. Each pattern string is one row of uppercase letter symbols. Return the zero-based top-left coordinate of every matching window, ordered by row and then column.
### Matching contract
For each candidate window independently, there must be a one-to-one mapping between symbols and integer values:
- Every occurrence of the same symbol must match the same integer.
- Different symbols must match different integers.
- The mapping can differ between windows.
The report illustrates `AT/TB` matching `1,2/2,3` but does not explicitly resolve whether different symbols may share a value. This practice version chooses the one-to-one interpretation above.
### Constraints & Assumptions
- The grid is rectangular, with 1 through 50 rows and columns.
- The pattern is rectangular, with 1 through 5 rows and columns, and symbols `A` through `Z`.
- Grid values are integers between -1,000,000,000 and 1,000,000,000.
- A window must fit fully inside the grid. If the pattern is larger in either dimension, return an empty list.
- Do not rotate, reflect, or resize the pattern.
### Examples
```text
grid = [[1,2,4,5],[2,3,6,7],[6,4,2,2]]
pattern = ["AT","TB"]
result = [[0,0]]
```
```text
grid = [[7,7],[7,7]]
pattern = ["AA","AA"]
result = [[0,0]]
```
The first example's upper-left window maps `A -> 1`, `T -> 2`, and `B -> 3`.
```hint Enforce both directions of the mapping
Remember both the integer assigned to each symbol and the symbol assigned to each integer. Checking only repeated symbols does not enforce distinctness between different symbols.
```
Constraints
- Grid dimensions are 1 through 50 by 1 through 50; values range from -1000000000 through 1000000000.
- Pattern dimensions are 1 through 5 by 1 through 5, rectangular, using uppercase A through Z.
- Each matching window has its own bijection: equal symbols map to equal values and distinct symbols to distinct values.
- Windows must fit fully and retain pattern orientation and size.
- Return all zero-based [row,col] coordinates in row-major order or [] when none fit or match.
Examples
Input: ([[1, 2, 4, 5], [2, 3, 6, 7], [6, 4, 2, 2]], ['AT', 'TB'])
Expected Output: [[0, 0]]
Explanation: The source repetition structure matches only the upper-left window.
Input: ([[7, 7], [7, 7]], ['AA', 'AA'])
Expected Output: [[0, 0]]
Explanation: One repeated symbol maps to one repeated value.