Find Palindrome With Fixed Length

Find Palindrome With Fixed Length

What is this problem about?

The Find Palindrome With Fixed Length interview question asks you to find the $n^{th}$ lexicographically smallest palindrome of a specific length $L$. For example, the $1^{st}$ smallest 3-digit palindrome is 101, the $2^{nd}$ is 111, and so on. You are given an array of queries (ranks) and the target length.

Why is this asked in interviews?

Companies like TikTok and VMware ask the Find Palindrome coding problem to test your mathematical intuition regarding palindromes. It evaluations if you realize that a palindrome is entirely determined by its first half. This allows you to transform a "find $n^{th}$ palindrome" problem into a simple "find $n^{th}$ number" problem. It's a great Math interview pattern.

Algorithmic pattern used

This problem follows the Palindrome Construction from Half pattern.

1. Half Length: A palindrome of length $L$ has a "determining half" of length $H = ceil(L / 2)$.
2. Start Value: The smallest $H$-digit number is $10^{H-1}$.
3. Find the Half: The $q^{th}$ smallest $H$-digit number is StartValue + q - 1.
4. Mirroring:
   • If this number has more than $H$ digits, the $q^{th}$ palindrome doesn't exist (return -1).
   • Otherwise, take this half-string and append its reverse (omitting the last character if $L$ is odd) to form the full palindrome.

Example explanation

$L = 3$, Query $q = 2$.

1. $H = ceil(3 / 2) = 2$.
2. Smallest 2-digit number is 10.
3. The $2^{nd}$ 2-digit number is $10 + 2 - 1 = 11$.
4. Mirror 11: $L$ is odd, so omit the last '1' when reversing. Full string: "11" + "1" = "111". Result: 111.

Common mistakes candidates make

• Brute Force: Trying to iterate through all numbers and checking if they are palindromes. For 15-digit numbers, this will never finish.
• Off-by-one: Mistakes in calculating the starting $H$-digit number or the $n^{th}$ offset.
• String Reverse logic: Failing to handle the "middle" character correctly for odd-length palindromes.

Interview preparation tip

Always remember that a palindrome of length $N$ is just a number of length $ceil(N/2)$ that has been mirrored. This insight reduces any palindrome search problem to a basic number range problem.