Meta·Software Engineer·Technical Phone Screen·Intermediate

IntermediatePrefer not to say

Jun 2026Remote

Summary

Meta coding interview with a grid manipulation problem that looks straightforward until you actually sit down and think about the symmetry constraints. One question, medium-to-hard difficulty, left me second-guessing my approach the whole time.

Questions Asked (1)

Given an n x n grid (n is odd) where each cell holds a value of 0, 1, or 2, find the minimum number of cells you need to change so that the grid contains a valid 'Y' shape. The Y is defined by the two top diagonals meeting at the center plus a vertical line going down from the center, all sharing one value, with every other cell sharing a different single value.

Algorithms & Data Structures

Author's notes

I spent way too long trying to brute force the value assignments before realizing you only have a small number of candidate (Y-value, background-value) pairs since both values are drawn from {0,1,2} and they have to be different.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

First, identify the set of cells that form the Y shape (the two top diagonals and the vertical line down from the center). Then, for each possible value (0, 1, 2) assigned to the Y, count how many cells in the Y need to change to that value and how many cells outside the Y need to change to a different single value (which can be any of the other two values). The minimum total changes over all choices gives the answer.

Pro tip: Clarify that the 'different single value' for the non-Y cells can be any of the other two values, not necessarily the same across all non-Y cells? Actually it must be a single value, so we choose the best one. Also, mention that the Y shape is fixed and symmetric, so you can precompute the cell sets.

1. Identify the Y-shaped cells

Determine the coordinates of all cells that belong to the Y: the two diagonals from the top corners to the center, and the vertical line from the center to the bottom. Since n is odd, the center is at (n//2, n//2).

2. Count frequencies for Y cells

For each possible value v (0,1,2), count how many cells in the Y already have value v. The number of changes needed to make all Y cells equal to v is (size of Y) minus that count.

3. Count frequencies for non-Y cells

For each possible value w (0,1,2), count how many cells outside the Y already have value w. The number of changes needed to make all non-Y cells equal to w is (total cells - size of Y) minus that count.

4. Compute total changes for each pair (v, w) with v ≠ w

For each valid pair where the Y value v and the non-Y value w are different, sum the changes from steps 2 and 3. The minimum sum over all such pairs is the answer.

5. Return the minimum

After evaluating all possible assignments, return the smallest total number of changes.

Key Points to Mention

The Y shape consists of exactly 3n - 2 cells? Actually: two diagonals each have n cells, but they share the center, so total diagonal cells = 2n - 1. The vertical line from center to bottom has (n - 1)/2 cells? Wait: center is at row n//2, column n//2. The vertical line goes down from center to bottom, so it includes the center and all cells below in the same column. Number of cells in vertical line = (n - 1)/2 + 1 = (n+1)/2. But the center is already counted in the diagonals, so total Y cells = (2n - 1) + ((n+1)/2 - 1) = 2n - 1 + (n-1)/2 = (4n - 2 + n - 1)/2 = (5n - 3)/2. For n=3, that's (15-3)/2=6, which matches: 3x3 Y has cells: (0,0),(0,2),(1,1),(2,1)? Actually for n=3, center (1,1). Diagonals: (0,0),(1,1),(2,2) and (0,2),(1,1),(2,0) -> union: (0,0),(0,2),(1,1),(2,0),(2,2) = 5 cells. Vertical down from center: (1,1),(2,1) -> adds (2,1). Total 6 cells. So formula (5n-3)/2 works for n=3: (15-3)/2=6. For n=5: (25-3)/2=11. Check: diagonals: 2*5-1=9 cells. Vertical down: center (2,2) plus rows 3,4 in col 2 -> 3 cells, but center already counted, so add 2. Total 11. Yes.
The non-Y cells must all be the same value, and that value must be different from the Y value.
There are only 3 possible values, so we can brute-force over all 3 choices for Y value and 2 choices for non-Y value (since they must differ).
Time complexity is O(n^2) to scan the grid once, and space O(1) extra.
Edge cases: n=1? But n is odd and at least 3? The problem says n is odd, but n=1 would have no Y shape? Actually for n=1, the Y shape is just the center? But definition requires two top diagonals and vertical line, which for n=1 would be just the center? Probably n>=3. Clarify if needed.
The Y shape is fixed; we don't need to consider rotations or other shapes.

AI-generated suggestions, not part of the candidate's original notes. May be inaccurate — verify before relying on them.