Adventures in Software Engineering Interviews: “Optimal” Longest Palindromic Substring
My friend’s pretty good at coding, having competed multiple times in the International Collegiate Programing Contest (it’s how we met). This interview was for an internship at a well-known tech company that is currently valued at north of a trillion dollars.
The interviewer asked “write a method that finds the longest palindromic substring”, and this was my friend’s thought process:
1. The naive O(n³) solution where you iterate through all substrings O(n²) and check if each is a palindrome O(n). 2. The more clever O(n²) solution where you take each letter and space between letters, O(n), and scan outwards to find the longest palindrome with that letter or space as the palindrome’s center, O(n). 3. There’s a O(n) solution after you build Suffix Trees, and there is an O(n) method of building suffix trees, but I only know the O(n log²n) method for suffix trees off the top of my head. 4. Manacher’s Algorithm, which is optimal at O(n), but I don’t know it.
