I solved this one in C++, and went with the naive method of iterating up from the number until I reached a palindrome. For the time complexity, the interviewer insisted it was linear in the distance between the answer and the original, but I pointed out that it was exponential in the number of digits, which I think was a better way of describing the scaling of the solution.