45 min. Brief introduction. 2 Coding questions.

1. Determine whether a string can be turned into a palindrome.
   This was really easy, but I felt my interviewer spent too much time on it. I explained why we can use a HashMap and just keep track of the number of each letter, and my interviewer just nodded. Then I wrote the code and the interviewer asked me to go through it with a few examples. Again, I spent like 10 additional minutes going through the examples with the interviewer. I felt the interviewer wanted me to spend too much time redundantly explaining my solution to the easy question.

2. For any given string, return all the palindromes longer than 1 character. Actually return a list of all of the palindromes.
   I came up with brute force, which was 2 nested loops and then making a new substring each time and then checking whether that string is a palindrome. That's O(n ^ 3) time. My interviewer asked how to improve it. I came up with a different way, but it was also O(n ^ 3). The interviewer also kept acting like my new way didn't make any sense. I found the problem online after the interview and my new way was actually listed in the solutions:
   https://leetcode.com/problems/palindromic-substrings/solution/
   There actually are O(n^2 log(n)) and O(n^2) solutions from what I read in the article, but I find it hard to believe someone should have come up with an O(n^2 log(n)) solution or an O(n^2) solution. Even the problem article says: Better approaches do exist to solve this problem in sub-quadratic [cubic if you want the actual strings] time, however those are significantly complex and impractical to implement in most interviews.

The interviewer also made remarks suggesting that I would move forward in the process. Lesson learned: always prepare to get rejected!

I'm not mad. Maybe there were candidates who got the sub-cubic complexities? Who knows :)