Meta·Software Engineer·Technical Phone Screen·Intermediate

Intermediate

Jun 2026

Summary

Meta SWE coding round, one algorithmic problem about rotational symmetry of numbers. Pretty niche constraint-based generation problem that took me a minute to fully wrap my head around.

Questions Asked (1)

Given an integer n, find all n-digit numbers that look the same when rotated 180 degrees. Valid digit pairs under rotation are: 0↔0, 1↔1, 8↔8, and 6↔9.

Algorithms & Data Structures

Author's notes

First instinct was brute force: generate all n-digit numbers, check each one.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Recognize that a strobogrammatic number of length n can be formed by placing a valid digit pair at both ends and recursively constructing the middle. Use a recursive function that builds numbers from outside in, handling the base cases for even and odd lengths, and ensure no leading zeros for n > 1. Then generate all such numbers and return them.

Pro tip: Clarify with the interviewer whether the output should be a list of integers or strings, and discuss the time complexity O(5^(n/2)) and space complexity O(n) due to recursion depth. Mention that for n=1, the valid numbers are 0, 1, and 8, but 0 is typically excluded if n>1 due to leading zero constraint.

1. Understand the problem and constraints

Confirm that n-digit numbers cannot have leading zeros (except possibly n=1). Identify the valid digit pairs: (0,0), (1,1), (8,8), (6,9), (9,6). Note that 6 and 9 are only valid as a pair, not individually.

2. Define the recursive structure

A strobogrammatic number of length n can be formed by adding a valid pair around a strobogrammatic number of length n-2. Base cases: n=0 returns [""], n=1 returns ["0", "1", "8"].

3. Implement the recursive generation

Write a helper function that builds numbers of a given length, and for the outermost layer, skip the pair (0,0) if the current length equals n and n > 1 to avoid leading zeros.

4. Handle edge cases and return result

For n=1, return ["0", "1", "8"] (or exclude 0 if required). For n>1, ensure no leading zeros. Convert the resulting strings to integers if needed, and return the list.

5. Analyze complexity and test

Time complexity is O(5^(n/2)) because each recursive step adds one of 5 pairs (or 4 for the outermost layer). Space complexity is O(n) for recursion depth. Test with small n like 1, 2, 3 to verify correctness.

Key Points to Mention

Recursive construction from outside in, pairing digits symmetrically.
Base cases for even and odd lengths: n=0 and n=1.
Handling leading zeros: skip (0,0) at the outermost level when n > 1.
Valid digit pairs: (0,0), (1,1), (8,8), (6,9), (9,6).
Time complexity O(5^(n/2)) and space complexity O(n) due to recursion.
Edge cases: n=1 includes 0, but for n>1, 0 cannot be the first digit.

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