Calculate the largest palindromic number from the product of two 6-digit numbers (100000 to 999999)
In an interview setting it is quite hard to come with an efficient solution (unless you happen to be very good in mental multiplication; however a \$99 * 91\$ example is a strong hint). The key to an efficient solution is an observation that

\$999999 * 999001 = 999000000999\$

is a quite large palindromic product. It means that you don't have to test the entire 6-digit ranges of multiplicands. It is enough to test multiplicands only in \$[999001.. 999999]\$ range. Just \$10^6\$ candidate pairs rather than \$10^{12}\$.

BTW, a similar identity holds for products of longer numbers as well.

Next, you may notice that there are just one thousand palindromic numbers larger than \$999000000999\$ (they are in form of 999abccba999), and to qualify as a solution is must have a 6-digit factor larger than \$999001\$. This implies the following algorithm (in pseudocode):

base = 999000000999
abc = 999
while abc &gt;= 0
    cba = reverse_digits(abc)
    number = base + abc * 1000000 + cba * 1000
    for factor in 999001 to sqrt(number)
        if number % factor == 0:
           return number
    abc -= 1


The reverse_digits of a 3-digit number could be done extremely fast (a lookup table, for example). Still a \$10^6\$ or so rounds, but no expensive tests for palindromicity.

All that said, since the problem stems from Project Euler #4 it is possible that it admits a more elegant number-theoretical solution.