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

Interview Question

Software Engineer Intern Interview

Find the largest palindrome in a given word.

Answer

Interview Answer

2 Answers

0

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
0

Good old Suffix tree.

Gee on Sep 28, 2011

Add Answers or Comments

To comment on this, Sign In or Sign Up.