Amazon Interview Question: Find the largest palindrome i... | Glassdoor

Interview Question

Software Engineer Intern Interview

Find the largest palindrome in a given word.


Interview Answer

2 Answers


Assume a single character is a palindrome of size 1. To begin, iterate starting at the beginning of the list. If element[i-1] == element[i+1], then continue continue checking with 1 replaced with 2, and so forth. Eventually you'll arrive at a contradiction; set currentBest accordingly. Continue to end of list, replacing currentBest as needed.

One optimization, if (currentMax/2 > arrayLength - i) then stop searching; It is impossible to find a longer palindrome with the remaining portion of the list.

Anonymous on Apr 24, 2011

Good old Suffix tree.

Gee on Sep 28, 2011

Add Answers or Comments

To comment on this, Sign In or Sign Up.