Adventures in Software Engineering Interviews: “Optimal” Longest Palindromic Substring
Here is the first article in the series: Misleadingly (NP-)Hard Problem
This is my friend’s story.
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:
Okay, I can think of four solutions:
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.I’ll start with #2 and work towards the asymptotically faster O(n log²n) solution with suffix trees.
Friend: “Here’s an O(n²) solution” [Proceeds to describe approach #2]
Interviewer: “Can you code it up?”
Friend: “Sure” [Whiteboards approach #2 pretty quickly, mentally preparing for approach #3]
Interviewer: [With over half the allotted time remaining] “Unfortunately, you started with the Optimal™ solution”
Friend: “…”
What.
